There are many classical paradigms to solve the small ball problem, and here we only talk about one of the most widely used-ternary coding solution.

Why do you think of using ternary? Actually, it's quite understandable Let's consider the state of the ball, including: not on the balance, on the left side of the balance, and on the right side of the balance. We might as well use some numbers to represent these three States:

0- Not on the balance

1-put it on the left panel of the balance.

2—— Put it on the right panel of the balance.

In this way, we can use a number string to represent the weighing process of a ball. For example, the code of a ball is 2 10 120, which means that the ball is weighed on the right plate for the first time, the left plate for the second time, the balance for the third time, the left plate for the fourth time, the right plate for the fifth time and the balance for the sixth time. Very simple, just use a number string to express the complicated weighing process of the ball.

For the sake of explanation, the problem is described as "12 ball weighs three times", but you can easily summarize it as "m ball weighs n times". Ok, let's talk less and get down to business.

Suppose we coded 12 balls in non-repetitive ternary code, and we will operate completely according to the coding when weighing. Step 0, we put the number 0 of 1 on the ball of 12 on the left side of the balance, and put the number 0 on the 2 on the right side of the balance, and record the weighing results; In step 1, we put 1 on the 12 ball on the left side of the balance, put 1 ball on the right side of the balance, and put 0 ball on the balance without 1 ball, and record the weighing results. In this way, the code has n bits, and we weigh it n times to get n groups of results.

Status of inspection results: the balance is balanced, the left side of the balance is lighter than the right side, and the left side of the balance is heavier than the right side. Huh? There are three kinds anyway. (hia hia, what a coincidence, the fun is yet to come) We use 0 to represent the balance, 1 means that the left side of the balance is lighter than the right side, and 2 means that the left side is heavier than the right side; In this way, after N times of weighting, we get an N-bit result code, which is also a ternary code. Note: this code may be the same as the code of a ball! :)

You seem vaguely aware of something. Ok, now let's get to the point: the code of the result is the same as that of the non-standard ball, or there is a direct correspondence. What is the relationship? Look down)

If we have determined the weighing method of a group of balls (corresponding to the ternary code of 12 balls), then now, conversely, the balls originally placed on the left plate of the balance at a certain step are now placed on the right plate of the balance, and the balls originally placed on the left plate of the balance are now placed on the right plate of the balance, but the balls originally not placed on the balance should not be placed on the balance. So the ball code obtained in this way (also 12) is a copy of the original ball code? Obviously, it is not repetitive. We call the code obtained by this correspondence a dual code (defined here as: every bit in the code, 1 is replaced by 2, and 2 is replaced by 1, 0 is unchanged, so the new code is called the dual code of the original code. For example, the double code of 22 102 is 1 1, or 22 10 1 and1are both double codes). At this time, you will consider such a question-how many 3-digit ternary codes are there? The answer is 3 3 = 27 codes (marked as 3 n), three more than the 24 codes mentioned above. Why do you want to study this kind of symmetric code? Because we put balls A, B, C and D on the left panel, and balls A', B', C' and D' on the right panel-the significance of weighing is the same as that of putting balls A', B', C' and D' on the left panel and putting balls A, B, C and D on the right panel, and the result is the same. Therefore, to realize this algorithm, code selection is very important-choose one of a pair of dual codes to number the balls.

At this point, I think you must have guessed-what are the three codes with 27 more than the above 24 codes? 000, 1 1 1, 222 respectively. 000 and itself are double codes, and 1 1 1 and 222 are double codes. Why get rid of the three of them? I don't want to explain here. To solve this problem, we have to look at the mathematical proof behind!

Therefore, we come to the conclusion that if a group of ternary codes are correctly selected to number the balls respectively, then the result code obtained in strict accordance with the weighing process of ball coding must be the code of non-standard ball or its dual code. (Because the codes of any two balls are not double codes, our weighing operation only determines non-standard balls. ) The proof method of this conclusion is too complicated (I typed 4 pages in word), so I put it at the end of the article and downloaded it.

Let's talk about the specific process of program coding first.

Referring to the above figure, we first get a code array to store the code. To save space, the code array stores decimal code in my program. I use GetTheBall.num2Code () and GetTheBall.code2Num () to realize the conversion between ternary and decimal. We first store all the codes in the array, then remove the three codes 000, 1 1 1 222, and then delete the remaining half of the codes to get the 12 code mark of the ball. For codes starting with 1, we select all codes greater than 1 1. For the code starting with 2, we cross out the dual code of "the code starting with 1". For codes that start with 0, we choose the code position from left to right, and the first number that is not 0 is 65430.

All right, count. Look, half of it has been deleted, and half is left. According to the coding method in the above figure, the result code obtained after operation, if in ball coding, the coded ball is non-standard and lighter than the standard ball. If the result code is not in the small ball code, then the result code is the dual code of the nonstandard ball, and the nonstandard ball is heavier than the standard ball.