【問題描述】
設(shè)A牛哺、B、C是3 個塔座。開始時瓶籽，在塔座A 上有一疊共n 個圓盤，這些圓盤自下而上桑逝，由大到小地疊在一起棘劣。各圓盤從小到大編號為1，2楞遏，……茬暇，n，奇數(shù)號圓盤著藍(lán)色寡喝，偶數(shù)號圓盤著紅色糙俗，如圖所示。現(xiàn)要求將塔座A 上的這一疊圓盤移到塔座B 上预鬓，并仍按同樣順序疊置巧骚。在移動圓盤時應(yīng)遵守以下移動規(guī)則：
規(guī)則(1)：每次只能移動1 個圓盤；
規(guī)則(2)：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上格二；
規(guī)則(3)：任何時刻都不允許將同色圓盤疊在一起劈彪；
規(guī)則(4)：在滿足移動規(guī)則(1)-(3)的前提下，可將圓盤移至A顶猜，B沧奴，C 中任一塔座上。
試設(shè)計一個算法长窄，用最少的移動次數(shù)將塔座A 上的n個圓盤移到塔座B 上滔吠，并仍按同樣順序疊置。
【編程任務(wù)】
對于給定的正整數(shù)n挠日，編程計算最優(yōu)移動方案.
其實(shí)雙色漢諾塔和漢諾塔是沒有區(qū)別的疮绷，不過漢諾塔的最優(yōu)次數(shù)的遞歸計算是很簡單的，我們也知道就是2^n-1次嚣潜，但是如何把其變化的方法表示出來則是需要一定的技巧冬骚，相信能將此題做出來后，遞歸就可以說是掌握的比較嫻熟了郑原。
先思考遞歸的終止條件唉韭，如果是n=0時候，就是什么都不用移動犯犁，直接結(jié)束遞歸即可属愤。再思考一下如果n=1時，只需要一步酸役，一個圓盤從A->B即可住诸，而兩個圓盤驾胆，則是先1 A->C，再 2 A->B,最后 1 C->B,初看上去很復(fù)雜贱呐，但其實(shí)不然丧诺，我們可以反著去研究，也是符合遞歸的思路奄薇，遞歸就是先研究最深層的n,然后通過遞推n-1,n-2的次數(shù)一直遞推至終止遞歸驳阎，得到結(jié)果。因此我們可以找到規(guī)律馁蒂，最后一次圓盤移動一定是最小的放到B的最上面呵晚，那倒數(shù)第二次圓盤移動一定是倒數(shù)第二小的放到B的最上面，以此類推沫屡。
如何打印順序呢饵隙， 那只需打印一行，n 從 a 到 b即可沮脖， 具體如何操作移動金矛，交由遞歸處理即可，具體思路流程有了勺届，如何實(shí)踐呢驶俊，n=1的時候，很明顯只需一次移動即可免姿，我們看看n=2時候废睦，也就是只有兩個圓盤的時候，是如何移動的养泡，我們是先要從1 A->C,2 A->B，要利用一個輔助盤先把1 從A移到C奈应，2 從A->B,后澜掩，再1 C->B,把輔助盤上的圓盤給放到目的地B上，n=2的時候是這樣杖挣，n=3的時候也是這樣肩榕，只不過多做了幾次操作，最后的步驟是一樣的惩妇，思路也是一樣的株汉， 需要利用輔助盤，因此 我們遞歸操作很簡單歌殃，先進(jìn)行將圓盤從 起點(diǎn)a到輔助盤c上乔妈，然后再將圓盤從輔助盤c放到目的地B上,每個圓盤都依次操作，只有最下面的圓盤是可以一步到位的氓皱，而這也無需我們考慮路召，代碼如下：
#include<iostream>
using namespace std;
void dchanoi(int n,char a,char b,char c)
{ if(n==0)
return ;
dchanoi(n-1,a,c,b);
cout<<n<<a<<b<<endl;
dchanoi(n-1,c,b,a);
}
int main()
{ int n;
cout<<"輸入n"<<endl;
cin>>n;
cout<<"從a移到b"<<endl;
dchanoi(n,'a','b','c');
}