分治算法之芯片测试，递归算法和迭代算法，C语言实现_分治 坏的芯片 c++

分治算法之芯片测试（递归算法和迭代算法）C语言实现

`#include<stdio.h>
#include"time.h"
#include<stdlib.h>
struct Chip
{
int num; //芯片型号
int state; //芯片好坏
};
void rand1()//坏芯片的测试
{
{ int n=rand()%(1-0+1)+0;
printf("%d",n);
}

}
// 递归算法
void text_3(struct Chip XP[],int n)//
{
int k=0;
int m=n;
if(n=2)
{
if(XP[0].state1&&XP[1].state1)
{
printf(“好的芯片编号为%d”,XP[0].num);
return ;
}

else
{
printf(“好的芯片编号为%d”,XP[2].num);
return;
}

}

for(int i=0;i<=m;i=i+2)
{ srand((unsigned)time(NULL));
if(XP[i].state1 && XP[i+1].state1 || rand()%(1-0+1)+01&&rand()%(1-0+1)+01)
{
n=n-2;//记录所剩的个数
XP[k]=XP[i];//覆盖
k++;//记录覆盖之后还有几个数值
}
}
text_3(XP,k);

}
//_________________________________________________________________________________________//迭代法
void text_2(struct Chip XP[],int n)//n其实传入来是一个奇数a[0]-a[n]是偶数个
{ int k=0;//记录新数组有多少个
int m=n;
while(n>2)//这里有问题
{
for(int i=0;i<=m;i=i+2)
{ srand((unsigned)time(NULL));
if(XP[i].state1 && XP[i+1].state1 || rand()%(1-0+1)+01&&rand()%(1-0+1)+01)
{
n=n-2;//记录所剩的个数
XP[k]=XP[i];//覆盖
k++;//记录覆盖之后还有几个数值
}
}
m=k;
n=k;
}
if(n=2)
{
if(XP[0].state1&&XP[1].state1)
printf(“好的芯片编号为%d”,XP[0].num);
else
printf(“好的芯片编号为%d”,XP[2].num);
}
}void text_0( struct Chip XP[],int n)//测试轮空那一个芯片
{ int k=0;//记录测试最后一个芯片真实性
srand((unsigned)time(NULL));//设计随机小数，当芯片是坏的时候随机产生01，
for(int i=0;i<n;i++)//用n-1个对它进行测试
{
if(XP[i].state1)//当测试芯片是真的话直接访问
{
if(XP[n].state1)
k++;
}
if(XP[i].state0)//当测试芯片是坏的话就随机报数
{
int n=rand()%(1-0+1)+0;
if(n1)
k++;
}
}
if(k>=n/2)
{
printf(“第%d个芯片为好的芯片”,n+1);//如果为好的芯片，就直接输出该芯片
}
else//如果是坏的芯片就去掉最后一个，跳到偶数的方法
{
//text_2(XP, n-1);//迭代算法，用while
text_3(XP,n-1);//递归算法用函数。
}
}void text_1( struct Chip XP[],int n)//数量为单数的芯片测试方法，有括号的是地址，没括号的实体
{
text_0(XP,n);//直接测试最后一个
}void main()
{ int P=1;//退出条件的参数
int n;//芯片的数量
//srand((unsigned)time(NULL));//定义随机数的前提
printf(“请输入芯片的总数量(最多50个，最少3个)，每个芯片的编号以及好坏”);
scanf("%d",&n);
struct Chip XP[50] ={{0,0}};//定义长数组for(int i=0;i<n;i++)//芯片输入
{ printf(“请输入第%d个芯片编号以及好坏\n”,i+1);
scanf("%d",&XP[i].num);
scanf("%d",&XP[i].state);
}
switch(n%2)//当n奇数和偶数的选择方法
{
case 1: text_1(XP,n-1); break;// 奇数测试第n-1个是否为真测试
case 0: text_2(XP,n-1) ;break;//偶数测试
}}