漢諾塔問題：有三根柱子A,B,C，其中A上面有n個圓盤，從上至下圓盤逐漸增大，每次只能移動一個圓盤，并且規定大的圓盤不能疊放在小的圓盤上面，現在想要把A上面的n個圓盤全部都移動到C上面，輸出移動的總步數以及移動的過程
分析：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//先求出移動的總步數1，假設g（n）表示n個圓盤時的移動總的步數，當n=1時，g(1)=1;2.現在可以把g(n)進行細分為三步： 1>先將n-1個圓盤從A通過C移動到B上面，相當于將n-1個圓盤從A移動到C，因此需要g(n-1)步； 2>然后將剩下的最大的圓盤從A移動到C，需要1步； 3>最后再將n-1個圓盤從B通過A移動到C上面，相當于將n-1個圓盤從A移動到C，因此也需要g(n-1)步；因此可以得出遞歸關系式：g(n) = 2*g(n-1)+1;//現在我們在來求出移動的過程1.假設hm(m,a,b,c)表示將m個圓盤從a通過b移動到c的過程，假設mv(a,c)輸出一次a到c的過程，即print a-->c2.初始化hm，當m=1時，hm(1,a,b,c)=mv(a,c);2.可以把hm(m,a,b,c)進行細分為三步： 1>先將n-1個圓盤從A通過C移動到B，此時b和c進行互換，也就是 hm(m-1,a,c,b); 2>然后將剩下的最大的圓盤從A移動到C，也就是hm(1,a,b,c); 3>最后將n-1個圓盤從B通過A移動到C，此時b和a進行交換，也就是 hm(m-1,b,a,c);最終得到過程的遞歸關系式：hm(m,a,b,c) = hm(m-1,a,c,b)+1+hm(m-1,b,a,c); |
實現代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public class test{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); test t = new test(); //獲取總的步數 System.out.println("需要移動的總步數為:" +t.getSum(n)); //獲取移動的過程 t.hm(n,'a','b','c'); } //獲取總步數 public int getSum(int n){ if(n == 1) return 1; return 2 * getSum(n-1) +1 ; } //獲取移動的過程 public void hm(int m,char a,char b,char c){ if(m == 1) move(a,c); hm(m-1,a,c,b); move(a,c); hm(m-1,b,a,c); } //輸出一次移動的過程 public void move(char a,char c){ System.out.print(a + "-->" + c + " "); }} |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/qq_27905183/article/details/64123828
