有100个同样的硬币,其中一个是假币,比真币重一些。你可以使用一个天平来比较硬币的重量。你最少需要称几次才能造出假币?给出答案和解决思路
时间: 2024-05-25 18:19:22 浏览: 9
答案是两次。
解决思路如下:
- 第一次称:将硬币分成三堆,每堆30个硬币,剩下10个硬币不用管。分别称量第一堆和第二堆硬币,如果两堆硬币的重量相等,则假币在第三堆中,否则假币在较重的那堆中。
- 第二次称:将第三堆硬币分成三堆,每堆10个硬币。分别称量第一堆和第二堆硬币,如果两堆硬币的重量相等,则假币在第三堆中,否则假币就是比较重的那堆中的一个硬币。
通过这种方法,最少只需要称两次就能找出假币。
相关问题
一个袋子里有30个硬币,其中一枚是假币,并且假币和真币一模一样,肉眼很难分辨,目前只知道假币比真币重量轻一点,设计合理算法如何区分出假币
可以采用分治策略来找出假币。具体步骤如下:
1. 将硬币分成三组,每组10个硬币。
2. 将其中两组放在天平两端进行称重,如果两端重量相等,则假币在第三组中,否则假币在较轻的一组中。
3. 对于包含假币的那组硬币,将其分成三组,每组3个硬币。
4. 将其中两组放在天平两端进行称重,如果两端重量相等,则假币在第三组中,否则假币在较轻的一组中。
5. 对于包含假币的那组硬币,将其分成三组,每组1个硬币。
6. 将其中两组放在天平两端进行称重,如果两端重量相等,则假币就是剩下那个硬币,否则假币就是较轻的那个硬币。
--相关问题--:
1. 如果假币比真币重一点怎么办?
2. 如果
有n枚硬币,其中有一枚硬币是假币,且假币的重量较轻,通过一架天平找出假币。比较次数最少。
可以采用二分法的思想,将n枚硬币分成两组,分别放在天平的两端,比较两端的重量,如果两端重量相等,则假币在剩下的n/2枚硬币中,否则假币在较轻的一组中。然后再将较轻的一组硬币继续分成两组,重复上述步骤,直到找出假币。这样比较的次数最少,为log2(n)次。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)