假设在一堆硬币中混杂着一枚假币,而且已知假币比真币重。假币问题研究的是如何用一架天平将假硬币找出来。现给定31枚硬币,其中有一枚假币,采用二分的思路,最多需要称( )次可以找出假币。
时间: 2024-03-15 21:42:52 浏览: 19
采用二分的思路,最多需要称 4 次可以找出假币。
首先将硬币分成两堆,一堆放 10 枚,另一堆放 21 枚。然后将这两堆硬币分别放在天平的两端,比较它们的重量。如果两堆重量相等,说明假币在剩下的那一堆中。这样就排除了一半的硬币。
接下来,将剩下的 21 枚硬币分成两堆,一堆放 10 枚,另一堆放 11 枚。同样地,将它们分别放在天平的两端,比较它们的重量。如果两堆重量相等,说明假币在剩下的那一堆中。这样又排除了一半的硬币。
接下来,将剩下的 11 枚硬币分成两堆,一堆放 5 枚,另一堆放 6 枚。同样地,将它们分别放在天平的两端,比较它们的重量。如果两堆重量相等,说明假币在剩下的那一堆中。这样又排除了一半的硬币。
最后,将剩下的 6 枚硬币分成两堆,一堆放 3 枚,另一堆放 3 枚。同样地,将它们分别放在天平的两端,比较它们的重量。如果两堆重量相等,说明剩下的一枚硬币就是假币;否则,假币就在天平较重的那一端。
相关问题
假设有120个硬币,其中有一枚假币,且已知假币比真币重。现有一台天平,请设计一个算法,怎么在最坏情况下用最少次数找出假币。写出寻找过程。
可以采用二分法的思想,将120个硬币分成两组,分别放在天平的两端。如果天平平衡,则说明假币在剩余的60枚硬币中,否则假币在天平较重的一端。
接下来,将天平较重的一端的60枚硬币再分成两组,放在天平的两端进行比较。如果天平平衡,则说明假币在剩余的30枚硬币中,否则假币在天平较重的一端。
重复以上步骤,每次都将硬币数量减半,直到最后只剩下一枚硬币,此时这枚硬币就是假币。
在最坏情况下,假币恰好在最后一次比较时被找出,因此需要进行7次比较。
寻找过程如下:
1. 将120枚硬币分成两组,放在天平两端进行比较。
2. 如果天平平衡,则假币在剩余的60枚硬币中,否则假币在天平较重的一端。
3. 将天平较重的一端的60枚硬币分成两组,放在天平两端进行比较。
4. 如果天平平衡,则假币在剩余的30枚硬币中,否则假币在天平较重的一端。
5. 将天平较重的一端的30枚硬币分成两组,放在天平两端进行比较。
6. 如果天平平衡,则假币在剩余的15枚硬币中,否则假币在天平较重的一端。
7. 将天平较重的一端的15枚硬币分成两组,放在天平两端进行比较。
8. 如果天平平衡,则假币在剩余的7枚硬币中,否则假币在天平较重的一端。
9. 将天平较重的一端的7枚硬币分成两组,放在天平两端进行比较。
10. 如果天平平衡,则假币在剩余的3枚硬币中,否则假币在天平较重的一端。
11. 将天平较重的一端的3枚硬币分成两组,放在天平两端进行比较。
12. 如果天平平衡,则假币在剩余的1枚硬币中,否则假币就是天平较重的那枚硬币。
有n枚硬币,其中有一枚硬币是假币,且假币的重量较轻,通过一架天平找出假币。比较次数最少。
可以采用二分法的思想,将n枚硬币分成两组,分别放在天平的两端,比较两端的重量,如果两端重量相等,则假币在剩下的n/2枚硬币中,否则假币在较轻的一组中。然后再将较轻的一组硬币继续分成两组,重复上述步骤,直到找出假币。这样比较的次数最少,为log2(n)次。