20CN网络安全小组论坛 - 编程破解 - MS面试问题！！你们会吗？？我想了30分钟啊

论坛: 编程破解标题: MS面试问题！！你们会吗？？我想了30分钟啊

复制本贴地址

作者: wan0000 [wan0000]

论坛用户

12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）

地主发表时间: 04-01-02 11:49

回复: 286 [unique]

版主

There are 12 coins, all identical in appearance, and all indentical in weight except for one, which is either heavier or lighter than the remaining 11 coins. Devise a procedure to identify the counterfeit coin in only 3 weighings with a balance.
After much struggle I came up with a solution in which I put coins on the pans of the balance for the next weighing based on the outcome of the previous weighing. It was a solution I had to keep on a sheet of paper because it was too hard to remember all the cases.
Much later, while on the faculty at Ohio State, I heard that the graduate student Rick Wilson (of Lucky 7 fame) had discovered a solution of the Counterfeit Coin Problem based on the finite projective plane of order 3. His solution had the wonderful feature that what coins go on which pan does not depend on the outcome of any weighing; moreover, once the three weighings are completed, the counterfeit coin is immediately identified.

I never wrote down Rick's solution (if I ever knew it) and some years later tried to rediscover it. I failed; but the following idea came to me. For each of the three weighings three things can happen; the left pan goes down, the right pan goes down, or the pans balance. With three weighings, that's 27 possible outcomes. Each possible outcome can be represented by an ordered triple ... or a three-digit number in base 3! If I can place the coins on the pans in the right way, the base 3 number representing the outcome of the three weighings would be the label of the counterfeit coin, and its sign, positive or negative, would tell me whether the counterfeit was lighter or heavier than the good coins!

I organized things as follows. The first weighing would represent the nines place, the second weighing the threes place, and the final weighing the units place. I chose "the left pan goes down" to represent the digit 1 and "the right pan goes down" represents the digit -1. The digit 0 represents the pans balancing. Then I placed the 12 coins on the pans in such a way that, if any one of them turned out to be counterfeit and heavy, the outcome of the weighing would be a positive number in balanced ternary notation. Here is how the numbers are placed on the pans according to these rules.

left pan right pan
(9) first weighing 5,6,7,8,9,10,11,12
(3) second weighing 2,3,4,11,12 5,6,7
(1) third weighing 1,4,7,10 2,5,8,11

Obviously this assignment of coins to pans cannot work because the number of coins per pan in the first two weighings are not equal. However, if we interpret the sign of the outcome for certain coins oppositely, we can insure that the coin assignment to the pans is four coins per pan. Accordingly, I chose to place the coins 7, 9, 11, and 12 to be placed so that the outcome weighing would have a sign opposite to the correct sign. This produced the assignment

left pan right pan
(9) first weighing 5,6,8,10 7,9,11,12
(3) second weighing 2,3,4,7 5,6,11,12
(1) third weighing 1,4,10,11 2,5,7,8

For example, if the counterfeit coin is 6 and heavier than the other coins, then, in the first weighing, the left pan goes down, in the second weighing the right pan goes down, and in the last weighing the pans balance. This produces the base three number (1,-1,0)=9-3+0=6, indicating that the counterfeit coin is the sixth coin and it is heavier than the other coins because 6 is positive. If the counterfeit coin is 5 and lighter than the other coins, then, in the first weighing, the right pan goes down, in the second weighing the left pan goes down, and in the last weighing the left side goes down. This produces the base three number (-1,1,1)=-9+3+1=-5, indicating that the counterfeit coin is the fifth coin and it is lighter than the other coins. The coins 7, 9, 11, and 12 are treated oppositely. If the counterfeit coin is 7 and is heavier than the other coins, then, in the first weighing, the right pan goes down, in the second weighing the left pan goes down, and in the last weighing the right pan goes down. This produces the base three number (-1,1,-1)=-9+3-1=-7, indicating, for this special case, that the counterfeit coin is the seventh coin and it is heavy because we reverse the sign for the specially treated coins.

You cannot fail to notice that this method should be able to handle thirteen coins. However, to maintain the same number of coins per pan, we need a coin guaranteed to be good. The table below takes care of this situation with G representing the known good coin.

left pan right pan
(9) first weighing 5,6,8,10,13 7,9,11,12,G
(3) second weighing 2,3,4,7,13 5,6,11,12,G
(1) third weighing 1,4,10,11,13 2,5,7,8,G

B1层发表时间: 04-01-02 12:00

回复: 286 [unique]

版主

将十二个球编号为1-12。

第一次，先将1-4号放在左边，5-8号放在右边。
　　1.如果右重则坏球在1-8号。
　　　　第二次将2-4号拿掉，将6-8号从右边移到左边，把9-11号放
　　　　在右边。就是说，把1,6,7,8放在左边，5,9,10,11放在右边。
　　　　　　1.如果右重则坏球在没有被触动的1,5号。如果是1号，
　　　　　　　则它比标准球轻；如果是5号，则它比标准球重。
　　　　　　　　第三次将1号放在左边，2号放在右边。
　　　　　　　　　　1.如果右重则1号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则5号是坏球且比标准球重；
　　　　　　　　　　3.这次不可能左重。
　　　　　　2.如果平衡则坏球在被拿掉的2-4号，且比标准球轻。
　　　　　　　　第三次将2号放在左边，3号放在右边。
　　　　　　　　　　1.如果右重则2号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则4号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则3号是坏球且比标准球轻。
　　　　　　3.如果左重则坏球在拿到左边的6-8号，且比标准球重。
　　　　　　　　第三次将6号放在左边，7号放在右边。
　　　　　　　　　　1.如果右重则7号是坏球且比标准球重；
　　　　　　　　　　2.如果平衡则8号是坏球且比标准球重；
　　　　　　　　　　3.如果左重则6号是坏球且比标准球重。
　　2.如果天平平衡，则坏球在9-12号。
　　　　第二次将1-3号放在左边，9-11号放在右边。
　　　　　　1.如果右重则坏球在9-11号且坏球较重。
　　　　　　　　第三次将9号放在左边，10号放在右边。
　　　　　　　　　　1.如果右重则10号是坏球且比标准球重；
　　　　　　　　　　2.如果平衡则11号是坏球且比标准球重；
　　　　　　　　　　3.如果左重则9号是坏球且比标准球重。
　　　　　　2.如果平衡则坏球为12号。
　　　　　　　　第三次将1号放在左边，12号放在右边。
　　　　　　　　　　1.如果右重则12号是坏球且比标准球重；
　　　　　　　　　　2.这次不可能平衡；
　　　　　　　　　　3.如果左重则12号是坏球且比标准球轻。
　　　　　　3.如果左重则坏球在9-11号且坏球较轻。
　　　　　　　　第三次将9号放在左边，10号放在右边。
　　　　　　　　　　1.如果右重则9号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则11号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则10号是坏球且比标准球轻。
　　3.如果左重则坏球在1-8号。
　　　　第二次将2-4号拿掉，将6-8号从右边移到左边，把9-11号放
　　　　在右边。就是说，把1,6,7,8放在左边，5,9,10,11放在右边。
　　　　　　1.如果右重则坏球在拿到左边的6-8号，且比标准球轻。
　　　　　　　　第三次将6号放在左边，7号放在右边。
　　　　　　　　　　1.如果右重则6号是坏球且比标准球轻；
　　　　　　　　　　2.如果平衡则8号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则7号是坏球且比标准球轻。
　　　　　　2.如果平衡则坏球在被拿掉的2-4号，且比标准球重。
　　　　　　　　第三次将2号放在左边，3号放在右边。
　　　　　　　　　　1.如果右重则3号是坏球且比标准球重；
　　　　　　　　　　2.如果平衡则4号是坏球且比标准球重；
　　　　　　　　　　3.如果左重则2号是坏球且比标准球重。
　　　　　　3.如果左重则坏球在没有被触动的1,5号。如果是1号，
　　　　　　　则它比标准球重；如果是5号，则它比标准球轻。
　　　　　　　　第三次将1号放在左边，2号放在右边。
　　　　　　　　　　1.这次不可能右重。
　　　　　　　　　　2.如果平衡则5号是坏球且比标准球轻；
　　　　　　　　　　3.如果左重则1号是坏球且比标准球重；

B2层发表时间: 04-01-02 12:00

回复: afan271314 [afan271314]

论坛用户

怎么和绕口令一样啊晕了

B3层发表时间: 04-01-02 12:18

回复: boby [boby]

论坛用户

说的很对呀

B4层发表时间: 04-01-02 13:26

回复: wan0000 [wan0000]

论坛用户

呵呵
看看我的想法对吗？？
任意取4个放左边，4个放右边！！
1。如果一样重，则在剩余的4个里面！！
1。把这4个编号1 2 3 4
1 2 比较相等在比较1 3
不等把重的与3比较
2。不等的话，把重的4个编号 1 2 3 4 轻的 5 6 7 8，其余9 10 11 12！！
比较 1 5 6 和 7 8 9
1。相等则2 3 4 里有1个重的
2。1 5 6 重则1是重的或者5 6里有1轻比较5 6 相等 1号轻不等则重的是特别的
3. 1 5 6 轻则5 6里有1轻的比较5 6 轻的为特别的

B5层发表时间: 04-01-02 14:06

回复: wan0000 [wan0000]

论坛用户

286 老兄
你自己做的还是以前见过类似的？？

B6层发表时间: 04-01-02 14:09