Balance is called a small ball problem
The balance said that there are many classic paradigm solutions, which we talk about only one of the most widely used applications here.
Why do you think of using a three-way? In fact, it is very understandable. Let us consider the state of the ball, there are: not placed on the balance, in the left side of the balance, three kinds in the balance. We may wish to use some digital to indicate these three states: 0-- did not put it on Tianping 1 - put in the left side of the balance 2 - Put in the balance right, we can use a digital string to represent a small The ball is weighed, such as a small ball code is 210120, indicating this small ball, the first weighing in the right disk, the second time in the left, the third is not in the sky, the fourth time Left disk, fifth time in the right disk, the sixth time is not in the balance. Very simple, just use a digital string to expand the small ball complex weighing process.
In order to facilitate explanation, the following will describe this problem with "12 small balls", however, you can easily be able to promote "M small ball said N times". Ok, idle words, books are positive.
Suppose we have made 12 small balls, no repetition, weigh, we are completely followed by coding, step 0, we put the code 0 in 12 small balls in Baiping On the left, the number 0 bits 2 is 2, and if the code 0 bit is 0, it is not placed on the balance, and the weighing result is recorded; step 1, we put the code on 12 small balls No. 1 The bit is 1 of the left side of the balance, the encoding of the first bit is 2, the number of the balance, the code 0] is not placed on the balance, and the weighing result is recorded; so, the encoding has n, we I will weigh the N times to get the N group results.
Investigate the status of the results: balance balance, the left side of the balance is lighter on the right, and the left side of the balance is more than the right. Huh? How is it three kinds. (Hia Hia, no book, good play is still behind) 0 to represent balance balance, lightly in the right side of the left side, focus on the right side of 2 bales; this, we have weeded N times The results of the n bit are encoded, and it is also a three-way encoding. Note: This code is likely to be the same as the code of a small ball! :)
You seem to have a confidence that I have realized what. Ok, now pick the questions: obtained the result encoding, like the coding of non-standard ball, or have a direct correspondence. (What is this relationship?
If we have determined a group of small balls (corresponding to 12 small ball 3), now, now, it is considering that the small ball of the left place in a step is now in the right point of the balance. The small ball on the left side of the balance is now on the right side of the balance. The ball that is not placed on the balance should not be placed on the balance. So this gotbook code (also 12) and the original repetition? Obviously, no repetition, we call the encoded by this correspondence to a pair (here next definition: put each digit in the encoding, 1 to 2, 2) to 1, 0 unchanged, get new coding called The original encoded pair. As 22102, the dual code is 11201, or 22101 and 11201 are mutually pair. At this time, you will consider such a problem - how many 3 binary codes? The answer is 3 ^ 3 = 27 (remembered 3 ^ n), more than 3 of the 24 encodes mentioned above. Why study this symmetrical code? Because we put A, B, C, D ball on the left side, put A ', B', C ', D' ball to the right disk - with us with A ', B', C ', D' Ball Put it left on the left, put A, B, C, D ball to the right disk, the weighing meaning is the same, the result is the same, we must avoid this repetitive operation. Therefore, this algorithm is realized, it is important to select a code - select one of the pair of pairs of pupensions to give the ball number. Here, I think you must guess - 27 more than the above 24 code? They are 000, 111, 222.000 and itself for dual code, 111 and 222. Why do you want to remove them? I don't think I still explain here, I have to solve this problem, you have to look at the following mathematics prove! So, we conclude that if a set of 3 enter code is correctly selected, it is used to give the ball number, then the results code obtained in strict accordance with the weighing process of the ball, inevitably be a non-standard ball code, or His pair is. (Because we give the small ball's encoding, any two small balls are not mutually pair, so our weighing operation is the only certificate of non-standard balls). The proof method of this conclusion is too complicated (I use word to play with Word " 4 pages), so put it in the text.
Let's talk about the specific process of the program to implement the encoding. Refer to the picture above, we first get the code to store the code with a Code array. In order to save space, in my program, the Code array is stored in the decimal code. I use gettheball.num2code () and gettheball.code2num () to implement three-in-one And the mutual conversion between the decimal system. We first deposit all the encodings into an array, then remove the three encodings of 000, 111, 222, then remove half of the residual encoding, and 12 encoded marks to the ball. For 1 out of the code, we choose all the encodings larger than 111. For 2-start coding, we will go to "1 of the unchecked part of the package", for the code, we choose from In the left-right coding bits, the first number of not 0 is 1 coding (here is very difficult, in fact, the first number of not 0 is not 1 is 2, we deleted it is 2 half). Ok, count, optimistic about half of half. According to the coding method of the above figure, the results obtained by the operation, if in the small ball code, the encoded ball is non-standard ball and is light than the standard sphere. If the result code is not in the small ball coding, the result code is a non-standard ball for dual code, non-standard ball ratio of standard ball.
Ok, I will tell a paragraph here. In fact, if you want to understand the meaning of this algorithm, why should I encode this, why is this correct, but also a strict mathematical certificate. Solving the texture of the balance with the three-way law, I have to pass my brothers Anxinghua, and the mathematical proof of this article is also not active, it may be a master from the CoI national team, I don't know the author The name, that article is also a disabled, which may be wrong, put it here to provide some information to beginners. So if you find a problem, please don't finish your point. If you know the original source and the original author, please contact me. My source code (Java version) related mathematical proof
