分而治之算法的例子：寻找伪造的货币

我们会给你一袋16枚硬币。
16枚硬币中的一枚是伪造的，伪造的硬币比真币更轻。
你的任务是找到这个伪造的硬币。
为了帮助您完成此任务，您将获得一种可用于比较两组硬币重量的仪器。使用此设备，您可以知道两组硬币是否具有相同的重量。
比较硬币1和硬币2的重量。
当硬币1比硬币2轻时，硬币1被锻造，当硬币2比硬币1轻时，硬币2被锻造。
任务完成了。
如果两枚硬币具有相同的重量，则比较硬币3和硬币4。
同样，如果货币很轻，找到伪造货币的任务就完成了。
如果两枚硬币具有相同的重量，继续比较硬币5和硬币6。
通过这种方式，伪造货币的存在可以通过多达八次比较来确定，并且可以找到伪造的货币。
另一种方法是使用分裂和征服方法。
如果你认为16个硬币的例子是一个大问题。
第一步是将问题分成两个较小的问题。
随机选择8个硬币作为第一组，剩余的8个硬币作为第二组称为B组。
以这种方式，解决了将十六个硬币分成两个八个硬币的问题。
第二步是确定A组和B组是否有任何假币。
该设备可用于比较A组和B组硬币的重量。
如果两个硬币组具有相同的重量，则可以确定没有伪造的货币。
如果两组不具有相同的重量，则可以确定存在伪造的硬币并且它是较轻的组硬币。
最后，在第三步中，第二步的结果用于获得对硬币的原始16个问题的答案。
如果只考虑货币，第三步非常容易。
如果您在A组或B组中有假币，您可以猜测这16枚硬币都有假币。
因此，可以仅通过重量比较来确定伪造货币是否存在。
现在，您需要识别这种相反的货币。
两个或三个硬币是无法细分的小问题。
如果只有一种货币，则无法确定它是否是假币。
在小问题上，可以发现假硬币比较一枚硬币和另外两枚硬币。
因此，16个硬币的问题可以分为两个8个硬币（A组和B组）。
通过比较两组硬币的权重，可以确定是否存在伪造货币。
如果没有伪造硬币，则算法结束。
否则，继续拆分两组硬币以找到假币。
假设B是最轻的组，因此将其分为两组。
一组称为B1，另一组称为B2。
如果比较这两组，应该有一个较轻的组。
如果B1很轻，则伪造的硬币在B1中，然后B1被分成两组。每组有两个硬币，其中一个叫做B1a，另一个叫做B1b。
通过比较这两组，您可以获得更轻的组。
这组中只有两个硬币，因此无需分割它们。
通过比较组中两种货币的权重，您可以快速查看哪种货币更轻。
最轻的硬币是您正在寻找的假币。