算法设计与分析 举例.doc

例3-7 [找出伪币] 给你一个装有16个硬币的袋子16个硬币中有一个是伪的并且那个伪造的硬币比真的硬币要轻一些你的任务是找出这个伪造的硬币为了帮助你完成这个任务将提供一台可用来比较两组硬币重量的仪器利用这台仪器可以知道两组硬币的重量是否相同 比较硬币1与硬币2的重量假如硬币1比硬币2轻则硬币1是伪造的假如硬币2比硬币1轻则硬币2是伪造的这样就完成了任务假如两硬币重量相等则比较硬币3和硬币4同样假