當前位置:編程學習大全網 - 遊戲軟體 - 求大神講解壹下C語言漢諾塔遞歸算法的簡易理解

求大神講解壹下C語言漢諾塔遞歸算法的簡易理解

壹開始我接觸漢諾塔也是很不解,隨著代碼量的積累,現在很容易就看懂了,因此樓主主要還是對遞歸函數的理解不夠深刻,建議妳多寫壹些遞歸程序,熟練了自己就能理解。

圓盤邏輯移動過程+程序遞歸過程分析

hanoi塔問題, 算法分析如下,設a上有n個盤子,為了便於理解我將n個盤子從上到下編號1-n,標記為盤子1,盤子2......盤子n。

如果n=1,則將“ 圓盤1 ” 從 a 直接移動到 c。

如果n=2,則:

(1)將a上的n-1(等於1)個圓盤移到b上,也就是把盤1移動到b上;

(2)再將a上 “盤2” 移到c上;

(3)最後將b上的n-1(等於1)個圓盤移到c上,也就是第(1)步中放在b上的盤1移動到c上。

註意:在這裏由於超過了1個盤子,因此不能直接把盤子從a移動到c上,要借助b,那

麽 hanoi(n,one,two,three)的含義就是由n個盤子,從one移動到three,如果n>2

那麽就進行遞歸,如果n=1,那麽就直接移動。

具體流程:

hanoi(2,a,b,c);由於2>1因此進入了遞歸的環節中。

<1>執行hanoi(1,a,c,b):這裏就是剛才的步驟(1),代表借助c柱子,將a柱子上的 1個圓盤(盤1)移動到b柱子,其實由於是n=1,此時c柱子並沒被用到,而是直接移動了。

<2>執行hanoi(1,a,b,c):這是步驟(2),借助b柱子,將a柱子上的壹個圓盤(盤2)移動到c柱子上。這裏由於也是n=1,也並沒有真正借助b柱子,直接移動的。

<3>執行hanoi(1,b,a,c):這是步驟(3),將b上的壹個盤子(盤1)移動到c

函數中由於每次調用hanoi的n值都是1,那麽都不會進入遞歸中,都是直接執行了mov移動函數。

如果n=3,則:(倒著想會想明白)移動的倒數第二部,必然是下面的情況

(1)將a上的n`-1(等於2)個圓盤移到c上,也就是將盤1、盤2 此時都在b柱子上,只有這樣才能移動最下面的盤子(盤3)。那麽由於現在我們先忽略的最大的盤子(盤3),那麽我們現在的目標就是,將兩個盤子(盤1、盤2)從a柱子上,借助c柱 子,移動到b柱子上來,這個過程是上面n=2的時候的移動過程,n=2的移動過程是“2 個盤子,從柱子a,借助柱子b,移動到柱子c”。現在是“2個盤子,從柱子a,借助柱子 c,移動到柱子b上”。因此移動過程直接調用n=2的移動過程就能實現。

(2)將a上的壹個圓盤(盤3)移到c。

(3)到這壹步,由於已經將最大的盤子(盤3)移動到了目的地,此時無論後面怎麽移動都不需要在用到最大的那個盤子(盤3),我們就先忽略他,剩下的目標就是將b上面的n-1個盤子(盤1、盤2)移動到c上,由於a上沒有盤子了,此時要完成上面的目標,就要借助a盤子。最終達到的目標就是將b上的2個盤子,借助a移動到c上,這個過程就是當n=2時分析的過程了,僅僅是最開始的柱子(b柱子)和被借助的柱子(a柱子)不同了。所以直接調用n=2時候的過程就能股實現了。

具體執行過程:

hanoi(3,a,b,c);由於3>1因此進入了遞歸的環節中。

<1>執行hanoi(2,a,c,b):這裏代表剛才的步驟(1),將兩個盤子(盤1、盤2)從a移動到b,中間借助c。根據n=2的分析過程,必然是能夠達到我們的目的。

<2>執行hanoi(1,a,b,c):現在a上只有壹個盤子(盤3),直接移動到c上面即可。

<3>執行hanoi(2,b,a,c):此時對應步驟(3),剩下的目標就是將b上的兩個盤子,借助a移動到c上。那麽同樣根據n=2的移動過程,必然能達到目的。

最終實現了3個盤子從a,借助b移動到了c。

  • 上一篇:位圖是什麽意思?
  • 下一篇:光暈1 傳奇 最後壹關
  • copyright 2024編程學習大全網