漢諾塔問題是一個很經典的題目
哈哈，其實就是我們都已經很熟悉游戲規則了，在此我就在啰嗦一遍題目，
題目描述：
給定一個由n個圓盤組成的塔，這些圓盤按照大小遞減的方式套在第一根柱上，現要將整個塔移動到第三根柱上，每次只能移動一個圓盤，且較大的圓盤在移動程序中不能放置在較小的圓盤上面，
輸入：
輸入只有一個正整數n
輸出：
接下來每一行輸出一步移動步驟，
在此，我們討論比較一種簡單而且很好理解的做法——遞回做法，既然遞回，我們只要想好遞回函式，其它的就交給函式吧，
好了，正經了，我們可以想象除了一個圓盤外最簡單的一種情況——兩個圓盤（哈哈），這種我們當然都知道了，
第一步：只要把上面的1號從A移動到B，
第二步：把2號從A移動到C，
第三步：再把1號從B移動到C就可以了，
（ps：手繪的圖，大家就忍受下吧[委屈]）
此時，我們想想，我們剛才的步驟是不是就是將兩個圓盤從A借助B移動到了C，在我們將1號從A移動到B的時候我們也可以理解成把1號這個圓盤從A借助C移動到B（但是事實我們并沒有借助），這時我們就可以想象了，把那個1號圓盤當做成除了最下面那個圓盤外的（n-1）個圓盤，這時，是不是就豁然開朗了，對于n個圓盤我們一樣可以分為三步走[嘻嘻]，
第一步：將（n-1）個圓盤從A借助C移動到B
第二步：將第n個圓盤從A移動到C
第三步：將（n-1）個圓盤從B借助A移動到C
代碼實作下：
void hanoi(int n,char A,char B,char C)
{
if(n==0)
return ;
hanoi(n-1,A,C,B);
step(n,A,C);
hanoi(n-1,B,A,C);
}
另外為了觀察，我們還需要寫一個列印移動步驟的函式，把id號圓盤從a位置移動到b位置，
上代碼：
void step(int id,char a,char b) // 把id號圓盤從a位置移動到b位置
{
cout<<"第"<<cnt++<<"步: 把 "<<id<<"號 從 "<<a<<" 移動到 "<<b<<endl;
}
輸出結果：
至于輸出的結果當然就是輸出：將n個圓盤從A借助B移動到C的步數，也就是 hanoi(n,‘A’,‘B’,‘C’)，
完整代碼：
#include<bits/stdc++.h>
using namespace std;
int cnt;
void step(int id,char a,char b)
{
cout<<"第"<<cnt++<<"步: 把 "<<id<<"號 從 "<<a<<" 移動到 "<<b<<endl;
}
void hanoi(int n,char A,char B,char C)
{
if(n==0)
return ;
hanoi(n-1,A,C,B);
step(n,A,C);
hanoi(n-1,B,A,C);
}
int main()
{
int n;
cnt=0;
cin>>n;
hanoi(n,'A','B','C');
return 0;
}
感謝閱讀！
不妨點個贊再走唄，感謝支持！
加油！
共同努力！
Keafmd
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/64544.html
標籤：其他
上一篇：深聊性能測驗，從入門到放棄之：Locust性能自動化(一)初識Locust
下一篇：CGB2005-京淘16