hanoiツインタワー
2084 ワード
Problem Description
a、b、cの3本の十分な長さの細い柱が与えられ、a柱に2 n(n<=200)個の中間に穴のある円盤が置かれ、n個の異なる寸法が共有され、各寸法には2つの同じ円盤があり、この2つの円盤は区別されていないことに注意する.同じサイズの円盤が一緒にあります.
これらのディスクをcカラムに移動し、移動中にbカラムに一時保存できます.要件:
(1)毎回1つの円盤しか移動できない.
(2)a,b,cの3本の細い柱上の円盤はいずれも上下大の順序を保たなければならない.
上記のタスクを完了するために必要な移動回数を最小限にしてください.
Input
第1の挙動Tが入力され、データ群数を表し、データ群毎にnが1つ、aカラム上に2 n個の円盤が置かれていることを示す.
Output
各入力セットについて、上記のタスクを完了するために必要な最小移動回数を出力します.
Sample Input
Sample Output
a、b、cの3本の十分な長さの細い柱が与えられ、a柱に2 n(n<=200)個の中間に穴のある円盤が置かれ、n個の異なる寸法が共有され、各寸法には2つの同じ円盤があり、この2つの円盤は区別されていないことに注意する.同じサイズの円盤が一緒にあります.
これらのディスクをcカラムに移動し、移動中にbカラムに一時保存できます.要件:
(1)毎回1つの円盤しか移動できない.
(2)a,b,cの3本の細い柱上の円盤はいずれも上下大の順序を保たなければならない.
上記のタスクを完了するために必要な移動回数を最小限にしてください.
Input
第1の挙動Tが入力され、データ群数を表し、データ群毎にnが1つ、aカラム上に2 n個の円盤が置かれていることを示す.
Output
各入力セットについて、上記のタスクを完了するために必要な最小移動回数を出力します.
Sample Input
2
1
2
Sample Output
2
6
/*
:A N , POW(2,N)-1 , N
POW(2,N+1)-2 ;
*/
// :
#include
#include
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("
");
}
return 0;
}