漢諾塔問題是一個經(jīng)典問題。

題意理解：有A,B,C三個柱子，將A柱子上的N個盤子（從小到大排列）移到C柱子上，每次只允許移動一個盤子，并且保證每個柱子上的盤子的排列都是從小到大。

（圖片源自百度圖片）

分析：由題意可知，如果要將A上的盤子移動到C，那么肯定需要借助C。

首先將A上的盤子從上到下依次編號為1-n。

運用整體思想：

　　1、假設(shè)1到n-1個盤子是一個整體

　　2、將1到n-1個盤子構(gòu)成的整體移動到B

　　3、將第n個盤子移動到C

　　4、再將第2步移動到B的整體移動到C就可以了。

　　重復以上過程，顯然這是一個遞歸的過程。下面給出代碼。

1 public class a2_1_6 { 2 static void Hanoi(int n,char A,char B,char C) //將A上的盤子移動到C 3 { 4 if(n>0){ 5 Hanoi(n-1,A,C,B); //1、將A上1到n-1個盤子移動到B 6 move(A,C);//2、將A最下面那個第n個盤子移動到C 7 Hanoi(n-1,B,A,C); //3、將B上的1到n-1個盤子移動到C 8 } 9 } 10 11 private static void move(char a, char b) { 12 System.out.println(a+"-> "+b); //第二步，將A上剩余的一個盤移到C; 13 } 14 15 public static void main(String args[]){ 16 Hanoi(4,'A','B','C'); 17 } 18 }

?

結(jié)果大概這么回事：

遞歸寫代碼很簡潔，但是很容易寫錯，寫錯基本就StackOverflowError了，然后遞歸也比較抽象，不是那么容易理解。所以我的原則是可以不用遞歸盡量不用，后面有時間找找非遞歸版本的漢諾塔。本人學渣，不足之處，望各位大佬指正，謝謝！

?

轉(zhuǎn)載于:https://www.cnblogs.com/woyaodangxueba/p/10453067.html

總結(jié)

以上是生活随笔為你收集整理的2_1_6 递归与分治策略（汉诺塔问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。