建站
咨詢
售后
建站咨詢
新聞中心
- 漢諾塔問題簡介
- 解題思路
- 題目及題解
漢諾塔(又稱河內(nèi)塔)問題是印度的一個古老的傳說。開天辟地的神勃拉瑪在一個廟里
留下了三根金剛石的棒，第一根上面套著64個圓的金片，大的一個在底下，其余一個
比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)
定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。解答
結(jié)果請自己運行計算，程序見尾部。面對龐大的數(shù)字(移動圓片的次數(shù))15，看來，眾僧們
耗盡畢生精力也不可能完成金片的移動。
后來，這個傳說就演變?yōu)闈h諾塔游戲:
1.有三根桿子A,B,C。A桿上有若干碟子
2.每次移動一塊碟子,小的只能疊在大的上面
3.把所有碟子從A桿全部移到C桿上
1.如果只有一個金片，則把該金片從源移動到目標棒，結(jié)束。
2.如果有n個金片，則把前n-1個金片移動到中轉(zhuǎn)的棒，然后把自己移動到目標棒，最后再把前n-1個移動到目標棒。
題目描述
漢諾塔問題(又稱為河內(nèi)塔問題)，是一個大家熟知的問題。在A，B，C三根柱子上，有n個不同大小的圓盤(假設(shè)半徑分別為1~n吧)一開始他們都魯在A上，你的目標是在最少的合法移動步數(shù)內(nèi)將所有盤子從A塔移動到C塔。游戲中的每一步規(guī)則如下1每一步只允許移動一個盤子(從一根柱子最上方到另一個柱子的最上方)2.移動的過程中，你必須保證大的盤子不能在小的盤子上方(小的可以放在大的上面，大盤子下面不能有任何其他大小的盤子)給出一個數(shù)n，求出最少步數(shù)的移動序列
輸入
輸入盤子數(shù)N
輸出
輸出步數(shù)M，接下的M行，按以下格式輸出 i 盤子編號，a為柱編號，b為柱編號
輸入樣例
3
輸出樣例
7
1 form A to C
2 form A to B
1 form C to B
3 form A to C
1 form B to A
2 form B to C
1 form A to C
題解
#define _CRT_SECURE_NO_WARNINGS 1
#include#includevoid Hanoi(int n, char pos1, char pos2, char pos3);
void move(char pos1,char pos2);
int main()
{int n;
scanf("%d", &n);
printf("%.0lf\n", pow(2, n) - 1);
Hanoi(n, 'A', 'B', 'C');
return 0;
}
//pos1 起始位置
// pos2 中轉(zhuǎn)位置
// pos3 目的位置
void move(int n,char pos1,char pos2)
{printf("%d form %c to %c\n",n,pos1,pos2 );
}
void Hanoi(int n,char pos1,char pos2,char pos3)
{int count = 0;
if (n == 1)
{ move(1,pos1, pos3);//遞歸結(jié)束條件，直接從起始位置至目的位置
}
else
{Hanoi(n - 1, pos1, pos3, pos2);
move(n,pos1, pos3);
Hanoi(n - 1, pos2, pos1, pos3);
}
} 輸出截圖
你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
標題名稱：漢諾塔問題-創(chuàng)新互聯(lián)
URL分享：http://www.dlmjj.cn/article/ipige.html
