这是一个创建于 3476 天前的主题，其中的信息可能已经有所发展或是发生改变。
12 枚金币外观相同，正常金币重量是标准一致的，假金币只是重量异常，天平没有砝码，如何只称 3 次，找出假金币以及它比正常金币轻了还是重了。
这个问题，网上随便一搜就能找到答案，只是金币换成了小球或别的什么。
有没有用编程作一个通用的解决办法？例如 120 枚中 1 枚假的，称 5 次能不能找出假金币的轻重等
试着用穷举法做了一个，发现计算量有点大。
求思路或答案。
这个问题，网上随便一搜就能找到答案，只是金币换成了小球或别的什么。
有没有用编程作一个通用的解决办法？例如 120 枚中 1 枚假的，称 5 次能不能找出假金币的轻重等
试着用穷举法做了一个，发现计算量有点大。
求思路或答案。
第 1 条附言 2016-04-04 14:49:18 +08:00
还是写个答案吧，有些人不认真读题了。。。
这种格式的答案， 楼主穷举了一下，有 304 个，大致就是按照按照 21 楼链接中的方法矩阵乘法。但这个按照算法，称 5 次时，数量已经大了很多，现在还没算出来 120 枚称 5 次时的答案。楼主更感兴趣的怎么用编程方法，解决这来问题。
一 01, 02, 03, 04 09, 10, 11, 12
二 01, 05, 06, 09 03, 04, 08, 12
三 02, 05, 07, 10 01, 04, 06, 09
结果清单如下
L,O,R 分别表示天平的结果:左重,平衡,右重，
L L R 01 重
L O L 02 重
L R O 03 重
L R R 04 重
O L L 05 重
O L R 06 重
O O L 07 重
O R O 08 重
R L R 09 重
R O L 10 重
R O O 11 重
R R O 12 重
O O O 无
R R L 01 轻
R O R 02 轻
R L O 03 轻
R L L 04 轻
O R R 05 轻
O R L 06 轻
O O R 07 轻
O L O 08 轻
L R L 09 轻
L O R 10 轻
L O O 11 轻
L L O 12 轻
这种格式的答案， 楼主穷举了一下，有 304 个，大致就是按照按照 21 楼链接中的方法矩阵乘法。但这个按照算法，称 5 次时，数量已经大了很多，现在还没算出来 120 枚称 5 次时的答案。楼主更感兴趣的怎么用编程方法，解决这来问题。
一 01, 02, 03, 04 09, 10, 11, 12
二 01, 05, 06, 09 03, 04, 08, 12
三 02, 05, 07, 10 01, 04, 06, 09
结果清单如下
L,O,R 分别表示天平的结果:左重,平衡,右重，
L L R 01 重
L O L 02 重
L R O 03 重
L R R 04 重
O L L 05 重
O L R 06 重
O O L 07 重
O R O 08 重
R L R 09 重
R O L 10 重
R O O 11 重
R R O 12 重
O O O 无
R R L 01 轻
R O R 02 轻
R L O 03 轻
R L L 04 轻
O R R 05 轻
O R L 06 轻
O O R 07 轻
O L O 08 轻
L R L 09 轻
L O R 10 轻
L O O 11 轻
L L O 12 轻
 | 1 hinate 2016-04-04 12:25:34 +08:00 2 分 |
 | 2 vietor 2016-04-04 12:25:45 +08:00 via Android 6,3,1 |
 | 3 zhjits 2016-04-04 12:28:55 +08:00  3 每次等分三份，称其中两份 |
 | 4 ncdx2009 OP |
 | 5 smallfount 2016-04-04 12:34:58 +08:00 在不知道轻还是重的情况下 2 分不能解决...因为第一次称好了完全不知道到底哪个是标准的... 所以至少也得是 3 分.... |
 | 8 Fleeting 2016-04-04 12:37:13 +08:00 via Android 3 分吧 |
 | 9 sciooga 2016-04-04 12:55:33 +08:00 这题很有趣，小学的时候我爸喜欢给我出这种益智题，当时拿到这道题真的没头绪，晚上睡觉后闭上眼想了半个小时想出来激动得... 给几个提示： 1.给每个硬币编号。 2.硬币间可以交换位置，看天平重轻方向是否改变。 3.原题关键字是“ 12 个乒乓球特征相同 其中只有一个重量异常”搜一搜就有答案了。 |
 | 10 srlp 2016-04-04 12:56:39 +08:00 一个天平可以比较三份数目相等的硬币，楼主按照这个思路就行 |
 | 11 233 2016-04-04 12:57:55 +08:00 很经典的题目，从小学做到工作。关键的一步就是在第二次测量时要重新分组 |
 | 12 allan888 2016-04-04 13:17:36 +08:00 3 这个之前看过，我说详细点好了，假设硬币叫做 1-12 ： a. 分 3 份，分别是 1-4 ， 5-8 ， 9-12 ，称 1-4 和 9-8 ，平的话就在 9-12 ，没啥好说的。 b.假设 1 ， 2 ， 3 ， 4 轻， 5 ， 6 ， 7 ， 8 重，那么确定 9 ， 10 ， 11 ， 12 是真的硬币。 c.拿出 1 和 3 个 9-12 里面的，比如 1 ， 9 ， 10 ， 11 ，这里面只有 1 需要确定是不是假的。 d.拿出 1 ， 9 ， 10 ， 11 和 2 ， 3 ， 4 ， 5 称，如果平的话就是 6 ， 7 ， 8 有问题，不用说了。 e.如果 1 ， 9 ， 10 ， 11 轻，那么 1 ， 5 有问题，因为 6 ， 7 ， 8 已经知道没问题， 2 ， 3 ， 4 有问题的话现在 2 ， 3 ， 4 从左边换到了右边，右边应该轻才对， 1 ， 5 有问题的话把 1 和一个真币称一下就知道谁是假币了。 f.如果 1 ， 9 ， 10 ， 11 重，那么 2 ， 3 ， 4 有问题，因为 1 ， 5 有问题的话 1 ， 5 都没有换边，轻重不会变，其实就是 2 ， 3 ， 4 换了位置导致轻重关系变了，到这步的话确定假币是偏轻的。 2 ， 3 ， 4 里面， 2 和 3 称一下轻的是假的，平的话 4 是假的。 |
 | 13 amet 2016-04-04 13:34:10 +08:00 1 信息论的题，刚学 称重可能得到三种结果:一边轻、一边重、两边平衡 H_1(x)=log(2)(3) 一共有 N 个球，假球可能轻可能重， N*2 H_2(x)=log(2)(2N) 需要最少次数在( H_1(x)/H_2(x) , H_1(x)/H_2(x)+1 )之间取整数 120 个球即 N=120 H_1(x)/H_2(x)=4.98869 …… 所以 5 次肯定可以 LaTeX 不熟，不会写对数，公式都是以 2 为底，将就看吧 |
 | 15 sigone 2016-04-04 13:46:08 +08:00 via Android 6/6 ， 3/3 ， 1/1 (1-1-1 排除法) 幼儿园水平水平 |
 | 16 steveshi 2016-04-04 13:48:40 +08:00 金田一做过这个题目…… |
 | 17 Xs0ul 2016-04-04 14:00:30 +08:00 @amet 按照你这里的理论， 3 次应该可以分 13 个球（ 3^3 > 13*2 ），然而我见到的题目全是 12 ，我相信不是出题者和做题者没有想到 13 的解法。事实上你不能保证每次获得的信息都是最好的（或者说是对于各种情况都是比较平均的），比如可能在某一步一边重留下的情况比较多，一样重留下的情况比较少。 |
 | 20 mimzy 2016-04-04 14:22:24 +08:00 via Android 只针对这道题的话 第一次看见是在这里 http://blog.csdn.net/pongba/archive/2008/06/13/2544933.aspx |
 | 21 luguozmy 2016-04-04 14:27:32 +08:00 https://en.wikipedia.org/wiki/Balance_puzzle https://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C 我记得这是以前初中的智力题, 不难的, 我家那个小弟弟认真想想就可以解出来 |
 | 22 loading 2016-04-04 14:28:07 +08:00 via Android 1 这一题不是考智商的，这是一个记忆题，因为这个题目已经烂大街了… |
| 25 ncdx2009 OP |
| 26 Xs0ul 2016-04-04 15:04:09 +08:00 @pimin 称球问题是指若在最多 (3^n-3)/2 个球中有一个特殊球的重量与众不同（不知道偏重还是偏轻），而其他球的重量全部相同，则用无砝码的天平称 n 次可以找出特殊球，并确定特殊球是偏轻还是偏重；如果有 (3^n-1)/2 个球，则同样可以保证找出特殊球，但不一定能确定特殊球是偏轻还是偏重 来自维基百科 https://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C @ncdx2009 楼主可以看看维基百科提到的矩阵解法 |
| OP @Xs0ul 目前是按照这个矩阵解法进行的编程练习, 这解法的数量增长太快了,12 枚称 3 次是 2 的 12 次方(4 位数) , 到 120 枚称 5 次是 2 的 120 次方(37 位数) 。 |
 | 28 kaizixyz 2016-04-04 17:27:51 +08:00 via iPad 12 个球有 1 个异常。可能性有 24 种。称相当于 3 进制。所以 3 位的编码就够了。理论上 13 个球应该也行啊。求大神来个 13 球版的 |
 | 29 RqPS6rhmP3Nyn3Tm 2016-04-04 19:09:32 +08:00 这不是很简单吗，二进制编码原理 |
 | 30 USCONAN 2016-04-04 19:25:01 +08:00 |
 | 31 malcolmyu 2016-04-04 21:09:02 +08:00 |
Select Language