算法项目问题

Question

要求你写一份关于以下算法问题的报告：这道题要求你在一组真币中找出一个假币。这枚假硬币之所以能被找到，是因为它和其余的真硬币的重量不一样。不是轻了就是重了，只是你事先不知道。你要做决定的唯一方法是一个经典的带有两个托盘的天平秤。你可以把一个或多个硬币放在一个托盘上，一个相似的数字放在另一个托盘上，并确定哪个托盘有较轻的一堆。例如，如果你只有三个硬币，那么拿硬币1和硬币2称重。如果天平平衡，那么硬币3一定是奇数。如果刻度不平衡，那么比较硬币1和硬币3。如果它们平衡，那么硬币2一定是奇数，而如果它们不平衡，那么硬币1一定是奇数。问题的关键是用最少的比较次数找到假币。3个硬币最少的比较是多少？为了4个硬币？为了5个硬币？为了12个硬币？对于N，任意数量的硬币？这个问题传统上用12枚硬币来陈述。

在报表中包括以下内容：

• 理解问题：描述您如何处理问题和示例，以加深理解。
• 了解算法过程如何解决问题：描述解决问题的一个或多个通用方法，包括您是如何踏进门的。
• 制定算法：更详细地描述您的算法。
• 评估您的算法的准确性及其作为解决其他问题的工具的潜力：描述为什么您认为您的算法解决方案是正确的，以及为什么它可能比您的其他想法更好。

问题：

在一组真硬币中找出一枚假硬币我们被告知有12枚硬币我们需要确定哪一枚是假的。我们也得到了一个更深的洞察力关于假硬币，即这枚硬币将不是相同的重量，其他的。这将向我们表明硬币是重的还是轻的，这是我们必须确定的。最后，我们意识到，我们将不得不作出这一决定与2托盘秤。

解决方案：

null

如果平衡，则硬币6为假，否则硬币5为假lgn=12=4

Answer 1

解决问题的一个算法是遵循以下步骤：

>

将堆栈分成两半。

再劈开一半放在天平上。

然后，你可以找到好的硬币使用2个比较。

因此，假设您有n个硬币，您需要int(log2(n))+2比较才能找到它。

我没有检查这种方法的最优性，但它必须至少接近最优性（最多1或2个额外比较）。