【芯片测试】有n片芯片，已知好芯片比坏芯片至少多1片。现在需要通过测试从中找出1片好芯片，测试方法如下：将2片芯片放到测试台上，2片芯片互相测试并报告测试结果（即好或者坏）；其中，好芯片的报告是正确的，而坏芯片的报告是不可靠的。为保证使用更少的测试次数，请设计一个合适的算法解决上述问题
算法设计思路
如果芯片数量为偶数，则逐个测试两个，并将测试存储的芯片存储在原始阵列中记录芯片下标的阵列中。 如果芯片为奇数，则从第一个芯片继续测试最后一个芯片。 测试到最后的芯片后，如果好的次数在芯片数的一半以上就表示是好的芯片，否则就表示是坏的芯片。 如果是坏芯片，就相当于不在意它，奇数减去1变成偶数。 如果为偶数，则每次遍历两个，因此如果最后一块芯片是坏芯片，则即使是额外出现的奇数也不会遍历。 (即使有5枚芯片，第1枚和第2枚也互相测试，第3枚和第4枚互相测试，n 2在5以上且6以上，所以如果不符合循环条件，就不会自然地遍历到最后。)
再开始测试这个数组的对应原始数组的后缀2，2。 1、测试结果好的话，选一张保存。 2、考试结果好不好，或者两者都不好的话就扔掉。 这个方法保证扔掉的坏芯片最终会成为好芯片以上。
将测试并保存的芯片放回此数组，每次从该数组的开头放入，复盖上一组的数据，循环到剩下的3片芯片或1片、2片。 好的筹码总是比坏的筹码多一枚，所以剩下三枚的时候，随便拿两张就能得到一枚好的筹码。 (假设有两张好的筹码，也照原样留下，好的筹码和坏的筹码都扔掉，剩下的是好的筹码。 )剩下2张或剩下1张时，一定会成为好的筹码。
算法实现的伪代码
3358 www.Sina.com/http://www.Sina.com/http://www.Sina.com /
输入：存储芯片的数组、左下标、右下标
输出：布尔值
if (chip arr [ left ]=truechiparr [ right ]=true ) return true； else if ((chip arr [ left ]=truechiparr [ right ]=false )|) chip arr [ left ]=falsechiparr [ right ]=true ) ) returre else返回假；
3358 www.Sina.com/http://www.Sina.com/http://www.Sina.com /
输入：存储芯片的数组、左下标、右下标
输出：布尔值
计数如果剩余芯片为奇数，则用于记录比较结果为真的次数的temp[chipArr.length]经过筛选的芯片的后缀Chip=chipArr.length剩余芯片数fori=0toch iparry=I=0)奇数比较芯片=芯片1最后芯片下标，相互测试其他芯片和最后芯片的if count是芯片数量的一半以上then这是好芯片，直接输出n=芯片保留芯片的数量chi=0f or I
算法
import java.util.Random； 公共类主{ staticrandomr=new random (； publicstaticvoidmain (字符串[ ] args ) { boolean[] chipArr={false，false，true，false，true，true，tru
e,true,true,false};//初始化数组 chipTest(chipArr); } public static void chipTest(boolean[] chipArr) { int count = 0; //当剩余芯片为奇数的时候用于记录对比结果为true的次数，若count >= 芯片数的一半，则说明被检测的那个芯片（选取最后一个）是好芯片，否则坏芯片 int[] tempArr = new int[chipArr.length]; //用于记录筛选出来的芯片的下标 int Chip = chipArr.length; //剩余芯片数 for (int i = 0; i < chipArr.length; i++) { tempArr[i] = i; //为记录数组初始化，值对应这chipArr的下标 } while (Chip > 3) { //当剩余芯片数大于3的时候就一直比较 if (Chip % 2 != 0) { //剩余芯片数为奇数时，用暴力算法，比较最后一枚芯片和其他芯片 int compareChip = Chip-1; //最后一枚芯片的下标 for (int i = 0; i < compareChip; i++) { //从第一枚芯片开始到最后一枚的前一枚与最后一枚芯片比较 if(compare(chipArr,compareChip,i)) count++; //若返回为true，则count++ if(count >= (Chip-1)/2){ //若刚刚好最后一个为好芯片，则直接输出，结束循环 System.out.println(tempArr[i]); break; } else count = 0; } if(count >= (Chip-1)/2) break; } int n = Chip; //记录剩余芯片数 Chip = 0; //令Chip为0，后面重新计算剩余的芯片数 for (int i = 1; i < n; i+=2) { //用后一枚芯片与前一枚芯片比较，两个两个比较 if(compare(chipArr,tempArr[i-1],tempArr[i])){ tempArr[Chip++] = tempArr[i-1]; //如果为真，temp数组以chip为下标就记录下原数组的该芯片的下标，剩余芯片+1 } } } if(Chip==3){ //若剩余芯片刚好为3，则直接判断，得出好芯片 if(compare(chipArr,tempArr[0],tempArr[1])){ System.out.println(tempArr[0]); }else System.out.println(tempArr[2]); }else System.out.println(tempArr[0]); } public static boolean compare(boolean[] chipArr, int left, int right) { //两枚芯片互相测试 if (chipArr[left] == true && chipArr[right] == true) { return true; } else if ((chipArr[left] == true && chipArr[right] == false) || (chipArr[left] == false && chipArr[right] == true)) { return false; } else { if (r.nextInt(3) == 0) { //两片芯片为坏的时候，有三分之一的概率返回测试结果为两个都为好 return true; } else return false; } }}
写得不好，多请谅解！