In this lab, I define 4 classes to implement the method.1.The first is Good with no attribute, just used to classify it’s a good chip.2.The second is Bad, the same with the Good class, but to express it’s a bad chip;3.The third is Test, used to find a good chip in the chip arrays . and here we use 分而治之法.4.The last is instance, using the good chip chosen in the third class to test other chips and print the outcome whether the chip is bad or good. And we use instanceof sign to test whether our outcome is true or not.(if chip is the instance of Good ,then it’s a good chip, otherwise it’s a bad one and compare with the outcome generated by the method in Test, we can judge whether the method can give what we want)Something added to my code.(1)I use arraylist to implement the array of chips and use two classes good andbad to represent good chips and bad chips.(2)I use true or false to represent 1 and 0 to express the outcome by mutual test.(3)To random the position of my chips, I use 伪随机. At first ,put the array intothe arraylist and then random some position and get the element at thisposition to the last of the array, so that we can get the random configuration of good and bad chips.代码部分//Class 1//define a good object which represent good chips without anyproperties.public class Good {}//Class 2//define a bad object which represent bad chipspublic class Bad {}//Class 3import java.util.ArrayList;public class Test {public static Object ultimate;/** the AtestB method is conformed with the requirement gg istrue ,gb is false, bg is true/false, bb is true/false, which is random because the chip is bad ,it has no ability to judge , and i use true and false to represent 0 and 1*/static boolean AtestB(Object A, Object B) {Good good = new Good();Bad bad = new Bad();if instanceof Good && B instanceof Good)return true;else if ((A instanceof Good && B instanceof Bad))return false;else {// use random to get the outcomeint result = (int) (Math.random() * 2);if (result == 0) {return false;} elsereturn true;}}// use n/2 method 分而治之static void nTest(ArrayList all) {int length = all.size();int divide = length / 2;ArrayList first = new ArrayList();ArrayList last = new ArrayList();ArrayList newList = new ArrayList();/** divide the arraylist all into 2 arraylist and test two objects whose* index are the same*/for (int i = 0; i < divide; i++) {first.add(all.get(i));}for (int i = divide; i < 2 * divide; i++) {last.add(all.get(i));}// if the length is odd, then judge whether divide/2 is evenif (length % 2 == 1) {// if divide/2 is even, then add the last element of "all" which is// left in the above procedure to the newListif (divide % 2 == 0) {newList.add(all.get(2 * divide));}}// if the test is all true and leave either one ,here I choose the// element in first arraylistfor (int i = 0; i < divide; i++) {if (AtestB(first.get(i), last.get(i))&& AtestB(last.get(i), first.get(i))) {newList.add(first.get(i));}}/** if arraylist has odd number, put the last one to temp and add it to* the newlist at last*/int newLength = newList.size();// if the length of the newList is 0,then the last one is a good chip,// and return it// if the length is 1,it must be a good chipif (newLength == 1) {ultimate = newList.get(0);return;}if (newLength == 0) {System.exit(0);}elsenTest(newList);}}//Class 4import java.util.ArrayList;public class Instance {/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubArrayList array = new ArrayList();// make sure the good chips are greater than bad chips so that the// outcome is reliableint number = (int) (Math.random() * 1000);// the total number is// produced by randomint badNum = (int) (Math.random() * number); // the total number is// produced by randomif (badNum > number / 2) {System.out.println("the result will beunreliable,please try again!");System.exit(0);}int goodNum = number - badNum;// add good and bad chips into the array in sequence atfirstfor (int i = 0; i < badNum; i++) {array.add(new Bad());}for (int i = badNum; i < number; i++) {array.add(new Good());}// do the random change position so that the position of good and bad// chips are random rather than in sequencefor (int i = 0; i < 1000; i++) {int random = (int) (Math.random() * (number / 2));array.add(array.get(random));array.remove(random);}// output the total number and the good number and bad numberSystem.out.println("The total numbers of chips are " + array.size()+ "\n there are " + goodNum + " good chips. \n there are "+ badNum + " bad chips");Test test = new Test();test.nTest(array);// use the right one chose in the test method to test other chip so that// we can get the entire outcomefor (int i = 0; i < array.size(); i++) {if+ (i + 1)+ "st chip is good ");elseSystem.out.print("The test outcome the " + (i + 1)+ "st chip is bad ");// use the instanceof method to test whether the chip is good or bad// to test the outcome aboveif (array.get(i) instanceof Good)System.out.println("The right outcome the " + (i + 1)+ "st chip is good");elseSystem.out.println("The right outcome the " + (i + 1)+ "st chip is bad");}}}The naïve method which I didn’t write use this method: test an element by all other element of the array in sequence ,record all of the outcome anddo the circulation for every element until you find an element with the outcome like Num(true) >= Num(false).<Num(true) represents the numbers of true outcome , and Num(bad) represents the numbers of bad outcome>For there are N chips, A good chips and B bad chips and A > B, if N is odd, then A >= B+1,if what we test is a good chip ,then at least Numb(true) = A – 1 = Num(false).<all of the good chips say it’s good and all of the bad chips say it’s a bad chip>, if what we choose is a bad chip, then at least Num(false) = A > Num(true) = B – 1. <all of the good chips say it’s bad and all of thebad chips say it’s a good chip>. If N is even , then A >= B + 2, if we choose an good one, the worst case is ,Num(true) = A – 1 >= B + 1>Num(false) = B, if we choose a bad one ,Num(false) = A > Num(true) = B – 1. In conclusion, whether N is old or even ,as long as A > B, if we get the outcome like Num(true) >= Num(false), we can know that the chip is a good one. And we can use it to test all the other chips in the array and print the outcome to be seen by the professor.If we have B > A , the number of bad chips are bigger than that of good chips.If N = odd , B >= A + 1 When test a bad chip ,it’s possible we can get the result like, Num(true) = B – 1 >= Num(false) = A, and when we test a good chip, it’s possible that we can get the result Num(false) = B >= Num(true)= A – 1; if N = even ,B >= A +2, When test a bad chip ,it’s possible we can get the result like, Num(true) = B – 1 > Num(false) = A, and when we test a good chip, it’s possible that we can get the result Num(false) = B >=Num(true) = A – 1; so the outcome we get will be not right.About the b problem , I use Chinese to explain.分而治之法：分情况考虑(1)n为偶数随机的两两配对，则共有n/2对，分别测试<在我的代码里是从中间分成两个array，然后让两个数组里面的下标相同的去比较测试>。
