重溫漢諾塔：
n個盤子的漢諾塔問題的最少移動次數(shù)是2^n-1,即在移動過程中會產(chǎn)生2^n個系列。由于發(fā)生錯移產(chǎn)生的系列就增加了汇恤，這種錯誤是放錯了柱子庞钢，并不會把大盤放到小盤上，即各柱子從下往上的大小仍保持如下關(guān)系 ：
n=m+p+q
a1>a2>...>am
b1>b2>...>bp
c1>c2>...>cq
ai是A柱上的盤的盤號系列因谎，bi是B柱上的盤的盤號系列基括， ci是C柱上的盤的盤號系列，最初目標是將A柱上的n個盤子移到C盤. 給出1個系列财岔，判斷它是否是在正確的移動中產(chǎn)生的系列.
例1：n=3
3
2
1
是正確的
例2：n=3
3
1
2
是不正確的风皿。
注：對于例2如果目標是將A柱上的n個盤子移到B盤. 則是正確的.
Input
包含多組數(shù)據(jù)，首先輸入T,表示有T組數(shù)據(jù).每組數(shù)據(jù)4行使鹅，第1行N是盤子的數(shù)目N<=64.
后3行如下
m a1 a2 ...am
p b1 b2 ...bp
q c1 c2 ...cq
N=m+p+q,0<=m<=N,0<=p<=N,0<=q<=N,
Output
????????????對于每組數(shù)據(jù)揪阶，判斷它是否是在正確的移動中產(chǎn)生的系列.正確輸出true昌抠，否則false
Sample Input
6 3 1 3 1 2 1 1 3 1 3 1 1 1 2 6 3 6 5 4 1 1 2 3 2 6 3 6 5 4 2 3 2 1 1 3 1 3 1 2 1 1 20 2 20 17 2 19 18 16 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Sample Output
true false false false true true
這道題讓我很好地重溫了漢諾塔的計算法則以及遞歸算法的技巧患朱。
首先需要了解得是漢諾塔的運算思想。個人認為遞歸的一個最大的特色炊苫，或者說優(yōu)點就是可以不知道算法實現(xiàn)的具體流程和步驟裁厅，只要清楚它的思想就可以得到簡練正確的代碼實現(xiàn)。
言歸正傳侨艾，漢諾塔的實現(xiàn)只需要遵循三步不變的循環(huán)步驟执虹，在沒有達到預想情況時便一直不停遞歸。
目的是將a上所有的盤子全部借助b移到c上唠梨，并且每次只移動一個袋励，小的只能發(fā)在大的上面，設一共有n個盤子当叭。這三個步驟為
1茬故、將最大盤子第n個盤子上的n-1個盤子移到b上。
2蚁鳖、這時磺芭，a上只有一個盤子n，則一次就可以把第n個盤子移到c上醉箕。
3钾腺、將b上的第n-1個盤子移到c上徙垫。
由于1,3,步驟中需要移動n-1個盤子，且移動過程遵循以上的法則放棒，那么步驟1：將n-1個盤子借助c從a移動到b上姻报，則又是一個如上的遞歸，直到成了將一個盤子從n移動到m上借助k间螟，則需要結(jié)束循環(huán)即可逗抑。因此代碼表示為：
?以前學過的漢諾塔移動方式的算法是：
void hanno(int n,char a,char b,char c)
{
if(n)
{
hanno(n-1,a,c,b);
?printf("%c->%c\n",a,c);
hanno(n-1,b,a,c);
}
}
而這道題目實則也是這三個步驟的考察。
首先寒亥，如果沒有出現(xiàn)差錯邮府，則需要滿足以上的移動規(guī)則「绒龋或者說是現(xiàn)在的三個桿子狀態(tài)可以滿足按照如上的步驟進行移動褂傀。
即滿足的狀態(tài)滿足下列條件：
1、為了實現(xiàn)將第n個盤子從a（起始位置）移動到c（目標位置）加勤，所以應該滿足第n個盤子一定不在b（中轉(zhuǎn)位置）上仙辟，如果是在中轉(zhuǎn)位置上，則說明還需要將第n個盤子從b移動到c鳄梅，和上述的轉(zhuǎn)移狀態(tài)不相符叠国，這樣做便是增加了錯誤移動，次數(shù)將增加戴尸，所以首先判斷最大的是否在b上粟焊，如果在，則說明一定不是最優(yōu)孙蒙，直接輸出false結(jié)束项棠。
（如果滿足第一個條件，就可以判定了嗎挎峦？當然不是香追，除此之外，還需要判定剩余的n-1個盤子仍舊滿足條件坦胶。由于移動到第n-1個盤子時透典，起始位置和目標位置都會發(fā)生變化，所以也應該將a顿苇，b峭咒，c進行適當交換使?jié)M足b為中轉(zhuǎn)位置。具體步驟為2,3岖圈。）
2讹语、如果第n個盤子在a上，下面進行的便是將n-1個盤子從a到b上蜂科，需判斷第n-1個盤子是不是在c上顽决，可以將從短条，c，b交換才菠，依舊判斷b上是不是有第n-1個盤子茸时。如果有，需要將它移動到目標位置赋访，增加錯誤移動可都。
3、如果在c上蚓耽，則說明上述的三個步驟已經(jīng)進行了兩個渠牲，需要進行的操作則是將第n-1個盤子從b移動到c，如果想要順利移動步悠，第n-1個盤子應該不在a上签杈，此時攒菠，將a和b互換饼问，判斷目前最大是否在b上爷辙。
綜上所述酒贬，整個過程所做的操作一直都是判斷目前最大的盤子是否在b上，每判斷一次便把b調(diào)整為中轉(zhuǎn)位置竞端。
由題意被因，每個盤子都所屬一個桿子蝗蛙，每個桿子最多可以放的盤子數(shù)量也可以預知择卦，所以可以使用標記法敲长，也可使用結(jié)構(gòu)體的方法。
以下是引用的網(wǎng)上大神的代碼：
代碼如下：
#include <iostream>
using namespace std;
int main()
{
int s;
int n;
int i,j;
int a,b,c;
int t[3][64];
int num[3];
int cas;
cin>>cas;
while(cas--)
{
cin>>n;
a=0;b=1;c=2;
for(i=0;i<3;i++)
for(j=0;j<n;j++)
t[i][j]=0;
for(i=0;i<3;i++)
{
cin>>num[i];
for(j=0;j<num[i];j++)
{
cin>>s;
t[i][s-1]=1;
}
}
while(n--)
{
if(t[b][n])
{
cout<<"false"<<endl;
break;
}
if(t[a][n])
{
i=b;
b=c;
c=i;
}
else if(t[c][n])
{
i=a;
a=b;
b=i;
}
}
if(n==-1)
cout<<"true"<<endl;
}
}