重温汉诺塔：
n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了，这种错误是放错了柱子，并不会把大盘放到小盘上，即各柱子从下往上的大小仍保持如下关系 ：
n=m+p+q
a1>a2>...>am
b1>b2>...>bp
c1>c2>...>cq
ai是A柱上的盘的盘号系列，bi是B柱上的盘的盘号系列， ci是C柱上的盘的盘号系列，最初目标是将A柱上的n个盘子移到C盘. 给出1个系列，判断它是否是在正确的移动中产生的系列.
例1：n=3
3
2
1
是正确的
例2：n=3
3
1
2
是不正确的。
注：对于例2如果目标是将A柱上的n个盘子移到B盘. 则是正确的.
Input
包含多组数据，首先输入T,表示有T组数据.每组数据4行，第1行N是盘子的数目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
对于每组数据，判断它是否是在正确的移动中产生的系列.正确输出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
这道题让我很好地重温了汉诺塔的计算法则以及递归算法的技巧。
首先需要了解得是汉诺塔的运算思想。个人认为递归的一个最大的特色，或者说优点就是可以不知道算法实现的具体流程和步骤，只要清楚它的思想就可以得到简练正确的代码实现。
言归正传，汉诺塔的实现只需要遵循三步不变的循环步骤，在没有达到预想情况时便一直不停递归。
目的是将a上所有的盘子全部借助b移到c上，并且每次只移动一个，小的只能发在大的上面，设一共有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，则需要结束循环即可。因此代码表示为：
以前学过的汉诺塔移动方式的算法是：
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);
}
}
而这道题目实则也是这三个步骤的考察。
首先，如果没有出现差错，则需要满足以上的移动规则。或者说是现在的三个杆子状态可以满足按照如上的步骤进行移动。
即满足的状态满足下列条件：
1、为了实现将第n个盘子从a（起始位置）移动到c（目标位置），所以应该满足第n个盘子一定不在b（中转位置）上，如果是在中转位置上，则说明还需要将第n个盘子从b移动到c，和上述的转移状态不相符，这样做便是增加了错误移动，次数将增加，所以首先判断最大的是否在b上，如果在，则说明一定不是最优，直接输出false结束。
（如果满足第一个条件，就可以判定了吗？当然不是，除此之外，还需要判定剩余的n-1个盘子仍旧满足条件。由于移动到第n-1个盘子时，起始位置和目标位置都会发生变化，所以也应该将a，b，c进行适当交换使满足b为中转位置。具体步骤为2,3。）
2、如果第n个盘子在a上，下面进行的便是将n-1个盘子从a到b上，需判断第n-1个盘子是不是在c上，可以将从，c，b交换，依旧判断b上是不是有第n-1个盘子。如果有，需要将它移动到目标位置，增加错误移动。
3、如果在c上，则说明上述的三个步骤已经进行了两个，需要进行的操作则是将第n-1个盘子从b移动到c，如果想要顺利移动，第n-1个盘子应该不在a上，此时，将a和b互换，判断目前最大是否在b上。
综上所述，整个过程所做的操作一直都是判断目前最大的盘子是否在b上，每判断一次便把b调整为中转位置。
由题意，每个盘子都所属一个杆子，每个杆子最多可以放的盘子数量也可以预知，所以可以使用标记法，也可使用结构体的方法。
以下是引用的网上大神的代码：
代码如下：
#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;
}
}
网友评论