描述
漢諾塔（Tower of Hanoi），又稱河內(nèi)塔蚀瘸，是一個源于印度古老傳說的益智玩具衙解。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤疑故。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上童擎。并且規(guī)定舌剂，在小圓盤上不能放大圓盤请垛，在三根柱子之間一次只能移動一個圓盤。
將一個塔上的所有圓盤移動到另一個塔上见咒，每次僅能移動一個圓盤偿衰，且每次移動需要保持大的圓盤在下、小的圓盤在上
漢諾塔問題
分析
圓盤移動的次數(shù)與圓盤的個數(shù)滿足一種函數(shù)關系改览，在這里設定：
f(n) = m;
其中n為圓盤的個數(shù)下翎，m為完成整個過程所用的次數(shù)。
當只有一個圓盤的時候宝当，只需要移動一次即可：
f(1) = 1;
當有兩個圓盤的時候视事，移動方法比較簡單，需要移動三次：
f(2) = 3;
當有三個圓盤時今妄，所涉及的移動過程較為復雜：
以上郑口，f(3) = 7;
根據(jù)以上流程，可以總結(jié)出漢諾塔的移動規(guī)律：
stage01階段盾鳞，移動了f(n-1)次圓盤犬性；
stage02階段，移動了1次圓盤腾仅；
stage03階段乒裆，移動了f(n-1)次圓盤；
即f(n) = 2f(n-1) + 1;
實現(xiàn)代碼
// 漢諾塔
public int hannoi(int n){
if(n == 1){
return 1;
}else if(n == 2){
return 3;
}else{
return 2*hannoi(n-1)+1;
}
}
