求漢諾塔問題的詳解 C,如何解漢諾塔問題

時間 2023-05-09 19:48:11

1樓:匿名使用者

漢諾塔遊戲的目的是把原來在a上的所有圓盤藉助b移動到c。 先給你分析下遞迴演算法,從最簡單的開始,遞迴演算法就是函式自己呼叫自己把複雜問題逐步簡單化直到最簡單時遞迴結束:

設a上有n個盤子。

如果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時, 移動的過程可分解為三個步驟:

第一步 把one上的n-1個圓盤,藉助three,移到two上;=>hanoi(n-1,one,three,two)

第二步 把one上的一個圓盤,移到three上;=>move(a,c)

第三步 把two上的n-1個圓盤,藉助one,移到three上;=>hanoi(n-1,two,one,three)

其中第一步和第三步是類同的。 當n=3時,第一步和第三步又分解為類同的三步,即把n'-1個圓盤從一個針移到另一個針上,這裡的n'=n-1。 備註:

這是我另一位網友的答案,直接copy過來做了微小改動適合你的程式。

2樓:匿名使用者

呵呵。這是個很有趣的程式。漢諾塔有3個柱,最多3個盤。

最底層那個總為1。第二層就是n-1。當n為1時,代表只有一個盤,直接移到3柱。

當超過一個盤時,執行hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); 這個hanoi()裡面的one,two,three是個形式引數,所以你只要老是看hanoi(n,a,b,c)就行了。至於形參換位置,就是abc換位置,於是上面的指令就是第二層盤子從1柱移到2柱,後面的就是3層的盤子移到3柱,函式重呼叫,,,最後顯示,則是從那個if(n==1)**開始,因為這是函式衝呼叫 的規則,。。這題的思維是反過來的,。

如何解漢諾塔問題

漢諾塔問題!!!

3樓:匿名使用者

數學歸納法:

一個盤子的話,一次就ok,記a1=1

兩個盤子,分三步:

1.將b最上面的一個盤子移到c上,就個就是上面一個盤子的情況,即a1次。

2.將b最下面的盤子移到a上,一次就好。

3.將c的所有盤子(1個),移到a上面,即a1次。

也就是a2=2a1+1=3 =2^2-1

三個盤子,分三步:

1.將b最上面的兩個盤子移到c上,即a2次2.將b最下面的盤子移到a上,一次就好。

3.將c上面的兩個盤子,移到a上,即a2次。

也就是a3=2a2+1=7=2^3-1

同理,n個盤子的情況:

1.將b上面的n-1個盤子移到c上,即an-1次2.將b最下面的盤子,移到a上,一次就好。

3.將c上面的兩個盤子,移到a上,即an-1次也就是an=2an-1 +1=2^n-1

漢諾塔問題 20

4樓:匿名使用者

第一次看的時候都是覺得很強大的,等你明白了後你就覺得那都是小兒科。

先確認你明白了分治策略的思想再說吧,一般寫不出**的情況都是對思想理解的不透,只是泛泛的理解。

先用筆在紙上好好的想想你的思想對不對,別一來就開始寫**,這對學習演算法沒有效果。

5樓:匿名使用者

設f(n, a, b,c) 表示 把n個盤從a移到c 藉助b ,它等於三個步驟。

個盤從a移到b

2 1個盤從a移到c

3 n-1個盤從b移到c

看第一個步驟,n-1個盤從a移到b,設為g(n-1,a,c,b),它又等於三個步驟。

n-2個盤從a移到c

1個盤從a移到b

n-1個盤從c移到b

這三個步驟恰恰是盤子為n-1時,從a移到b藉助c的步驟,就是說,這三個步驟等於f(n-1,a,c,b)

所以g(n-1,a,c,b)=f(n-1,a,c,b),進而推的。

f(n, a, b,c) =f(n-1, a,c,b) ,f(1, a, b,c), f(n-1, b,a,c))

自己參悟吧,很簡單的。

6樓:匿名使用者

程式設計時,腦子裡不要去思考遞迴過程**來轉去,會讓人很頭疼,一會兒就暈了)。

數列我想你是清楚的,所謂的遞迴,就是把an變成a(n-1)去處理問題,處理一個通項式是相同的方法,只要給出a1(或者還有a2),這是遞迴結束的條件。

假設漢諾塔a b c三根針,只考慮移動最底下的盤子時,如果只有一個盤子,就是直接a->c

如果只有兩個盤子,就是a->b 然後a->c

如果只有三個盤子,就是a->c a->b c->b 然後a->c

可以發現,1)如果想移動最底下的盤子,則,先要上面n-1個移動到b盤,即可。

2)在移動b盤上的n-1中的最底下的盤子時,則改變一下源針和中間針即可,即:把b看成a a看成b

3)接下來,在移動a盤上的n-2中的最底下的盤子時,則恢復源針和中間針即可,即:a還是a,b還是b。本步與第一步相同,即1 2兩步是在n>1時,的迴圈。

4)當只有一個盤子時(n=1),就做「源針」到「目標針」即可,結束本次遞迴。

因此,遞迴程式只有以上三步,即可實現漢諾塔的移動。

c++雙層漢諾塔問題。。。很有意思也很難

7樓:網友

其實和單層的一樣,將設有2n個在a

起始:a,需要移動2n,則先將2n-1個移到c,再將一個移到b,這時最大的兩個分別已經到位。

起始:c,需要移動2n-2,則先將2n-4個移到a,再將一個移到b,這時次大的兩個分別到位。

起始:a,需要移動2n-4,則先將2n-5個移到a,再將一個移到b,這時第三大的兩個分別到位。

.以此類推就行,具體請去參考理解單層漢諾塔的實現。

漢諾塔問題,為什麼程式這樣寫,請解釋一下 50

漢諾塔問題

8樓:匿名使用者

漢諾塔問題是典型的遞迴問題,解題的關鍵就是將這個問題逐步進行分解,直到最後剩1個盤子的時候一步完成。

基本上,漢諾塔可以可以用下面的方式實現:

void move(char x, char y){ cout<"<

當只剩下1個盤子的時候,把最後一個盤子從起始柱子移動到目標柱子。就是程式中n==1時候的分支;

當剩下的盤子很多的時候,就將整個過程分解:

1、把n-1個盤子從起點柱子移動到(當前)沒有任何盤子的過度柱子;

2、把最後一個盤子從起點柱子移動到目標柱子;

3、把n-1個盤子從過度柱子移動到目標柱子(模仿1和2的操作方法來實現)。

這就是else分支所要進行的操作。

因此,這裡面用到了2次遞迴,一次是操作1,一次是操作3。

c++漢諾塔的執行問題

9樓:古鎮靈狐

這是一個遞迴函式,move(m, 'a', b', c')這個函式要做的事情是把m個盤從a藉助b運到c。要完成這個事情,一共分三步走,首先將m-1個盤從a藉助c運到b,再將第m個盤運到c,最後將m-1個盤從b藉助a運到c。走完這3步,你就完成了這個函式的功能。

那麼如何將m-1個盤從a藉助c運到b,再將第m個盤運到c呢?我們可以利用遞迴呼叫自己move(m-1, 'a', c', b'),這有要按函式的三步走,一直遞迴下去,直到只有一個盤的時候結束,也就是進入函式的if(n==1).

1 的作用就是把n個盤中(除了最大的那個第n個盤)n-1個盤從a通過c運送到b

2 的作用是把這n-1個盤從b通過a再運到c

1執行完當然就是執行3了,3執行完執行2。不過1和2都是遞迴呼叫了自己,所以都會一層一層的走下去,走到n==1然後又一層層回來,自己體會。。

怎麼執行怎麼輸出看我前面的大部頭解釋。

10樓:瞬

遞迴的程式千萬不要去研究他是怎麼執行的,而是要知道它的退出條件,他的深度遍歷的條件,剛開始學遞迴肯定會很迷惑,建議你多做一些深搜的題目,你就自然會明白遞迴了,我這裡有一些參加比賽時所練習的一些題目,從最初的難度一點點上升(ps:我開始不會寫遞迴的,現在很熟練了)如果你需要的話可以給你,不需要你採納也可以。

11樓:科研知識

你看下c語言遞迴呼叫那一章節就會明白。

100財富求講解達人 C語言遞迴漢諾塔求講解

遞迴法是一種很方便的演算法,你不要太過於糾結過程。hannoi這個函式4個變數,分別是要處理的塔的層數n,和塔a,b,c a表示原塔,b是目標塔,c是中間的塔 當n 1時,只有一層,直接移動 其餘情況 先講上面的 n 1 層塔移到c上,此處可看做原問題的子問題,即hanoi n 1,a,c,b 再將...

C語言漢諾塔問題,請問這個n 3的詳細步驟是什麼呀,大一新生

看不懂 知道你上大學 但你也不要欺負我們這些沒文化的嘛 你應該去問你的老師 求真正理解漢諾塔問題的程式設計大神回答一下,當n 3時,用c語言編寫的漢諾塔遞迴呼叫 的詳細執行過程 汗會欣 漢諾塔 hannota.c include 解法 如果柱子標為abc,要由a搬至c,在只有一個盤子時,就將它直接搬...

c語言問題求詳解不要只有答案

第1題 b a選項,例 void f int j int main 很明顯 全域性變數j的作用域僅限於main函式區域性變數i作用域為f函式,但main函式中未使用j,實際上j的作用域為無。c選項 函式的形參都是區域性變數 d選項 auto變數只有呼叫的時候才賦值,呼叫結束就釋放,所以無初值 sta...