漢諾塔 · 算法-不只leetCode

一．起源：　　漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。二．抽象為數學問題：　　如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數 ~~~ 解：（1）n == 1 第1次 1號盤 A---->C sum = 1 次 (2) n == 2 第1次 1號盤 A---->B 第2次 2號盤 A---->C 第3次 1號盤 B---->C sum = 3 次（3）n == 3 第1次 1號盤 A---->C 第2次 2號盤 A---->B 第3次 1號盤 C---->B 第4次 3號盤 A---->C 第5次 1號盤 B---->A 第6次 2號盤 B---->C 第7次 1號盤 A---->C sum = 7 次不難發現規律：1個圓盤的次數 2的1次方減1 　　　　　　　2個圓盤的次數 2的2次方減1 3個圓盤的次數 2的3次方減1 。。。。。 n個圓盤的次數 2的n次方減1 故：移動次數為：2^n - 1 ~~~ 三．調用方法的棧機制:（特點：先進后出）從主線程開始調用方法（函數）進行不停的壓棧和出棧操作，函數的調用就是將函數壓如棧中，函數的結束就是函數出棧的過程，這樣就保證了方法調用的順序流，即當函數出現多層嵌套時，需要從外到內一層層把函數壓入棧中，最后棧頂的函數先執行結束（最內層的函數先執行結束）后出棧，再倒數第二層的函數執行結束出棧，到最后，第一個進棧的函數調用結束后從棧中彈出回到主線程，并且結束。四．算法分析（遞歸算法）：我們在利用計算機求漢諾塔問題時，必不可少的一步是對整個實現求解進行算法分析。到目前為止，求解漢諾塔問題最簡單的算法還是同過遞歸來求，至于是什么是遞歸，遞歸實現的機制是什么，我們說的簡單點就是自己是一個方法或者說是函數，但是在自己這個函數里有調用自己這個函數的語句，而這個調用怎么才能調用結束呢？，這里還必須有一個結束點，或者具體的說是在調用到某一次后函數能返回一個確定的值，接著倒數第二個就能返回一個確定的值，一直到第一次調用的這個函數能返回一個確定的值。實現這個算法可以簡單分為三個步驟：　　　　（1）把n-1個盤子由A 移到 B；　　　　（2）把第n個盤子由 A移到 C；　　　　（3）把n-1個盤子由B 移到 C；從這里入手，在加上上面數學問題解法的分析，我們不難發現，移到的步數必定為奇數步：　　　　（1）中間的一步是把最大的一個盤子由A移到C上去；　　　　（2）中間一步之上可以看成把A上n-1個盤子通過借助輔助塔（C塔）移到了B上，　　　　（3）中間一步之下可以看成把B上n-1個盤子通過借助輔助塔（A塔）移到了C上； ~~~ package com.imooc; import java.util.Scanner; public class TowerOfHanoi { static int m =0; //標記移動次數 //實現移動的函數 public static void move(int disks,char N,char M) { System.out.println("第" + (++m) +" 次移動 : " +" 把 "+ disks+" 號圓盤從 " + N +" ->移到-> " + M); } //遞歸實現漢諾塔的函數 public static void hanoi(int n,char A,char B,char C) { if(n == 1 ) //圓盤只有一個時，只需將其從A塔移到C塔 TowerOfHanoi.move(1, A, C); //將編b號為1的圓盤從A移到C else { //否則 hanoi(n - 1, A, C, B); //遞歸，把A塔上編號1~n-1的圓盤移到B上，以C為輔助塔 TowerOfHanoi.move(n, A, C); //把A塔上編號為n的圓盤移到C上 hanoi(n - 1, B, A, C) ; //遞歸，把B塔上編號1~n-1的圓盤移到C上，以A為輔助塔 } } public static void main(String[] args) { Scanner imput = new Scanner(System.in); char A = 'A'; char B = 'B'; char C = 'C'; System.out.println("*************************************"); System.out.println("這是漢諾塔問題(把A塔上編號從小號到大號的圓盤從A塔通過B輔助塔移動到C塔上去"); System.out.println("***************************************"); System.out.print("請輸入圓盤的個數："); int disks = imput.nextInt(); TowerOfHanoi.hanoi(disks, A, B, C); System.out.println(">>移動了" + m + "次，把A上的圓盤都移動到了C上"); imput.close(); } } ********************************************************************** 這是漢諾塔問題（把A塔上編號從小號到大號的圓盤從A塔通過B輔助塔移動到C塔上去 ********************************************************************** 請輸入圓盤的個數：4 第1 次移動 : 把 1 號圓盤從 A ->移到-> B 第2 次移動 : 把 2 號圓盤從 A ->移到-> C 第3 次移動 : 把 1 號圓盤從 B ->移到-> C 第4 次移動 : 把 3 號圓盤從 A ->移到-> B 第5 次移動 : 把 1 號圓盤從 C ->移到-> A 第6 次移動 : 把 2 號圓盤從 C ->移到-> B 第7 次移動 : 把 1 號圓盤從 A ->移到-> B 第8 次移動 : 把 4 號圓盤從 A ->移到-> C 第9 次移動 : 把 1 號圓盤從 B ->移到-> C 第10 次移動 : 把 2 號圓盤從 B ->移到-> A 第11 次移動 : 把 1 號圓盤從 C ->移到-> A 第12 次移動 : 把 3 號圓盤從 B ->移到-> C 第13 次移動 : 把 1 號圓盤從 A ->移到-> B 第14 次移動 : 把 2 號圓盤從 A ->移到-> C 第15 次移動 : 把 1 號圓盤從 B ->移到-> C >>移動了15次，把A上的圓盤都移動到了C上 ~~~