python實現漢諾塔遞歸算法經典案例

2019-11-25 16:47:12

字體：大中小

來源：轉載

供稿：網友

學到遞歸的時候有個漢諾塔的練習，漢諾塔應該是學習計算機遞歸算法的經典入門案例了，所以本人覺得可以寫篇博客來表達一下自己的見解。這markdown編輯器還不怎么會用，可能寫的有點格式有點丑啦，各位看官多多見諒.
　網上找了一張漢諾塔的圖片，漢諾塔就是利用用中間的柱子把最左邊的柱子上的圓盤依次從大到小疊上去，說白了就是c要跟原來的a一樣

廢話少說，先亮代碼

def move(n, a, buffer, c):  if(n == 1):    print(a,"->",c)    return  move(n-1, a, c, buffer)  move(1, a, buffer, c)  move(n-1, buffer, a, c)move(3, "a", "b", "c")

　首先是定義了一個移動的函數,四個參數分別代表，a柱上的盤子個數，buffer也就是b柱，命名為buffer便于理解，顧名思義就是一個a移動到c的緩沖區(qū).然后c就是目標柱子
下面我們來讀函數代碼
　遞歸的一般寫法，肯定有個中止遞歸循環(huán)的條件，所以在判斷a柱上的盤子個數為1的時候既可以中止遞歸并返回,a柱上面只有一個的時候肯定就是把a移動到c了，重點是下面的代碼，遞歸其實是一種很抽象的算法，我們要利用抽象思維去想漢諾塔這個問題，把a柱上的盤子想成兩份，就是上面的盤子和最底下的盤子，如果所示

　我們不關心上面的盤子到底有幾個，我們每次的操作就是把最底下的盤子通過緩沖區(qū) b柱 buffer 移動到c柱。
　童鞋們肯定在想為啥要醬紫移動呢，其實這是一種總結歸納吧，你自己玩一下漢諾塔游戲就會發(fā)現規(guī)律，其實這個游戲就是不停的把上面的所有的想方設法的移到b上，然后把a最后最大的那個弄到c,然后再絞盡腦汁的把b上的移動到c，這時候你就發(fā)現，原來b上的也要先通過空的也就是a來存放當前b上面的n-1個，然后把b的最大最后的移動到c，這里規(guī)律就體現出來了，也可以抽象出移動的方法，并可以以此設計出程序算法.

　以下我們來利用剛才的抽象思維解讀剩余代碼

move(n-1, a, c, buffer)

這段代碼就是表示把剛才所說的a柱的上面的n-1個，通過c按照從小到大的規(guī)則先移動到緩沖區(qū)buffer。此函數進入遞歸。

move(1, a, buffer, c)

當上面的語句執(zhí)行完成，也就是n-1個盤子的遞歸移動完成之后，執(zhí)行此語句，就是把a柱上的一個盤子移動到c,也就是所謂的最底下的盤子

move(n-1, buffer , a, c)

最后一步，就是剛才把a上面的n-1個都移動到了buffer上面，肯定要通過a移動到c才能完成整個漢諾塔的移動啊，于是最后一步自然是把剛才的n-1個通過a當緩沖區(qū)移動到c柱上.
　我來寫下整個移動流程，以a柱上有3個為例子

/**我把3個盤子的漢諾塔全部通過代碼演示，按縮進原則，每一個縮進即進一個遞歸函數，每打印一次即中止當前遞歸,也就是每個print說明:  1.n = 3, n = 2, n = 1是每次執(zhí)行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的第一個遞歸完成,打印結果，執(zhí)行當前子函數剩余代碼      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 的第二個遞歸完成，打印結果并執(zhí)行當前子函數的剩余代碼    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移動到c,//整個代碼執(zhí)行完畢,漢諾塔移動完成

最后的打印結果為: