hdu1995(汉诺塔问题,算出目标盒子的移动次数)
程序员文章站
2024-03-24 14:38:46
...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1995
题目描述:
即相当于给指定的总盒子个数,和目标盒子,需要给出目标盒子在这个总个数下的移动次数
思路:
用汉诺塔直接一步一步地移动去++的话,会导致越到后面话的时间就越多。故,我们转变思路。找其中的数字关系,如下:
//首先,如果是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;
}
上一篇: dstat命令的使用
下一篇: 74. 搜索二维矩阵