漢諾塔遞歸演算法分析

A. 什麼是遞歸演算法

遞歸演算法就是一個函數通過不斷對自己的調用而求得最終結果的一種思維巧妙但是開銷很大的演算法。
比如：
漢諾塔的遞歸演算法：
void move(char x,char y){
printf("%c-->%c\n",x,y);
}

void hanoi(int n,char one,char two,char three){
/*將n個盤從one座藉助two座，移到three座*/
if(n==1) move(one,three);
else{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

main(){
int n;
printf("input the number of diskes:");
scanf("%d",&n);
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C');
}
我說下遞歸的理解方法
首先：對於遞歸這一類函數，你不要糾結於他是干什麼的，只要知道他的一個模糊功能是什麼就行，等於把他想像成一個能實現某項功能的黑盒子，而不去管它的內部操作先，好，我們來看下漢諾塔是怎麼樣解決的
首先按我上面說的把遞歸函數想像成某個功能的黑盒子，void hanoi(int n,char one,char two,char three); 這個遞歸函數的功能是：能將n個由小到大放置的小長方形從one 位置，經過two位置 移動到three位置。那麼你的主程序要解決的問題是要將m個的"漢諾塊"由A藉助B移動到C，根據我們上面說的漢諾塔的功能，我相信傻子也知道在主函數中寫道：hanoi(m,A,B,C)就能實現將m個塊由A藉助B碼放到C，對吧？所以，mian函數裡面有hanoi(m,'A','C','B');這個調用。
接下來我們看看要實現hannoi的這個功能，hannoi函數應該幹些什麼？
在hannoi函數里有這么三行
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
同樣以黑盒子的思想看待他，要想把n個塊由A經過B搬到C去，是不是可以分為上面三步呢？
這三部是：第一步將除了最後最長的那一塊以外的n-1塊由one位置經由three搬到two 也就是從A由C搬到B 然後把最下面最長那一塊用move函數把他從A直接搬到C 完事後 第三步再次將剛剛的n-1塊藉助hannoi函數的功能從B由A搬回到C 這樣的三步實習了n塊由A經過B到C這樣一個功能，同樣你不用糾結於hanoi函數到底如何實現這個功能的，只要知道他有這么一個神奇的功能就行
最後：遞歸都有收尾的時候對吧，收尾就是當只有一塊的時候漢諾塔怎麼個玩法呢？很簡單吧，直接把那一塊有Amove到C我們就完成了，所以hanoni這個函數最後還要加上 if(n==1)move(one,three);（當只有一塊時，直接有Amove到C位置就行）這么一個條件就能實現hanoin函數n>=1時將n個塊由A經由B搬到C的完整功能了。
遞歸這個復雜的思想就是這樣簡單解決的，呵呵 不知道你看懂沒？純手打，希望能幫你理解遞歸
總結起來就是不要管遞歸的具體實現細節步驟，只要知道他的功能是什麼，然後利用他自己的功能通過調用他自己去解決自己的功能（好繞口啊，日）最後加上一個極限情況的條件即可，比如上面說的1個的情況。

B. 漢諾塔遞歸演算法是什麼

如下：

1、漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。

大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

2、抽象為數學問題：從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數。

演算法分析（遞歸演算法）：

實現這個演算法可以簡單分為三個步驟：把n-1個盤子由A 移到 B；把第n個盤子由 A移到 C；把n-1個盤子由B 移到 C。從這里入手，在加上上面數學問題解法的分析，我們不難發現，移到的步數必定為奇數步。

1、中間的一步是把最大的一個盤子由A移到C上去。

2、中間一步之上可以看成把A上n-1個盤子通過藉助輔助塔（C塔）移到了B上。

3、中間一步之下可以看成把B上n-1個盤子通過藉助輔助塔（A塔）移到了C上。

C. 漢諾塔遞歸問題

漢諾塔的遞歸演算法與解析

從左到右 A B C 柱 大盤子在下, 小盤子在上, 藉助B柱將所有盤子從A柱移動到C柱, 期間只有一個原則: 大盤子只能在小盤子的下面.
如果有3個盤子, 大中小號, 越小的越在上面, 從上面給盤子按順序編號 1(小),2(中),3(大), 後面的原理解析引用這里的編號.

遞歸演算法簡單來說就是方法內部自己調用自己, 同時也一定有一個結束點. 如果對方法調用棧了解的話,其實是很容易理解方法的調用過程的, 就是從主線程開始調用方法進行不停的壓棧和出棧操作. 方法的調入就是將方法壓入棧中, 方法的結束就是方法出棧的過程, 這樣保證了方法調用的順序流. 如果跟蹤遞歸的調用情況會發現也是如此, 到最後一定是這個方法最後從棧中彈出回到主線程, 並且結束.
棧的特點:先進後出。 比如一個方法 A 自己調用自己, 我用編號區分一下進棧過程:
A -> A(1) -> A(2) -> A(3)
在A(3)時滿足某種條件得以退出, 回到 A(2), A(2)結束回到A(1), 再回到A, 出棧過程:
A(3) -> A(2) -> A(1) -> A
對於遞歸,還有一個形象的認識,就是我小時候家裡有一個櫃子, 櫃子兩端都是玻璃, 頭伸進櫃子看一面鏡子,會看到鏡子里還有鏡子, 然後鏡子里還有鏡子, 但和遞歸的特點不同的是這鏡子的反射是沒有盡頭的, 只要眼睛一直能看到底的話.
了解完遞歸春虛橡後, 再回頭來看如何用遞歸的方式解決漢諾塔的問題.
案例 1 - 假設只有一個盤子的時候, 盤子數量 N=1
只有一個步驟 將第1個盤子從A移動到C, 為了對比方便我這樣來描述這個步驟：
步驟 盤子編號 從柱子移動 移動到柱子
1 1 A C
案例 2 - 如果有兩個盤子, 盤子數量 N = 2
步驟 盤子編號 從柱子移動 移動到柱子
1 1 A B
2 2 A C
3 1 B C
案例 3 - 如果有三個盤子, 盤子數量 N = 3
步驟 盤子編號 從柱子移動 移動到柱子
1 1 A C
2 2 A B
3 1 C B
4 3 A C
5 1 B A
6 2 B C
7 1 A C
如何找出盤子移動的規律 ？
我們要做的最重要的一件事情就是永遠要把最底下的一個盤子從 A 移動到 C
看看上面從1個盤子的移動到3個盤子的移動, 在移動記錄中,當盤子的編號和盤子數量相同的時候他們的步驟都是從A移動到C (看加粗的部分),其它的步驟對等.
再觀察第3個案例中的第 1-3 步 和 第 5-7步
第 1-3 步 目的是從 A 移動扒旁到 B 如果我們把 B 當作終點, 那麼這里的第 1-3 步理解起來和 第2個案例的三個步驟完全相同, 都是通過一個柱子來移譽祥動,和第2個案例比起來在後面加括弧來表示
1 1 A C ( A -> B)
2 2 A B ( A -> C)
3 1 C B ( B -> C)
總結：將盤子B變成C即可.
第 5-7 步 目的是從 B 移動到 C 如果我們把 C 當作終點, 那麼這里的 5-7 步理解起來和上面也是一樣的, 和第2個案例的三個步驟也完全相同.和第2個案例比起來就是:
5 1 B A ( A -> B)
6 2 B C ( A- > C)
7 1 A C ( B -> C)
總結: 將盤子B變成A即可
根據這個演示可以明確幾點規律:
1. 當盤子只有一個的時候,只有一個動作 從 A 移動到 C 即結束.
2. 當有N個盤子的時候, 中間的動作都是從 A 移動到 C, 那麼表示最下面的第N個盤子移動完畢
3. 中間動作之上都可以認為是: 從 A 移動到 B
4. 中間動作之下都可以認為是: 從 B 移動到 C
2，3，4 可以表示為
1 1 A B
2 2 A C
3 1 B C
這種結構一直在重復進行,C#不太熟悉,試著寫寫,就有了以下代碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure
{
class HanoiTower
{

public void MoveDisk(int DiskQuantity,string PositionA, string PositionB, string PositionC)
{
// If there's only one disk, then end.
if (DiskQuantity == 1)
{
Console.WriteLine("Move disk from position {0} to {1}.", PositionA, PositionC);
// Must return
return;
}
else
{
// Step 1 - Change B to C (A --> B)
MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
// Step 2 - No changes (A --> C)
MoveDisk(1, PositionA, PositionB, PositionC);
// Step 3 - Change B to A (A --> C)
MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
}
}

static void Main(string[] args)
{
HanoiTower hanoi = new HanoiTower();

Console.WriteLine("Please input Disk Quantity:");
int DiskQuantity = Convert.ToInt32(Console.ReadLine());

hanoi.MoveDisk(DiskQuantity, "A", "B", "C");

Console.ReadKey();
}
}
}

結合上面的分析,最重要的就是這里的3步交換動作, 中間從 A到C的動作是最底層盤子的最終操作.
//Step 1 - Change B to C (A --> B)
MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
//Step 2 - No changes (A --> C)
MoveDisk(1, PositionA, PositionB, PositionC);
//Step 3 - Change B to A (A --> C)
MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
至於第1個參數為什麼是DiskQuantity - 1,或者1 大家再回到上面看看是不是所有的步驟都是.. 1. 1,2,1. 1,2,1,3,1,2,1 這種以盤子數對稱的結構,而它前後都是重復1,2,1 的過程.

D. 漢諾塔遞歸演算法是什麼

漢諾塔遞歸演算法是演算法分析。實現這個演算法可以簡單分為三個步驟:把n-1個盤子由A 移到 B;把第n個盤子由 A移到 C，把n-1個盤子由B 移到 C。

漢諾塔的來源及應用

相傳在古印度聖廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤。

游戲的目標：把A桿上的金盤全部移到C桿上，並仍保持原有順序疊好。操作規則：每次只能移動一個盤子，並且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置於A、B、C任一桿上。

漢諾塔問題是用遞歸方法求解的一個典型問題，在實際教學中，可以在傳統教學方式的基礎上，利用計算機輔助教學進行演算法的模擬演示教學，使學生更容易接受和理解遞歸演算法的思想，不但能提高學生的學習興趣，而且還能取得較好的教學效果。

E. 漢諾塔遞歸演算法是什麼

漢諾塔是經典遞歸問題：

相傳在古印度聖廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤。

游戲的目標：把A桿上的金盤全部移到C桿上，並仍保持原有順序疊好。操作規則：每次只能移動一個盤子，並且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置於A、B、C任一桿上。

如果A只有一個（A->C）。

如果A有兩個（A->B）,(A->C),(B->C)。

如果A有三個（A->C）,(A->B),(C->B),(A->C),(B->A),(B->C),(A->C)。

如果更多，那麼將會爆炸式增長。

遞歸：就是函數自己調用自己。 子問題須與原始問題為同樣的事，或者更為簡單；遞歸通常可以簡單的處理子問題，但是不一定是最好的。

其實遞歸在某些場景的效率是很低下的。尤其是斐波那契.從圖你就可以發現一個簡單的操作有多次重復。因為它的遞歸調用倆個自己。那麼它的遞歸的膨脹率是指數級別的，重復了大量相同計算。

起源：

漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。

大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。