1205：漢諾塔問題

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 19568 ??? 通過數: 7240

【題目描述】

約19世紀末，在歐州的商店中出售一種智力玩具，在一塊銅板上有三根桿，最左邊的桿上自上而下、由小到大順序串著由64個圓盤構成的塔。目的是將最左邊桿上的盤全部移到中間的桿上，條件是一次只能移動一個盤，且不允許大盤放在小盤的上面。

這是一個著名的問題，幾乎所有的教材上都有這個問題。由于條件是一次只能移動一個盤，且不允許大盤放在小盤上面，所以64個盤的移動次數是：18,446,744,073,709,551,615

這是一個天文數字，若每一微秒可能計算(并不輸出)一次移動，那么也需要幾乎一百萬年。我們僅能找出問題的解決方法并解決較小N值時的漢諾塔，但很難用計算機解決64層的漢諾塔。

假定圓盤從小到大編號為1, 2, ...

【輸入】

輸入為一個整數(小于20）后面跟三個單字符字符串。

整數為盤子的數目，后三個字符表示三個桿子的編號。

【輸出】

輸出每一步移動盤子的記錄。一次移動一行。

每次移動的記錄為例如 a->3->b 的形式，即把編號為3的盤子從a桿移至b桿。

【輸入樣例】

2 a b c

【輸出樣例】

a->1->c a->2->b c->1->b

【分析】

? ? ? ? 漢諾塔問題是經典問題，每本語言書中都有這道題。注意本題的要求是最終將盤子從a盤移動到b盤，而不是c盤。

【參考代碼】

#include <stdio.h> void move(char x,int y,char z) {printf("%c->%d->%c\n",x,y,z); } void hanoi(int n,char a,char c,char b) //a所在盤,c目標盤,b中轉盤 {if(n==1)move(a,n,c);else{hanoi(n-1,a,b,c);move(a,n,c);hanoi(n-1,b,c,a);} } int main() {int m;char x,y,z;scanf("%d %c %c %c",&m,&x,&y,&z);hanoi(m,x,y,z);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1205

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1205：汉诺塔问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。