汉诺塔

1.分治定义

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

1)分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题

2)解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

3)合并：将各个子问题的解合并为原问题的解。

if |P|≤n0

then return(ADHOC(P))

//将P分解为较小的子问题 P1 ,P2 ,…,Pk

for i←1 to k

do yi ← Divide-and-Conquer(Pi) 递归解决Pi

T ← MERGE(y1,y2,…,yk) 合并子问题

return(T)

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1
,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

2.汉诺塔定义

Ø汉诺塔的传说

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

假如每秒钟一次，共需多长时间呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

3.解决思路

Ø汉诺塔游戏的演示和思路分析:

1)如果是有一个盘， A->C

如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘

1)先把 最上面的盘 A->B

2)把最下边的盘 A->C

3)把B塔的所有盘 从 B->C

4.个人理解

把牌分为两部分，最下面一个，和上面的所有，先把最上面所有的（n-1）移动到b盘（借助c盘的帮助），再把最下面的一个移动到c盘，最后再把b盘上的所有移动到c盘（借助a盘的帮助），把规模为n的问题分为n-1,1，n-1的三个问题，递归基就是只有一个元素，那就把元素从a到c

5.代码讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
        solve(4,'a','b','c');
    }
    //n个塔借组b使他从a到c
    public static void solve(int n,char a,char b,char c){
        if (n==1){
            System.out.println("第1个盘从"+a+"到"+c);
        }else {
            solve(n-1,a,c,b);//吧最上面的pan全部移到b上
            System.out.println("第"+n+"个盘从"+a+"到"+c);//这个ac是指起点到终点，不是a点和c点
            solve(n-1,b,a,c);//再把b上的pan全部移到c上
        }

    }
}