漢諾塔（Tower of Hanoi，又稱(chēng)河內塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具。大梵天創(chuàng )造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著(zhù)64片黃金圓盤(pán)。大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。
當盤(pán)子的個(gè)數為n時(shí)，移動(dòng)的次數應等于2^n – 1。后來(lái)一位美國學(xué)者發(fā)現一種出人意料的簡(jiǎn)單方法，只要輪流進(jìn)行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤(pán)按從大到小的順序放在柱子A上，根據圓盤(pán)的數量確定柱子的排放順序：
若n為偶數，按順時(shí)針?lè )较蛞来螖[放 A、B、C；
若n為奇數，按順時(shí)針?lè )较蛞来螖[放 A、C、B。
① 按順時(shí)針?lè )较虬褕A盤(pán)1從現在的柱子移動(dòng)到下一根柱子，即當n為偶數時(shí)，若圓盤(pán)1在柱子A，則把它移動(dòng)到B；若圓盤(pán)1在柱子B，則把它移動(dòng)到C；若圓盤(pán)1在柱子C，則把它移動(dòng)到A。
② 接著(zhù)，把另外兩根柱子上可以移動(dòng)的圓盤(pán)移動(dòng)到新的柱子上。即把非空柱子上的圓盤(pán)移動(dòng)到空柱子上，當兩根柱子都非空時(shí)，移動(dòng)較小的圓盤(pán)。這一步?jīng)]有明確規定移動(dòng)哪個(gè)圓盤(pán)，你可能以為會(huì )有多種可能性，其實(shí)不然，可實(shí)施的行動(dòng)是唯一的。
③ 反復進(jìn)行①②操作，最后就能按規定完成漢諾塔的移動(dòng)。
所以結果非常簡(jiǎn)單，就是按照移動(dòng)規則向一個(gè)方向移動(dòng)金片：
如3階漢諾塔的移動(dòng)：A→C，A→B，C→B，A→C，B→A，B→C，A→C
// 用遞歸求解漢諾塔問(wèn)題
int step=1; // 整型全局變量,預置1,步數
void move(int, char, char, char);// 聲明要用到的被調用函數
void main()
{
int n;// 整型變量,n為盤(pán)數,
printf("請輸入盤(pán)數 n=");// 提示信息
scanf("%d",&n);// 輸入正整數n
printf("在3根柱子上移%d只盤(pán)的步驟為:",n);
move(n,'a','b','c');// 調用函數 move(n,'a','b','c')
system("pause");
}
void move(int m, char p, char q, char r)
{// 自定義函數體開(kāi)始
if (m==1)// 如果m為1,則為直接可解結點(diǎn),
{
// 直接可解結點(diǎn),輸出移盤(pán)信息
printf("[%d] move 1# from %c to %c", step,p,r);
step++;// 步數加1
}
else// 如果不為1,則要調用move(m-1)
{
move(m-1,p,r,q);// 遞歸調用move(m-1)
//直接可解結點(diǎn),輸出移盤(pán)信息
printf("[%d] move %d# from %c to %c", step, m, p, r);
step++;// 步數加1
move(m-1,q,p,r);// 遞歸調用move(m-1)
}
}//自定義函數體結束
運行結果：
請輸入盤(pán)數 n=4
在3根柱子上移4只盤(pán)的步驟為:
[1] move 1# from a to b
[2] move 2# from a to c
[3] move 1# from b to c
[4] move 3# from a to b
[5] move 1# from c to a
[6] move 2# from c to b
[7] move 1# from a to b
[8] move 4# from a to c
[9] move 1# from b to c
[10] move 2# from b to a
[11] move 1# from c to a
[12] move 3# from b to c
[13] move 1# from a to b
[14] move 2# from a to c
[15] move 1# from b to c
非遞歸方法：
#include <iostream>
using namespace std;
//圓盤(pán)的個(gè)數最多為64
const int MAX = 64;
//用來(lái)表示每根柱子的信息
struct st{
int s[MAX]; //柱子上的圓盤(pán)存儲情況
int top; //棧頂，用來(lái)最上面的圓盤(pán)
char name; //柱子的名字，可以是A，B，C中的一個(gè)
int Top()//取棧頂元素
{
return s[top];
}
int Pop()//出棧
{
return s[top--];
}
void Push(int x)//入棧
{
s[++top] = x;
}
} ;
long Pow(int x, int y); //計算x^y
void Creat(st ta[], int n); //給結構數組設置初值
void Hannuota(st ta[], long max); //移動(dòng)漢諾塔的主要函數
int main(void)
{
int n;
cout << "輸入圓盤(pán)的個(gè)數：" << endl;
cin >> n; //輸入圓盤(pán)的個(gè)數
st ta[3]; //三根柱子的信息用結構數組存儲
Creat(ta, n); //給結構數組設置初值
long max = Pow(2, n) - 1;//動(dòng)的次數應等于2^n - 1
Hannuota(ta, max);//移動(dòng)漢諾塔的主要函數
system("pause");
return 0;
}
void Creat(st ta[], int n)
{
ta[0].name = 'A';
ta[0].top = n-1;
//把所有的圓盤(pán)按從大到小的順序放在柱子A上
for (int i=0; i<n; i++)
ta[0].s[i] = n - i;
//柱子B，C上開(kāi)始沒(méi)有沒(méi)有圓盤(pán)
ta[1].top = ta[2].top = 0;
for (i=0; i<n; i++)
ta[1].s[i] = ta[2].s[i] = 0;
//若n為偶數，按順時(shí)針?lè )较蛞来螖[放 A B C
if (n%2 == 0)
{
ta[1].name = 'B';
ta[2].name = 'C';
}
else //若n為奇數，按順時(shí)針?lè )较蛞来螖[放 A C B
{
ta[1].name = 'C';
ta[2].name = 'B';
}
}
long Pow(int x, int y)
{
long sum = 1;
for (int i=0; i<y; i++)
sum *= x;
return sum;
}
void Hannuota(st ta[], long max)
{
int k = 0; //累計移動(dòng)的次數
int i = 0;
int ch;
while (k < max)
{
//按順時(shí)針?lè )较虬褕A盤(pán)1從現在的柱子移動(dòng)到下一根柱子
ch = ta[i%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " <<"Move disk " << ch << " from " << ta[i%3].name <<" to " << ta[(i+1)%3].name << endl;
i++;
//把另外兩根柱子上可以移動(dòng)的圓盤(pán)移動(dòng)到新的柱子上
if (k < max)
{ //把非空柱子上的圓盤(pán)移動(dòng)到空柱子上，當兩根柱子都為空時(shí)，移動(dòng)較小的圓盤(pán)
if (ta[(i+1)%3].Top() == 0 ||ta[(i-1)%3].Top() > 0 &&ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop();
ta[(i+1)%3].Push(ch);
cout << ++k << ": " << "Move disk "<< ch << " from " << ta[(i-1)%3].name<< " to " << ta[(i+1)%3].name << endl;
}
else
{
ch = ta[(i+1)%3].Pop();
ta[(i-1)%3].Push(ch);
cout << ++k << ": " << "Move disk "<< ch << " from " << ta[(i+1)%3].name<< " to " << ta[(i-1)%3].name << endl;
}
}
}
}
運行結果：
輸入圓盤(pán)的個(gè)數：
5
步驟：
1: Move disk 1 from A to C
2: Move disk 2 from A to B
3: Move disk 1 from C to B
4: Move disk 3 from A to C
5: Move disk 1 from B to A
6: Move disk 2 from B to C
7: Move disk 1 from A to C
8: Move disk 4 from A to B
9: Move disk 1 from C to B
10: Move disk 2 from C to A
11: Move disk 1 from B to A
12: Move disk 3 from C to B
13: Move disk 1 from A to C
14: Move disk 2 from A to B
15: Move disk 1 from C to B
16: Move disk 5 from A to C
17: Move disk 1 from B to A
18: Move disk 2 from B to C
19: Move disk 1 from A to C
20: Move disk 3 from B to A
21: Move disk 1 from C to B
22: Move disk 2 from C to A
23: Move disk 1 from B to A
24: Move disk 4 from B to C
25: Move disk 1 from A to C
26: Move disk 2 from A to B
27: Move disk 1 from C to B
28: Move disk 3 from A to C
29: Move disk 1 from B to A
30: Move disk 2 from B to C
31: Move disk 1 from A to C
－End－
聯(lián)系客服
