带有扭曲的经典假币拼图
Classic Counterfeit coin puzzle with a twist
这个问题类似于经典的硬币搜索，寻找一枚重量比 x 枚硬币轻但硬币数量可能是假的硬币的扭曲。真币的重量都一样，假币的重量也一样。假币比真币轻
我要解决的问题的区别在于最多有 2 个假币（即可能没有假币、1 个假币或 2 个假币）。
我的尝试示例：
我在这个问题的早期尝试是弄清楚如何找到假硬币，当 x = 9 # of coins 时，但是你最多只能使用体重秤 6 次来弄清楚。
我首先将 x = 9 个硬币分成 3 个一组，然后比较这些组以检查是否相等（如果所有组 = 没有假币，因为最多可能有 2 个假币，并且至少有 0 个假硬币。）然后从那里检查第 1 组与第 2 组的不平等性，然后再次检查第 1 组与第 3 组的不平等性。第 1,2 组或第 3 组中可能存在 2 个假币，而另一种可能存在1 枚假硬币，每组分为 2 组，例如组 1,2、1,3 或 2,3。考虑到这些情况，我进行了比较，从而将组的比较分为三部分，直到我找到最后几个硬币并找到假币。
问题是：
在一堆硬币中，其中 x 个硬币的数量为“>= 3”，我将如何在确保称重次数为 O(log base 2 of (n)) 的同时找到假硬币.我如何找到一个通用公式来计算从 x 数量的硬币中找到最多 2 个假币所需的称重次数。
当我可以考虑所有情况并以较慢的速度比较每个情况时，编程就很容易了。然而，考虑到称重的次数必须为 O(log base 2 (n))，这会变得更加困难。我考虑过使用硬币的数量来区分如何进行比较，例如检查 x 数量的硬币是奇数还是偶数，然后决定如何进行比较。如果是奇数，将x-1分成3组，将最后一个硬币放入第四组，然后继续向下比较，最终找到假币，如果有的话。我还考虑过将 100 个硬币分成 33 个，然后比较这 3 个组，然后去掉 1/3 的硬币和 运行 比较剩下的 66 个。我仍然无法解决如何设计一个通用算法程序来找到假硬币，然后如何找到一个通用公式来比较以 log base 2 (n) 为底数的加权次数。
即使 n = prime/odd 数字，也很难在适用于任何 n >= 3 的一般程序中拆分这些硬币并检查重量。
为了澄清，我需要帮助来弄清楚 if/how 我之前的 attempt/example 可以用来创建一个通用的比较算法，该算法将适用于 x>=3 的任意数量的硬币，而称重次数为O(log base 2 (n)).
由于 O(log_2 n) 与任何基数 b>1 的 O(log_b n) 相同，因此用户 @n.1.8e9 在评论中建议的递归分解为三分之一符合该要求。 prime/odd个数字就不用考虑了，只要我们能用一定的称重次数解出一些指定的一定数量的硬币即可。
在这里，假设 3 个硬币是我们的基本情况。在对所有 3 对进行称重后（从技术上讲，我们可以称重 2 次），我们将确切知道这 3 枚硬币中哪一枚是轻的（如果有的话）。因此，如果我们将一堆 11 枚硬币分成三分之一，每枚 3 枚，我们可以拿走剩下的 2 枚硬币，从其他堆中借任何其他硬币，进行 3 次称重，然后丢弃剩下的 2 枚硬币，因为我们知道它们的状态。只要有 O(log n) 个分裂阶段，处理剩余部分就不会影响渐近。
证明中唯一复杂的部分是，在第一步之后，我们从“0、1 或 2 个假货”问题转向两个 'exactly 1 fake' 子问题或“1 或 2 个假货”子问题.假设您知道 1 + log_3 n 权重的原始 'exactly 1 fake' 问题的解决方案，证明应该看起来非常相似。
'at most 2 fake'和'1或2个假货'的程序是一样的。给定 n 个硬币，我们将它们分成三组 floor(n/3) 个硬币（并像上面那样处理任何剩余的硬币）。如果 n <= 3，停止并执行所有称量。否则，给定桩 A、B 和 C，执行 3 对称重 (A, B)、(A, C) 和 (B, C)。
如果它们的重量都相同 (A=B=C)，则没有假币。
如果一堆不同，有两种情况：单堆比其他两堆轻或重。
如果它更轻（例如，A < B，A < C，并且 B = C），那么 A 堆正好有 1 或 2 个假硬币，我们有一个关于 n/3 个硬币的问题实例（丢弃 B 堆和 C 堆）。
如果异常值较重（例如，A = B，A < C，且 B < C），则 A 堆和 B 堆各有一枚假币，这就是标准的假币问题。
要证明称重次数的界限，您可能需要使用归纳法。每个递归层级最多需要6次称重，所以可能剩余最多2个假币时需要称重次数的上限公式为T(n) = max(T(n/3), 2 * (1 + log_3(n/3))) + 6，其中1 + log_3 (n/3)项为标准上限用完美的策略在 n/3 个硬币中找到一个轻硬币（我们在所有分区中取整数）。
这个问题类似于经典的硬币搜索，寻找一枚重量比 x 枚硬币轻但硬币数量可能是假的硬币的扭曲。真币的重量都一样，假币的重量也一样。假币比真币轻
我要解决的问题的区别在于最多有 2 个假币（即可能没有假币、1 个假币或 2 个假币）。
我的尝试示例： 我在这个问题的早期尝试是弄清楚如何找到假硬币，当 x = 9 # of coins 时，但是你最多只能使用体重秤 6 次来弄清楚。
我首先将 x = 9 个硬币分成 3 个一组，然后比较这些组以检查是否相等（如果所有组 = 没有假币，因为最多可能有 2 个假币，并且至少有 0 个假硬币。）然后从那里检查第 1 组与第 2 组的不平等性，然后再次检查第 1 组与第 3 组的不平等性。第 1,2 组或第 3 组中可能存在 2 个假币，而另一种可能存在1 枚假硬币，每组分为 2 组，例如组 1,2、1,3 或 2,3。考虑到这些情况，我进行了比较，从而将组的比较分为三部分，直到我找到最后几个硬币并找到假币。
问题是：
在一堆硬币中，其中 x 个硬币的数量为“>= 3”，我将如何在确保称重次数为 O(log base 2 of (n)) 的同时找到假硬币.我如何找到一个通用公式来计算从 x 数量的硬币中找到最多 2 个假币所需的称重次数。
当我可以考虑所有情况并以较慢的速度比较每个情况时，编程就很容易了。然而，考虑到称重的次数必须为 O(log base 2 (n))，这会变得更加困难。我考虑过使用硬币的数量来区分如何进行比较，例如检查 x 数量的硬币是奇数还是偶数，然后决定如何进行比较。如果是奇数，将x-1分成3组，将最后一个硬币放入第四组，然后继续向下比较，最终找到假币，如果有的话。我还考虑过将 100 个硬币分成 33 个，然后比较这 3 个组，然后去掉 1/3 的硬币和 运行 比较剩下的 66 个。我仍然无法解决如何设计一个通用算法程序来找到假硬币，然后如何找到一个通用公式来比较以 log base 2 (n) 为底数的加权次数。
即使 n = prime/odd 数字，也很难在适用于任何 n >= 3 的一般程序中拆分这些硬币并检查重量。
为了澄清，我需要帮助来弄清楚 if/how 我之前的 attempt/example 可以用来创建一个通用的比较算法，该算法将适用于 x>=3 的任意数量的硬币，而称重次数为O(log base 2 (n)).
由于 O(log_2 n) 与任何基数 b>1 的 O(log_b n) 相同，因此用户 @n.1.8e9 在评论中建议的递归分解为三分之一符合该要求。 prime/odd个数字就不用考虑了，只要我们能用一定的称重次数解出一些指定的一定数量的硬币即可。
在这里，假设 3 个硬币是我们的基本情况。在对所有 3 对进行称重后（从技术上讲，我们可以称重 2 次），我们将确切知道这 3 枚硬币中哪一枚是轻的（如果有的话）。因此，如果我们将一堆 11 枚硬币分成三分之一，每枚 3 枚，我们可以拿走剩下的 2 枚硬币，从其他堆中借任何其他硬币，进行 3 次称重，然后丢弃剩下的 2 枚硬币，因为我们知道它们的状态。只要有 O(log n) 个分裂阶段，处理剩余部分就不会影响渐近。
证明中唯一复杂的部分是，在第一步之后，我们从“0、1 或 2 个假货”问题转向两个 'exactly 1 fake' 子问题或“1 或 2 个假货”子问题.假设您知道 1 + log_3 n 权重的原始 'exactly 1 fake' 问题的解决方案，证明应该看起来非常相似。
'at most 2 fake'和'1或2个假货'的程序是一样的。给定 n 个硬币，我们将它们分成三组 floor(n/3) 个硬币（并像上面那样处理任何剩余的硬币）。如果 n <= 3，停止并执行所有称量。否则，给定桩 A、B 和 C，执行 3 对称重 (A, B)、(A, C) 和 (B, C)。
如果它们的重量都相同 (A=B=C)，则没有假币。
如果一堆不同，有两种情况：单堆比其他两堆轻或重。
如果它更轻（例如，A < B，A < C，并且 B = C），那么 A 堆正好有 1 或 2 个假硬币，我们有一个关于 n/3 个硬币的问题实例（丢弃 B 堆和 C 堆）。
如果异常值较重（例如，A = B，A < C，且 B < C），则 A 堆和 B 堆各有一枚假币，这就是标准的假币问题。
要证明称重次数的界限，您可能需要使用归纳法。每个递归层级最多需要6次称重，所以可能剩余最多2个假币时需要称重次数的上限公式为T(n) = max(T(n/3), 2 * (1 + log_3(n/3))) + 6，其中1 + log_3 (n/3)项为标准上限用完美的策略在 n/3 个硬币中找到一个轻硬币（我们在所有分区中取整数）。