用html做家谱网站代码,玉溪建设网站,网站建设服务要交印花税吗,东莞外贸网站搭建制作实验2 芯片测试算法设计
一、【实验目的】
#xff08;1#xff09;理解分治策略的设计思想#xff1b;
#xff08;2#xff09;熟悉将伪码转换为可运行的程序的方法#xff1b;
#xff08;3#xff09;能够根据算法的要求设计具体的实例。
二、【实验内容】 有…实验2 芯片测试算法设计
一、【实验目的】
1理解分治策略的设计思想
2熟悉将伪码转换为可运行的程序的方法
3能够根据算法的要求设计具体的实例。
二、【实验内容】 有n片芯片其中好芯片比坏芯片至少多1片现需要通过测试从中找出1片好芯片。测试方法是:将2片芯片放到测试台上2片芯片互相测试并报告测试结果:“好”或者“坏”。假设好芯片的报告是正确的坏芯片的报告是不可靠的。请设计一个算法使用最少的测试次数来找出1片好芯片。
提示:可参考教材P29页的算法2.3. 测试函数可以采用以下方法。
#include stdio.h
#include stdlib.h
#include time.h
//建立测试函数参数iA表示主动测试芯片 iB表示被测芯片.返回值为被测芯片的测试值
//值为1时表示好芯片为0时表示坏芯片.
//应用随机数来表示不确定的值1、0.注意:在主函数中加上随机数种子语句srand(time(NULL));
//算法的输入可以用数组表示比如:ABc[17]{1,0,0,1,1,1,0,0,1,1,1,1,0,1,0,0,0} 表示17个芯片其中9片好芯片、8片坏芯片。
int X_test(int iA,int iB)
{ if(iA1) return iB; return rand()%2;
}
三、实验源代码
#include iostream
using namespace std;
#include time.h
#include queueint input[] {-1, 1,0,0,1,1,1,0,0,1,1,1,1,0,1,0,0,0}; // 输入数组表示每个芯片的质量// X_test函数用于测试两个芯片之间的连接情况
int X_test(int iA, int iB)
{if(iA 1)return iB;return rand()%2; // 随机返回0或1
}// testOneChip函数用于测试一个芯片与其他芯片的连接情况
int testOneChip(int chip, int n)
{int count;for(int i1; in; i){count X_test(input[chip], input[i]);}if(count (n-1)/2) // 奇数至少有(n-1)/2个报好return true;else //否则报坏return false;
}// main函数是程序的入口点
int main()
{srand(time(NULL)); // 设置随机数种子int n 17; // 芯片数量int k n; // 当前待测试的芯片数量queueint q; // 使用队列存储待测试的芯片下标for(int i1; in; i)q.push(i); // 将芯片下标入队while(k 3){for(int i1; i k/2; i){int chipIndex1 q.front(); // 取出队列头部的芯片下标q.pop();int chipIndex2 q.front(); // 取出队列头部的芯片下标q.pop();int test1 X_test(input[chipIndex1], input[chipIndex2]); // 测试两个芯片之间的连接情况int test2 X_test(input[chipIndex2], input[chipIndex1]); // 测试两个芯片之间的连接情况if(test1 test2 test2 1) // 如果两个芯片都连接良好则任取一片留下{q.push(chipIndex2);}else{; // 丢弃}}if(k % 2 1) // 如果剩余芯片数量为奇数则对最后一片芯片进行单独测试{int chipIndex1 q.front();q.pop();if(testOneChip(chipIndex1, n) true) // 如果该芯片与其他芯片连接良好则将其加入队列q.push(chipIndex1);}k q.size(); // 更新当前待测试的芯片数量}int chipIndex1 q.front(); // 取出队列头部的芯片下标q.pop();int chipIndex2 q.front(); // 取出队列头部的芯片下标q.pop();if(k 3) // 如果剩余芯片数量为3则进行最后一次测试{int test1 X_test(input[chipIndex1], input[chipIndex2]); // 测试两个芯片之间的连接情况int test2 X_test(input[chipIndex2], input[chipIndex1]); // 测试两个芯片之间的连接情况if(test1 || test2) // 如果至少有一个芯片连接良好则输出该芯片的下标{cout q.front() endl;return 0;}}if(k 2 || k 1) // 如果剩余芯片数量为2或1则直接输出其中一个芯片的下标{cout chipIndex1 endl;return 0;}
}
四、实验结果
第12片是好芯片
