Geek
脑力小体操 穿过不可能通过的洞
在不撕裂纸张,毁坏光盘的情况下,你能想出让光盘通过那个洞的方法吗?
关于之前“称假币”问题的变种,问题来自著名博客→
http://www.matrix67.com/blog/archives/6970#more-6970。
停更数年之后,人家又开始不定期写博客了……上面链接内有详细分析。
题目如下
今天的则是经典称量金币puzzle的变种(前段时间在某博客看到的。详见下期解答篇。敬请期待厚)。
已知有9枚金币,其中 1枚 是以铜为主的假币。为方便计,假设标准金币的质量在高精度范围内都一样。在经典情况下,如果给你一台三角天平(就是像跷跷板那种,童虎天秤座圣衣的造型),则称2次就必然能找出那枚假币(若你从来没听说过这个puzzle,不妨先思考一下这个问题)。
很多程序员估计都听说过fake-coin算法,那就是针对这一问题一般化的算法。
但是,注意了,这一次,我们不用机械三角天平。你所用的是“电子天平”,它不会直观地显示哪边重哪边轻,而是在全部称完后把每次的结果一并打印出来。当然正常来说,使用这种天平,我们可以称重一次就打印一次结果,但现在规定,在面对当下挑战任务的时候,你仅能打印一次。
也就是说,你没法根据第一次的反馈结果来设计第二次称量,必须事先规划出完整的称法。
好了,现在你能仅称2次就找到假币吗?
因为有朋友回复说太简单,脑子刚做完热身运动,答案就出来了。那再来个选作的:27枚金币中有1枚假币,用电子天平称3次找出来?
54d个:
把硬币从1-27编号,每9个硬币成A,B,C三个大组 ,每个大组中每三个硬币组成一个小组即 A.1 A.2 A.3, B.1 B.2 B.3, C.1 C.2 C.3 九个小组
1.第一次称A B两个大组,确定铜币在哪个大组
2.第二次把每个大组的第一和第二小组分别置于天枰两边, 即比较 A.1 B.1 C.1 三个小组 与 A.2 B.2 C.2 来确定位于哪个小组
3.第三次天枰两边分别放每个小组的第一位(1,4,7,… 22,25号硬币,共9枚) 与 每个小组第二位 (2,5,8 … 23, 26号共9枚硬币) 来确定铜币位于小组第几位
知道铜币位于哪个大组,哪个小组,小组第几位就能推算出铜币的位置
南郭小儿: