主题:伪造硬币问题
快乐至诚
[专家分:0] 发布于 2010-05-11 13:36:00
给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法,并计算其时间复杂度。
回复列表 (共2个回复)
沙发
alweeq86 [专家分:1170] 发布于 2010-05-11 15:16:00
0. 把硬币尽量等量分成三份,如果有1份不同就用数量相同的比较重量,如果3份重量相同就随便选2份,称量结果:
1. 2份数量相同的硬币质量相同,则假币在另一份硬币里,不管另一份硬币数量是否与前面相同;
2. 2份数量相同的硬币质量不同,则假币(前提假币重量低)在质量低的一堆里;
3. 把有问题的一堆硬币GOTO步骤0
板凳
雪光风剑 [专家分:27190] 发布于 2010-05-11 19:23:00
代码网上有很多
我来回复