圓盤邏輯移動過程+程序遞歸過程分析
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。