n枚硬币。哪个是假的?
我们有 n 个硬币。其中一件是假的,是更重还是更轻(我们不知道)。我们有带 2 个盘子的秤。我们怎样才能在p步中获得假币呢?
你能帮我写一个这样的程序吗?不需要完整的计划,只需想法。
谢谢。
Possible Duplicate:
Algorithm to find minimum number of weighings required to find defective ball from a set of n balls
We have n coins. One of them is fake, which is heavier or lighter (we don't know). We have scales with 2 plates. How can we get the fake coin in p moves?
Can you give me a hand for writing such a program? No need a whole program, just ideas.
Thank you.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
这称为平衡谜题。请参阅Marcel Kołodziejczyk 的两盘平衡和广义假币问题< /em> 这个问题的概括。
This is known as Balance puzzle. See Marcel Kołodziejczyk’s Two-pan balance and generalized counterfeit coin problem for a generalization of this problem.
我记得对 n=12 和 13 的这个问题进行了求解,部分是手工求解,最后用程序求解。我不知道如何解决一般的 n...但我知道如何开始 - 通过考虑
n
的小值并通过手。我怀疑本质上有一些模式可以为此递归使用......但是您会发现用笔和纸发现小值(例如,n=4 到 7)比通过编码更容易发现它们。
I remember solving this for n=12 and 13, partly by hand and then with a program at the end. I don't know how I would solve it for a general n... but I know how I'd start - by considering small values of
n
and doing it by hand.I suspect there are essentially patterns that can be used recursively for this... but you'll find them much easier to discover with pen and paper for small values (n=4 to 7, for example) than by coding.
将硬币放在两侧,真币会相互平衡,假币会使秤朝任何一个方向移动。当天平不平衡时,您刚放的两枚硬币中的一枚是假的,用一枚真硬币试一试。
如果硬币是你收到的物品,那么你应该能够在程序中很容易地做到这一点。
Put coins on each side, the real ones will balance each other out, the fake will make the scale go either way. When the scales aren't balanced, one of the 2 you just put on is fake, try each against a real coin.
If the coins are objects you're handed, then you should be able to do that in a program quite easily.