ハノータV 1995(数学+打表+再帰)
1867 ワード
ハノータV
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3407 Accepted Submission(s): 1994
Problem Description
1,2,...,nでn個の皿を表し,1番皿,2番皿,...と呼ぶ.大皿を数えると大きい.クラシックなハンノタワー
問題はしばしば再帰的な古典的な例題として存在する.ハノタ問題の故事を知らない人もいるかもしれない.ハノタは
インドの伝説の1つのストーリ、神は世界を創造する時3本のダイヤモンドの柱を作って、1本の柱の上で下から上へ大きさを押します
64枚の黄金の円盤が順番に積み重ねられている.神はボロモンに円盤を下から大きさ順に別の柱に置くように命じた.
子の上.また、小円盤では円盤を拡大することができず、3本の柱の間で1回に1つの円盤しか移動できないことが規定されている.我々
少なくとも2^64-1回移動する必要があることを知っています.移動中に発見された円盤の移動回数は多く、少ないものもあります.に告げる
子の総数と皿番号を算出し、その皿の移動回数を算出する.
Input
複数組のデータを含んで、まずTを入力して、T組のデータがあることを示す.各データの1行は、皿の数N(1<=N<=60)と皿である
号k(1<=k<=N).
Output
各グループのデータについて、1つの数を出力し、目標に達したときにk番ディスクに必要な最小移動数を出力します.
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3407 Accepted Submission(s): 1994
Problem Description
1,2,...,nでn個の皿を表し,1番皿,2番皿,...と呼ぶ.大皿を数えると大きい.クラシックなハンノタワー
問題はしばしば再帰的な古典的な例題として存在する.ハノタ問題の故事を知らない人もいるかもしれない.ハノタは
インドの伝説の1つのストーリ、神は世界を創造する時3本のダイヤモンドの柱を作って、1本の柱の上で下から上へ大きさを押します
64枚の黄金の円盤が順番に積み重ねられている.神はボロモンに円盤を下から大きさ順に別の柱に置くように命じた.
子の上.また、小円盤では円盤を拡大することができず、3本の柱の間で1回に1つの円盤しか移動できないことが規定されている.我々
少なくとも2^64-1回移動する必要があることを知っています.移動中に発見された円盤の移動回数は多く、少ないものもあります.に告げる
子の総数と皿番号を算出し、その皿の移動回数を算出する.
Input
複数組のデータを含んで、まずTを入力して、T組のデータがあることを示す.各データの1行は、皿の数N(1<=N<=60)と皿である
号k(1<=k<=N).
Output
各グループのデータについて、1つの数を出力し、目標に達したときにk番ディスクに必要な最小移動数を出力します.
Sample Input
2
60 1
3 1
Sample Output
576460752303423488
4
// ,a[i]=2*a[i+1],
// , 。
#include<stdio.h>
#include<string.h>
#include<math.h>
int main(){
int i,n,m,t;
__int64 a[61]={0,1};
for(i=2;i<=60;i++)
a[i]=a[i-1]*2;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
printf("%I64d
",a[n-m+1]);
}
return 0;
}