回 帖 发 新 帖 刷新版面

主题:伪造硬币问题

给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法,并计算其时间复杂度。

回复列表 (共2个回复)

沙发

0.  把硬币尽量等量分成三份,如果有1份不同就用数量相同的比较重量,如果3份重量相同就随便选2份,称量结果:
1.  2份数量相同的硬币质量相同,则假币在另一份硬币里,不管另一份硬币数量是否与前面相同;
2.  2份数量相同的硬币质量不同,则假币(前提假币重量低)在质量低的一堆里;
3.  把有问题的一堆硬币GOTO步骤0

板凳

代码网上有很多

我来回复

您尚未登录,请登录后再回复。点此登录或注册