本文主要是介绍hanoi双塔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
给定a、b、c三根足够长的细柱，在a柱上放有2n(n<=200)个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的。尺寸相同的圆盘在一起。
现在将这些圆盘移动到c柱上，在移动过程中可放在b柱上暂存。要求：
(1) 每次只能移动一个圆盘；
(2) a、b、c三根细柱上的圆盘都要保持上小下大的顺序。
请问完成上述任务所需的最少移动次数。
现在将这些圆盘移动到c柱上，在移动过程中可放在b柱上暂存。要求：
(1) 每次只能移动一个圆盘；
(2) a、b、c三根细柱上的圆盘都要保持上小下大的顺序。
请问完成上述任务所需的最少移动次数。
Input
输入第一行为T，表示数据组数，对于每组数据就一个n，表示在a柱上放有2n个圆盘。
Output
对于每组输入，输出完成上述任务所需的最少移动次数。
Sample Input
2 1 2
Sample Output
2 6
/*
解题报告：A柱上只有N个盘子，至少移动次数为POW(2,N)-1次，而有N个不同的尺寸的两个 相同尺寸的盘子至少移动的次数为POW(2,N+1)-2次；
*/
//标程：
#include<stdio.h>
#include<string.h>
int p[205][205],a[200],maxn;
void f(int x)
{
int i,j;
for(i=1;i<=x+1;i++)
{
for(j=1;j<=200;j++)
p[x][j]=p[x][j]*2;
for(j=1;j<=200;j++)
{
if(p[x][j]>=10)
{
p[x][j+1]+=p[x][j]/10;
p[x][j]%=10;
maxn=j+1;
}
if(p[x][j]) maxn=j;
}
}
}
int main()
{
//freopen("a.txt","r",stdin);
int n,t,i,j;
memset(p,0,sizeof(p));
for(i=1;i<=200;i++)
{
maxn=0;
p[i][1]=1;
memset(a,0,sizeof(a));
f(i);
p[i][0]=maxn;
p[i][1]-=2;
}
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=p[n][0];i>0;i--)
printf("%d",p[n][i]);
printf("\n");
}
return 0;
}
这篇关于hanoi双塔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
