分治法生活中应用举例?

生活中用分治法解决问题的案例如下:

找出伪币

给你一个装有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组硬币的重量。假如两组硬币重量相等,则可以判断伪币不存在。假如两组硬币重量不相等,则存在伪币,并且可以判断它位于较轻的那一组硬币中。

最后,在第三步中,用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在,则第三步非常简单。无论A组还是B组中有伪币,都可以推断这1 6个硬币中存在伪币。因此,仅仅通过一次重量的比较,就可以判断伪币是否存在。

假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币,那么不能判断出它是否就是伪币。在一个小问题中,通过将一个硬币分别与其他两个硬币比较,最多比较两次就可以找到伪币。

这样16硬币的问题就被分为两个8硬币(A组和B组)的问题。通过比较这两组硬币的重量,可以判断伪币是否存在。如果没有伪币,则算法终止。否则继续划分这两组硬币来寻找伪币。假设B是轻的那一组,因此再把它分成两组,每组有4个硬币。

称其中一组为B1,另一组为B2。比较这两组,肯定有一组轻一些。如果B1轻,则伪币在B1中,再将B1又分成两组,每组有两个硬币,称其中一组为B1a,另一组为B1b。比较这两组,可以得到一个较轻的组。

由于这个组只有两个硬币,因此不必再细分。比较组中两个硬币的重量,可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。