Recently, when I was reading the introduction to algorithm, I saw this chip test problem. I thought about it for a long time and summarized my thinking

1. Problem description

Diogenes had n VLSI chips that were supposed to be identical, and in principle they could be tested against each other. The professor’s test device can measure two chips at a time. When two chips are placed in the device, each one tests the other and reports whether it is good or bad. A good chip can always report on whether another is good or bad, but the results of a bad chip are unreliable. Thus, the four possible outcomes for each test are as follows:

A chip report B chip report conclusion
B is good A is good Both are good or both are bad
B is good A is bad At least one piece is bad
B is bad A is good At least one piece is bad
B is bad A is bad At least one piece is bad
A) Demonstrate that if more than n/2 chips are bad, no strategy can be used to determine which chip is good in this paired test method. Suppose the bad chips could band together to trick the professor.

B) Assuming that more than n/2 of the chips are good, consider finding a good chip from n. Prove that n/2 pairs of tests are sufficient to reduce the size of the problem by nearly half.

C) Assuming that more than N /2 chips are good, prove that good chips can be found by θ (n) on the test. Give and solve the recurrence of the number of times an expression is tested.

2

  1. When both chips report good, if one A is bad, B is also bad because the other B says A is good
  2. When two chips report one good and one bad:
    1. The chip that says the other is good must be bad: suppose A says B is good, B says A is bad, and if A is good, then B is good, and B says A is bad, then B contradicts itself, so A must be bad.
    2. The chip that says the other party is bad may be good or bad: after the above analysis, A must be bad, so A’s statement is not credible (may be right or wrong), then B says A is bad, B can be good or bad
  3. When both chips report bad:
    1. First of all, they can’t both be good
    2. If one is good: if A is good, then A says B is bad; B is bad, so I don’t care what B says
    3. Both of them are bad, so it doesn’t matter what they say

3. Algorithm analysis

For problem A, the exhaustive method is used to compare any chip with all other chips. Since more than n/2 of the chips are bad, and the bad chips can be combined to deceive the professor, the test results are unreliable and it is impossible to judge whether the chip is good or bad.

For problems B and C, let’s assume that there are a good number of chips, b bad number of chips, z test pairs with all good test results, where all good test pairs are X, all bad test pairs are Y, x+y=z.

Design idea of divide and conquer algorithm

Here is the premise: good chip than bad chip at least 1 more! (The following example, if you don’t understand, you can assume that there are 4 or 6 chips in total)

One, random pair pairs, there are altogether⌊ n / 2 ⌋Yeah, test them separately.

Ii. According to the description of the problem:

(1) If the test results are one good and one bad, or two bad, then discard the pair:

  • It is easy to understand that the good is more than the bad. If one good is lost and the other bad is lost, then the good is still more than the bad. Let alone the two bad ones

(2) If the test results are two good, then discard one at will and leave the other:

  • Explanation: The main purpose is to reduce the size of the chip, after the first step, with both report good situation now, because more good than bad chip, so there is no all of the chip to test into a good one bad), the pair of two chips are good, or is bad, so casually throw a from each pair of chips, There were still more good chips than bad ones, but the number of chips was cut in half

(3) The case of odd number of chips should be considered:

  • ifnIs odd, the remaining chip is not paired. At this time, the test results in step (2) should be two good logarithms of chipszTo judge: ifzIs odd, discard this chip; ifzFor an even number (0 is also an even number), leave the chip.
    • Explanation :(a) whenzFor odd number, assume the worst case, namely a chip is good in the final remaining, assuming that the front (z – 1) for the same amount of good and bad chips, now with a pair of chip, the chip is good, or is bad, if is bad, the good chip number less than a bad chip count, not stand, the chip is good. That is whenzIs odd, logarithm of good chips – logarithm of bad chips >=1 pair, that is, the number of good chips – the number of bad chips >= 2, after losing half, the number of good chips – the number of bad chips >=1(see the figure below); Then the last extra chip must be thrown away, and the last good chip is more than the bad chip
    • If (b)zFor even (0 is also even), assuming the worst case, that is, the z is as good as the bad for the chip, then the extra piece must be good; If the extra piece is bad, then the logarithm of good and bad chips in z pairs is >=2 pairs, that is, the number of good and bad chips is >= 4, and the number of good and bad chips is >=2. Even if a bad chip is added, there are still more good chips than bad chips in the end

After this operation, the number of good chips left must still be greater than the number of bad chips, and after the ⌊n/2⌋ test, the size of the original problem was reduced by nearly half (problem (b) solved).

3. Repeat step (2). When n<=2, only good chips are left.

Since there are always more good chips than bad chips, there are only good chips when n<=2

Conclusion:

One good, one bad, or two bad pairs will have at least one bad pair, and discarding the pair will ensure that there will still be more good chips left than bad ones. The test result is all good, which may be good for the chip, may be all bad, randomly discard one, leaving one. Set the log of the good chip to x and the log of the bad chip to y. Consider the case of n: if n is even, then x>y, so the number of good chips left is still greater than the number of bad chips; If n is odd, there is an unpaired chip left. Consider the case of z: if z is odd, then x>y, discard the chip, so that the number of good chips left is still greater than the number of bad chips; If z is even, consider the situation of the chip: if the chip is good, then x>=y, leaving the good chip, so that the number of good chips left is still greater than the number of bad chips; If the chip is bad, then x-y>=2, leaving the bad chip, so that the number of good chips left is still greater than the number of bad chips. To sum up, the number of good chips left must be greater than the number of bad chips.Copy the code

For problem C: Using the operation method in B, the recursion is: f(n) = f(n/2) + n/2. This recursion conforms to the third case of the master theorem, so a good chip can be found by using θ (n) on the test.

Four, code implementation

class Test {
    public static void main(String[] args) {
    	// Use an array to store chips, 1 for good chips, 0 for bad chips, the following array always has 23 chips, 12 for good
        int[] arr = {1.0.1.0.1.1.1.1.0.1.0.0.0.0.1.0.1.0.0.1.0.1.1};
        System.out.println(Arrays.toString(getRight(arr,arr.length)));
    }

    // Define a test platform to simulate the test device in the problem, good chip output right, bad chip random output
    public static boolean[] judge(int x, int y) {
        boolean[] result = new boolean[2];
        if (x == 1 && y == 1) {
            result[0] = true;
            result[1] = true;
        } else if (x == 1 ^ y == 1) {
            result[0] = false;
            result[1] = ((int) (Math.random() * 2)) = =1;
        } else {
            result[0] = ((int) (Math.random() * 2)) = =1;
            result[1] = ((int) (Math.random() * 2)) = =1;
        }
        return result;
    }

    // Return a correct chip
    public static int[] getRight(int[] arr,int length) {
    	// If the number of chips is less than or equal to 2 and all chips are good, return
        if (length<= 2) {
            int[] z = new int[length];
            for (int i = 0; i < length; i++) {
                z[i] = arr[i];
            }
            return z;
        }
        // Here we use an array to store the selected chips. The array is defined as the worst case length. In other cases, there may be more bits behind the array
        // So use length to indicate the valid length of the array
        int[] tmp = new int[length / 2 + 1];
        boolean[] result = null;// This array is used to receive test results

        int point = 0;// Record the number of selected chips
        // The chips are tested in pairs
        for (int i = 0; i < length-1; i += 2) {
            result = judge(arr[i], arr[i + 1]);
            if(! result[0] ^ result[1]) {
                // If both chips are good, one of them will be selected at random
                int x = (int) (Math.random() * 2); tmp[point] = arr[i + x]; point++; }}// Consider the case where the total number is odd
        if (length % 2= =1) {
        	// In this case, we should judge according to the selected number. Even numbers are added and odd numbers are thrown away
            if (point % 2= =0) {
                tmp[point] = arr[length - 1]; point++; }}// Recursively, continue testing in pairs until the number of chips is less than three
        returngetRight(tmp,point); }}Copy the code