一起玩轉漢諾塔

漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

後來，這個傳說就演變為漢諾塔遊戲，玩法如下:

1.有三根杆子A,B,C。A杆上有若干碟子

2.每次移動一塊碟子,小的只能疊在大的上面

3.把所有碟子從A杆全部移到C杆上

分析：

如果n=1，則將圓盤從A直接移動到C。
如果n=2，則：
1.將A上的n-1(等於1)個圓盤移到B上；
2.再將A上的一個圓盤移到C上；
3.最後將B上的n-1(等於1)個圓盤移到C上。
  如果n=3，則：
A. 將A上的n-1(等於2，令其為n`)個圓盤移到B(藉助於C)，步驟如下：
(1)將A上的n`-1(等於1)個圓盤移到C上。
(2)將A上的一個圓盤移到B。
(3)將C上的n`-1(等於1)個圓盤移到B。
B. 將A上的一個圓盤移到C。
C. 將B上的n-1(等於2，令其為n`)個圓盤移到C(藉助A)，步驟如下：
(1)將B上的n`-1(等於1)個圓盤移到A。
(2)將B上的一個盤子移到C。
(3)將A上的n`-1(等於1)個圓盤移到C。
   到此，完成了三個圓盤的移動過程。
    從上面分析可以看出，當n大於等於2時，移動的過程可分解為三個步驟：
第一步  把A上的n-1個圓盤移到B上；
第二步  把A上的一個圓盤移到C上；
第三步  把B上的n-1個圓盤移到C上；其中第一步和第三步是類同的。

也許你已經發現規律了，即每次都是先將其他圓盤移動到輔助柱子上，並將最底下的圓盤移到c柱子上，然後再把原先的柱子作為輔助柱子，並重複此過程。

這個過程稱為遞歸，即定義一組基本操作，這組操作將規模小一點（或大一點）的操作當做一個整體——無需關心它的細節，只當它已經完成了——然後執行剩下的操作。而在更小或更大的規模中也依此操作，直到規模達到預定值

在數學上，有些公式就是採用遞歸的方式定義的。例如階乘和斐波那契數列（Fibonacci Sequence）。前者的公式為：

規定0!=1!=1，對於n>=2，有n!=n*(n-1)!

這裡的n-1就是比n規模略小的階乘，而1就是規模的最小值（預定值）（0是作為特殊值而專門規定的）。

著名的斐波那契數列定義如下，可以看出，f(n)是由規模更小一些的f(n-1)和f(n-2)推導出來的：

f(0)=0，f(1)=1
f(n)=f(n-1)+f(n-2) (n>=2)

因此，遞歸實際上就是用自己來定義自己。

回到前面漢諾塔的問題上來。我們假設函數func(n, a, b, c)用於將n個圓盤由a移動到c，b作為輔助柱子。那麼我們可以這樣實現這個遞歸過程：

func:
if n!=0 then
;預定值 func(n-1, a, c, b)
;將n-1個盤子由a移動到b，以c為輔助柱子
（注意參數順序） move a[n] to c
;將a上的最後一個盤子移動到c func(n-1, b, a, c)
;將n-1個盤子由b移動到c，以a為輔助柱子

endif
;完成

ｊａｖａ代碼實現

import java.util.Scanner;

public class ddd{
    static int count=1;//用來記錄生成步驟的條數
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        move(n,"A","B","C");
    }
    /**
     * 將n個盤子從A移到B，C作為輔助的柱子
     * @param n 原來有多少個盤
     * @param A 原來放置盤子的柱子
     * @param B B柱子
     * @param C C柱子
     */
    public static void move(int n,String A,String B,String C) {
        if(n==1){
            System.out.println("第"+count+++"步:"+"將第1個盤從"+A+"移到"+B);
        }
            else{
            move(n-1,A,C,B);
            System.out.println("第"+count+++"步:"+"將第"+n+"個盤從"+A+"移到"+B);
            move(n-1,C,B,A);
        }
    };
        }

python代碼實現

def move(n, a, b, c):
if n==1:
        print (a,'-->',c)
        return
    else:
        # 首先需要把 (N-1) 個圓盤移動到 b
        move(n-1,a,c,b)
        # 將a的最後一個圓盤移動到c
        move(1,a,b,c)
        # 再將b的(N-1)個圓盤移動到c
        move(n-1,b,a,c)  
move(4, 'A', 'B', 'C')

詳細解釋：

def move(n, a, b, c):
if n==1:
        print (a,'-->',c)
        return
    else:
        # 首先需要把 (N-1) 個圓盤移動到 b
        move(n-1,a,c,b)
        # 將a的最後一個圓盤移動到c
        move(1,a,b,c)
        # 再將b的(N-1)個圓盤移動到c
        move(n-1,b,a,c)  
move(4, 'A', 'B', 'C')'''
我把3個盤子的漢諾塔全部通過代碼演示，
按縮進原則，每一個縮進即進一個遞歸函數，
每列印一次即中止當前遞歸,也就是每個print
說明:
 1.n = 3, n = 2, n = 1
 是每次執行if(n == 1)的結果，
 這裡就不寫判斷了，相信大家也能看懂，
 也就是n不等與1時就減1進入遞歸
 2.請注意a,b,c柱每次進入函數的順序，
 不要被形參帶錯路了，看準每次函數參數的實參
'''
move(3, "a", "b", "c")
n=3:
 #開始從a上移動n-1即2個盤子通過c移動到b,
 #以騰出c供a最後一個盤子移動
   move(2, "a","c","b")
  n=2:
 #開始進行n=2的一個遞歸，
 #把當前a('a')柱上的n-1個盤子
 通過c('b'）移動到b('c')
   move(1, "a", "b", "c")
  n=1:
 #n=2的第一個遞歸完成,列印結果，
 #執行當前子函數剩餘代碼
     print("a", "->", "c")
    move(1, "a", "c", "b")
  n=1:
       print("a", "->", "b")
    move(1, "c", "a", "b")
  n=1:
       print("c", "->", "b")
#到這裡完成了a柱上面的n-1即是2個盤子的移動
#開始把a柱上最後一個盤子移動到c柱上
   move(1, "a", "b", "c")
  n=1:
       print("a", "->", "c")
#到這裡完成移動a柱上的最後一個盤子到c柱上
   move(2, "b", "a", "c")
  n=2:
#開始進行n=2的第二個遞歸,
# 即把當前b('b')的盤子(n-1個)
# 通過a('a')移動到c('c')上
   move(1, "b", "c", "a")
   n=1:
#n=2 的第二個遞歸完成，
# 列印結果並執行當前子函數的剩餘代碼
     print("b", "->", "a")
    move(1, "b", "a", "c")
   n=1:
       print("b", "->", "c")
    move(1, "a", "b", "c")
   n=1:
       print("a", "->", "c")
# 到這裡把b上的盤子通過a移

擴展：漢諾塔問題的非遞歸實現

這種算法看得我頭疼，直接傳送門吧

https://tieba.baidu.com/f?kz=1255166419&red_tag=3546780199

知識重在總結和梳理，只有不斷地去學習並運用，才能化為自己的東西。由於本人進階猿類時間尚短，故此公眾號即是我學習，工作的筆記，也是和大家交流，相互提升技術的平臺，希望大家不吝賜教。