漢諾塔是計算機學教科書中常用的游戲，用來說明遞回的魔力，該游戲有3個柱子和一組不同大小的圓盤，柱子從圓盤的中心穿過，
題目描述
設abc是三個塔座，開始時，在塔座a 上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊放在一起，各圓盤從小到大編號為1,2,3,...,n，
現要求將塔座a 上的一疊圓盤移到塔座 b 上，并仍按同樣順序疊置，在移動圓盤是應遵守以下移動規則：
每次只能移動一個圓盤；
任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；
在滿足移動規則1和2的前提下，可以將圓盤移至a,b,c中任一塔座上，
要求列印出出若干行，每行表示盤子的一次移動
如：1 a->c 表示將 a 號圓盤從 塔座移到 c 塔座
輸入
一行：n表示表示初始時 a塔有 c 個圓盤
輸出
未知行數
每行表示一次移動：
格式：圓盤編號 塔的編號->塔的編號
如：1 a->c 表示將 號圓盤從 a 塔座移到 c 塔座
樣例輸入
2
樣例輸出
1 A->C
2 A->B
1 C->B
游戲開始時，所有圓盤疊放在左側第一個柱子上，如下圖所示：
游戲的目標是將所有的圓盤從第一個柱子移動到第三個柱子，同時遵守以下規則：
① 除了被移動時，所有圓盤都必須放在柱子上，
② 一次只能移動一個圓盤，
③ 圓盤不能放置在比它小的圓盤上面，
現在來看一看游戲的一些玩法示例，最簡單的情況是當只有一個圓盤時：在這種情況下，只要將圓盤從第一個柱子移動到第三個柱子就可以一次性完成游戲，
如果有兩個圓盤，則需要通過 3 個步驟解決這個游戲：
① 將圓盤從第一個柱子移動到第二個柱子（它必須是最上面的一個)，
② 將圓盤從第一個柱子移動到第三個柱子，
③ 將圓盤從第二個柱子移動到第三個柱子，
請注意，雖然游戲的目的是將圓盤從第一個柱子移動到第三個柱子，但是有必要使用第二個柱子作為一些圓盤的臨時安放位置，解決方案的復雜性隨著要移動的圓盤數量的增加而迅速增加，
移動 3 個圓盤需要 7 步移動，如下圖所示：
這個游戲有一個迷人的傳說，根據這個傳說，河內寺廟里有一群僧侶，他們有 3 個柱子和 64 個圓盤，這些圓盤最初堆放在第一個柱子上，而僧侶們則需要將它們移動到第三個柱子上，當僧侶們完成任務時，世界將會消亡，
現在回到這個問題本身，來考慮當圓盤的數量不做限制時，一般情況下的解決方案，
這個問題可以被描述為：將 n 個圓盤從第一個柱子移動到第三個柱子，使用第二個柱子作為臨時柱子，
要理解如何使用回圈解決這個問題是非常困難的，但令人高興的是，設想一個遞回解決方案并不困難：如果可以（遞回地）將 n-1 個圓盤從第一個柱子移動到第二個柱子，而使用第三個柱子作為臨時掛鉤，那么最大的圓盤將獨自放在第一個柱子上，然后就可以一次性把最大圓盤從第一個柱子移動到第三個柱子，接下來，可以（遞回地）將 n-1 個圓盤從第二個柱子移動到第三個柱子，這次使用第一個柱子作為臨時柱子，
so:
#include <bits/stdc++.h>
using namespace std;
void f(int n,char x,char y,char z)
{
if(n==0) return;
f(n-1,x,z,y);
cout <<n << ' '<< x << "->" << z << endl;
f(n-1,y,x,z);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n;
cin >> n;
f(n,'A','C','B');
return 0;
}
本文來自小默的博客，轉載請注明原文鏈接：https://www.cnblogs.com/momotrace/p/17128304.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544097.html
標籤：其他
上一篇：vector的用法
下一篇：中文標題相似度檢測