分治算法找出伪币给你一个装有16个硬币的袋子

16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些

你的任务是找出这个伪造的硬币

为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同

比较硬币1与硬币2的重量

假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的

这样就完成了任务

假如两硬币重量相等，则比较硬币3和硬币4

同样，假如有一个硬币轻一些，则寻找伪币的任务完成

假如两硬币重量相等，则继续比较硬币5和硬币6

按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币

另外一种方法就是利用分而治之方法

假如把16硬币的例子看成一个大的问题

第一步，把这一问题分成两个小问题

随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组

这样，就把16个硬币的问题分成两个8硬币的问题来解决

第二步，判断A和B组中是否有伪币

可以利用仪器来比较A组硬币和B组硬币的重量

假如两组硬币重量相等，则可以判断伪币不存在

假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中

最后，在第三步中，用第二步的结果得出原先16个硬币问题的答案

若仅仅判断硬币是否存在，则第三步非常简单

无论A组还是B组中有伪币，都可以推断这16个硬币中存在伪币

因此，仅仅通过一次重量的比较，就可以判断伪币是否存在

假设需要识别出这一伪币

把两个或三个硬币的情况作为不可再分的小问题

注意如果只有一个硬币，那么不能判断出它是否就是伪币

在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币

这样，16硬币的问题就被分为两个8硬币（A组和B组）的问题

通过比较这两组硬币的重量，可以判断伪币是否存在

如果没有伪币，则算法终止

否则，继续划分这两组硬币来寻找伪币

假设B是轻的那一组，因此再把它分成两组，每组有4个硬币

称其中一组为B1，另一组为B2

比较这两组，肯定有一组轻一些

如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b

比较这两组，可以得到一个较轻的组

由于这个组只有两个硬币，因此不必再细分

比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些

较轻的硬币就是所要找的伪币

以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。