欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu1995(汉诺塔问题,算出目标盒子的移动次数)

程序员文章站 2024-03-24 14:38:46
...

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1995
题目描述:hdu1995(汉诺塔问题,算出目标盒子的移动次数)

即相当于给指定的总盒子个数,和目标盒子,需要给出目标盒子在这个总个数下的移动次数

思路:

用汉诺塔直接一步一步地移动去++的话,会导致越到后面话的时间就越多。故,我们转变思路。找其中的数字关系,如下:
//首先,如果是n个盒子,那么最小的移动次数就是为:2^n-1
//如果为3个盒子:1+2+4=7
//即[盒子3] 2^(3-3)+[盒子2] 2^(3-2)+[盒子1] 2^(3-1)
//如果为4个盒子:1+2+4+8=15
//即[盒子4] 2^(4-4)+[盒子3] 2^(4-3)+[盒子2] x^(4-2)+[盒子1] 2^(4-1)
//那么如果为n个盒子:1+2+…+2^(n-1)
//若要取n个盒子的第a个盒子的移动次数,就为:2^(n-a)

ac代码:

#include<stdio.h>

typedef long long int ll;

//如果是n个盒子,那么最小的移动次数就是为:2^n-1
//如果为3个盒子:1+2+4=7
			//即[盒子3] 2^(3-3)+[盒子2] 2^(3-2)+[盒子1] 2^(3-1)
//如果为4个盒子:1+2+4+8=15
 			//即[盒子4] 2^(4-4)+[盒子3] 2^(4-3)+[盒子2] x^(4-2)+[盒子1] 2^(4-1)
//那么如果为n个盒子:1+2+...+2^(n-1)
//若要取n个盒子的第a个盒子的移动次数,就为:2^(n-a) 
int main(){
	int t;
	int n,a;//n为总共n个盒子,a为第a个盒子 
	scanf("%d",&t);
	ll value[62];
	ll answer = 0;//用来接收结果的值 
	value[0] = 1;
	for(int i = 1;i <= 60;i++){//将2的1到60次方都记录到value数组里面 
		value[i] = value[i-1]*2;		
	}
//	printf("59次方:%lld\n",value[59]);
	while(t--){

		scanf("%d%d",&n,&a);

		printf("%lld\n",value[n-a]);


	}
	
	return 0;
	
}