经典的假币谜题

Question

这个问题与经典的硬币搜索类似，搜索一枚重量比x枚硬币轻的假币，但可能是假币的硬币数量有所增加。真硬币的重量都一样，假硬币的重量也一样。假硬币比真硬币轻。

我试图解决的那个的区别是当最多有2个假币时（即可能有，没有假硬币，1个假硬币或2个假硬币）。

我尝试的例子：我在这个问题的早期部分的尝试是弄清楚如何找到假币（如果有的话），当x=9#硬币时，但是你最多只能使用重量秤6次来弄清楚。

我首先将x = 9个硬币分成3个一组，然后比较各组以检查是否相等(如果所有组都相等，则表示没有假硬币，因为最多可能有2个假硬币，至少有0个假硬币。)然后从那里开始检查组1与组2的不等式，并再次检查组1与组3的不等式。组1、2或3中有两个假硬币的可能性，以及诸如组1、2、1、3或2、3的两个组中每个组有一个假硬币的另一种可能性。考虑到这些情况，我进行了比较，从而将各组的比较分成三组，直到我找到最后的几个硬币并找到假硬币。

问题是 __________：

在一堆硬币中，硬币的x数量为“

当我可以考虑所有情况并以较慢的速度比较每个情况时，编程这很容易。然而，当考虑称重的次数必须是O（对数基数2（n））时，它会变得更加困难。我考虑过使用硬币的数量来区分如何进行比较，例如检查硬币的x数量是奇数还是偶数，然后决定如何比较。如果是奇数，将x-1分成3组，并将最后一枚硬币放入第四组，然后继续螺旋式比较，最终找到假币，如果有的话。我还考虑过把100个硬币分成33个，然后比较3组，然后去掉1/3的硬币，在左边66个进行比较。我仍然无法解决如何设计一个通用算法程序来找到假币，然后如何找到一个通用公式来比较加权到对数基数2（n）的次数。

即使当n =质数/奇数时，也很难用适用于任何数n的通用程序来分割这些硬币并检查重量

为了澄清，我需要帮助弄清楚我之前的尝试/示例是否/如何应用于创建通用比较算法，该算法适用于任何数量的硬币，其中x

Answer 1

因为O（log_2n）与O（log_bn）对于任何碱基b都是相同的

在这里，让3枚硬币作为我们的基本案例。在权衡了所有3对硬币后（技术上，我们可以通过2个称重来逃脱），我们将确切地知道这3枚硬币中的哪一枚是轻的，如果有的话。所以如果我们把一堆11枚硬币分成3枚的三分之一，我们可以拿走这2枚剩余的硬币，从其他一堆借用任何其他硬币，进行3次称重，然后丢弃这2枚剩余的硬币，因为我们知道它们的状态。只要有O（log n）分裂阶段，处理剩余的硬币不会影响渐近性。

证明的唯一复杂部分是，在第一步之后，我们从“0、1或2个假”问题转到两个“正好1个假”子问题或“1或2个子问题”。假设您知道使用＜code＞1 log_3n＜/code＞权值的原始“精确1假”问题的解决方案，那么证明应该相当相似。

“最多2个假货”和“1个或2个假货”的程序是一样的。给定n个硬币，我们将它们分成三组< code>floor(n/3)硬币(并像上面一样处理任何剩余的硬币)。如果n

如果它们的重量相同（A＝B＝C），就没有假硬币。

如果有一桩不一样，有两种情况：单桩比其他两桩轻或重。

如果它更轻（例如，A

如果异常值较重（例如，A=B，A

为了证明加权数的界限，您可能需要使用归纳法。每个递归级别最多需要6个权重，因此当可能剩余多达2个虚拟币时，所需权重数的上限公式是T（n）=max（T（n/3），2*（1log_3（n/3））6，其中1log_3（n/3）项是标准上限，具有完美的策略，可以在n/3硬币中找到一个光币（我们在所有部门中获得整数）。