【（伪）递归】HDU1997 - 汉诺塔VII（非递归解法）

本文主要是介绍【（伪）递归】HDU1997 - 汉诺塔VII（非递归解法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

汉诺塔大家应该很熟悉了吧？啥！？没听说过！？上面那么大一张图片是什么？

这次学长出了一道很DT的题（不要问我啥是DT，打开搜狗输入法输入dt按两下等号再按一下空格就知道了），看了看大神们的解……嗯……看不懂，但是中心思想还是大差不差，他们都用了递归啦、打表啦，我就想着不用递归试试！

【题目】

     
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

     
true
false
false
false
true
true

【解题思路】

汉诺塔移动盘子的步骤（步骤自行百度）是一定的，这就会有一定的规律，规律是，最下面的盘子一定会出现在目标柱子和起始柱子上，比如有3个盘子从大到小标号为3、2、1，要把他们从A柱移到C柱上，那么3号盘子一定不可能出现在B柱上，因为移3号盘子时是直接从起始柱（此时为A柱）移到目标柱（此时为Ｃ柱上的），那么当把３移到Ｃ柱上之后，此时Ａ柱上就没有盘子了，而Ｂ柱从下往上数是２、１号盘子，此时２号盘子便成了剩下盘子中接下来将要移至目标柱（Ｃ柱）的最大号盘子了，而对于２号盘子，此时它的起始柱为Ｂ柱，目标柱为Ｃ柱，所以在以后的步骤中，２盘是不可能出现在此时的中间柱Ａ柱上的。

如果盘子多了，不管什么情况，最下面待移动的最大盘子的目标柱一定是Ｃ，起始柱当最大盘子编号换一次，柱子在Ａ、Ｂ之间换一次，当然最最大的盘子的起始柱一定是Ａ柱。

所以检测最下面最大的盘子位置是否正确时分三种情况：

１、当前最大的待移动的盘子在起始柱上（正确位置Ｉ）。

此时接着检测第二大的待移动的盘子，而这个时候第二大的待移动的盘子需要被移到对于最大的待移动的盘子来说的中间柱上，即对于第二大的盘子，它的起始柱于最大的待移动的盘子的起始柱相同，目标柱却是最大的待移动的盘子的中间柱！

２、当前最大的待移动的盘子在目标柱上（正确位置ＩＩ）。

此时还是要接着检测第二大的待移动的盘子，而这个时候第二大的待移动的盘子需要被移到对于最大的待移动的盘子来说的目标柱上，所以此时，第二大的待移动的盘子不可能粗现在最大的待移动盘子的起始柱上！

３、当前最大的待移动的盘子在中间柱上（错误位置）。

当前最大的待移动的盘子此时出现在了不该出现的柱子上，这种情况最简单，直接ｂｒｅａｋ出去报错！

循环检查至最小的盘子，全部出现在正确位置时即可报对了，循环时的难点就在起始柱、中间柱、目标柱的转换，转换方式如果上面的３种情况看懂了就简单了。具体还得看代码。

代码中二维数组ｐａｎ［ｘ］［ｊ］中ｘ表示Ａ、Ｂ、Ｃ三根柱子，ｊ表示此时从下至上每根柱子上盘子的序号，盘子序号是从小到大的升序。

ｏ１、ｏ２两步分别是更换起始柱目标柱的方式。

【代码】

#includeint panduan(int k,int aa,int bb,int cc,int pan[][64]);
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int k;
scanf("%d",&k);
int a,b,c,pan[3][64]={0};
scanf("%d",&a);
for(int i=0;i0;j--)
{
flag=1;
for(int i=0;i<64;i++)
{
if(pan[p][i]==j)
{
flag=0;
goto o1;
}			
else if(pan[q][i]==j)
{
flag=0;
goto o2;
}		
}
if(flag)
break;
o1: q=bb;m=bb;bb=cc;cc=m;
continue;
o2:	m=aa;p=bb;aa=bb;bb=m;
continue;	
}
if(flag)
return 0;
else
return 1;
}

这篇关于【（伪）递归】HDU1997 - 汉诺塔VII（非递归解法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！