算法洗脑系列（8篇）——第五篇 分治思想

  由于最近工作比较忙，好长时间都没有更新博客了，今天就分享下分治思想。

一： 思想

     有时候我们处理一个复杂的问题，可能此问题求解步骤非常杂，也可能是数据非常多，导致我们当时很难求出或者无法求出，古语有云：

步步为营，各个击破，这个思想在算法中称为分治思想，就是我们可以将该问题分解成若干个子问题，然后我们逐一解决子问题，最后将子问题

的答案组合成整个问题的答案。

二: 条件

     当然各个思想都有它的使用领域，所以玩这场分治游戏就要遵守它的游戏规则。

       ①   求解问题确实能够分解成若干个规模较小的子问题，并且这些子问题最后能够实现接近或者是O（1）时间求解。

       ②   各个子问题之间不能有依赖关系，并且这些子问题确实能够通过组合得到整个问题的解。

三：步骤

     通过上面对分治的说明，可以看到分治分三步走：

       ①  分解： 将问题分解成若干了小问题。

       ②  求解： O(1)的时间解决该子问题。

       ③  合并： 子问题逐一合并构成整个问题的解。

四：举例

      有n位选手参加羽毛球赛，比赛要进行n-1天，每位选手都要与其他每一个选手比赛一场并且每位选手每天都要比赛一场，请根据比赛要求

   排出选手的比赛日程表。

   思路：首先我们拿到问题要给自己打气，哈哈，因为日常的基本问题都跑不出我们所知道算法思想的范畴，此问题也包括在内。

           当n是8，16，32时，面对这么一个庞大的问题我们可能就崩溃了，因为我们实在无法求出来，此时我们就要想想是否可以分治一下。

           ①  就拿16个选手的比赛安排来说，需要比赛15天。

           ②  分成2个8位选手7天的比赛安排。

           ③  分为4个4位选手3天的比赛安排。

           ④  分为8个2位选手1天的比赛安排。

         相信2位选手1天的比赛安排大家都会吧，如图:

        然后退化到第三步即4位选手3天的比赛安排，如图：

        在图中可以看出:

          第一天：将1，2位和3，4位选手的日程合并。

          第二天，第三天：这两天的比赛安排其实可以发现规律的，整个表格可以划分四格，对角赋值。

程序代码如下：