學(xué)到遞歸的時(shí)候有個(gè)漢諾塔的練習(xí)，漢諾塔應(yīng)該是學(xué)習(xí)計(jì)算機(jī)遞歸算法的經(jīng)典入門案例了，所以本人覺得可以寫篇博客來(lái)表達(dá)一下自己的見解。這markdown編輯器還不怎么會(huì)用，可能寫的有點(diǎn)格式有點(diǎn)丑啦，各位看官多多見諒.

網(wǎng)上找了一張漢諾塔的圖片，漢諾塔就是利用用中間的柱子把最左邊的柱子上的圓盤依次從大到小疊上去，說(shuō)白了就是c要跟原來(lái)的a一樣

廢話少說(shuō)，先亮代碼

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")

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

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

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

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

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

move(1, a, buffer, c)

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

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

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

/**
我把3個(gè)盤子的漢諾塔全部通過(guò)代碼演示，按縮進(jìn)原則，每一個(gè)縮進(jìn)即進(jìn)一個(gè)遞歸函數(shù)，每打印一次即中止當(dāng)前遞歸,也就是每個(gè)print
說(shuō)明:
 1.n = 3, n = 2, n = 1是每次執(zhí)行if(n == 1)的結(jié)果，這里就不寫判斷了，相信童鞋們也能看懂，也就是n不等與1時(shí)就減1進(jìn)入遞歸
 2.請(qǐng)注意a,b,c柱每次進(jìn)入函數(shù)的順序，不要被形參帶錯(cuò)路了，看準(zhǔn)每次函數(shù)參數(shù)的實(shí)參 
**/
move(3, "a", "b", "c")
n=3:
 //開始從a上移動(dòng)n-1即2個(gè)盤子通過(guò)c移動(dòng)到b,以騰出c供a最后一個(gè)盤子移動(dòng)
 move(2, "a","c","b")
 n=2:
 //開始進(jìn)行n=2的一個(gè)遞歸，把當(dāng)前a('a')柱上的n-1個(gè)盤子通過(guò)c('b'）移動(dòng)到b('c')
  move(1, "a", "b", "c")
  n=1:
  //n=2的第一個(gè)遞歸完成,打印結(jié)果，執(zhí)行當(dāng)前子函數(shù)剩余代碼
   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個(gè)盤子的移動(dòng)
//開始把a(bǔ)柱上最后一個(gè)盤子移動(dòng)到c柱上
move(1, "a", "b", "c")
n=1:
 print("a", "->", "c")
 //到這里完成移動(dòng)a柱上的最后一個(gè)盤子到c柱上 
move(2, "b", "a", "c")
n=2:
//開始進(jìn)行n=2的第二個(gè)遞歸,即把當(dāng)前b('b')的盤子(n-1個(gè))通過(guò)a('a')移動(dòng)到c('c')上
 move(1, "b", "c", "a")
 n=1:
 //n=2 的第二個(gè)遞歸完成，打印結(jié)果并執(zhí)行當(dāng)前子函數(shù)的剩余代碼
  print("b", "->", "a")
 move(1, "b", "a", "c")
 n=1:
  print("b", "->", "c")
 move(1, "a", "b", "c")
 n=1:
  print("a", "->", "c")
  //到這里把b上的盤子通過(guò)a移動(dòng)到c,
//整個(gè)代碼執(zhí)行完畢,漢諾塔移動(dòng)完成

最后的打印結(jié)果為:

童鞋們理解了漢諾塔的遞歸算法原理后，可以寫個(gè)程序來(lái)試試，這里只是學(xué)到Python的遞歸所以用了Python，童鞋們可以用其他語(yǔ)言實(shí)現(xiàn)，漢諾塔確實(shí)能幫助理解遞歸原理，遞歸在程序設(shè)計(jì)中的重要性不言而喻啦！

最新評(píng)論