分治算法

分治算法

1. 算法介绍

分治法就是“分而治之”，就是把一个复杂的问题分成两个或者更多的相同或者相似的子问题，再把子问题分解成更小的字问题......直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并，分治法是很多高效算法的基础，比如：排序算法（快速排序，归并排序），傅里叶变换（快速傅里叶变换）

分治算法求解的经典问题：二分搜索、大整数乘法、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔问题

2. 算法步骤

分治法在每一层递归上都有三个步骤

• 分解：将原问题分解成若干个规模较小，相互独立，与原问题形式相同的子问题
• 解决：若子问题规模较小而容易被解决则直接解决，否则递归的解决各个子问题
• 合并：将各个子问题的解合并为原问题的解

3. 算法实践-汉诺塔问题

3.1 汉诺塔的传说

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，

假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31557600秒，计算一下：

18446744073709511615秒

这表明移完这些金片需要5845.42亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.42亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

3.2 思路分析

• 如果是有一个盘，从一塔移动到三塔（若 n >= 2，均将其看作为两个盘：1.最下面的盘 2.上面的盘）
• 先把一塔除了最下面的盘移动到二塔
• 把一塔最下边的盘 移动到三塔
• 把二塔所有的盘移动到三塔

4. 汉诺塔问题代码实现

package cn.imut;

public class Hanoitower {

    public static void main(String[] args) {
        hanoiTower(3,"一塔","二塔","三塔");
    }

    //汉诺塔移动
    public static void hanoiTower(int num, String a, String b, String c) {
        //若只有一个盘
        if(num == 1) {
            System.out.println("第1个盘从 " + a + "->" + c);
        }else {
            //将一塔除了最下面的盘移动到二塔（移动过程中会用到三塔）
            hanoiTower(num - 1, a, c, b);
            //将一塔最下面的盘移动到三塔
            System.out.println("第" + num + "个盘从 " + a + "->" + c);
            //把二塔下所有的盘移动到三塔
            hanoiTower(num - 1, b, a, c);
        }
    }
}

分治算法

原文：https://www.cnblogs.com/yfyyy/p/12775244.html