文档介绍：数学题之汉洛塔系列***@Gxjun ?汉诺塔 IV ?还记得汉诺塔 III吗?他的规则是这样的:不允许直接从最左(右)边移到最右(左) 边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到小盘的上面。 xhd 在想如果我们允许最大的盘子放到最上面会怎么样呢?(只允许最大的放在最上面)当然最后需要的结果是盘子从小到大排在最右边。 Input ?输入数据的第一行是一个数据 T,表示有 T组数据。每组数据有一个正整数 n(1 <= n <= 20) ,表示有 n个盘子。 Output ?对于每组输入数据,最少需要的摆放次数。 Sample Input ? 2 1 10 ? Sample Output ? 2 19684 ? Author ? xhd ? Source ? ACM 程序设计期末考试_热身赛(感谢 xhd & 8600) ?汉罗塔 1 经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着 64 片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘。有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩,当然这个传说并不可信,如今汉诺塔更多的是作为一个玩具存在。 Gardon 就收到了一个汉诺塔玩具作为生日礼物。 Gardon 是个怕麻烦的人(恩,就是爱偷懒的人),很显然将 64 个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难,所以 Gardon 决定作个小弊,他又找来了一根一模一样的柱子,通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是:当 Gardon 在一次游戏中使用了 N个盘子时,他需要多少次移动才能把他们都移到第三个柱子上?很显然,在没有第四个柱子时,问题的解是 2^N-1 ,但现在有了这个柱子的帮助,又该是多少呢? 汉诺塔 V 用 1,2,...,n 表示 n个盘子,称为 1号盘, 2号盘,... 。号数大盘子就大。经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着 64 片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘。我们知道最少需要移动 2^64-1 ,有的圆盘移动次数多,有的少。告之盘子总数和盘号,计算该盘子的移动次数. ?? Input ?包含多组数据,首先输入 T,表示有 ,是盘子的数目 N(1<=N<=60) 和盘号 k(1<=k<=N) 。? Output ?对于每组数据,输出一个数,到达目标时 k号盘需要的最少移动数。 Sample Input ? 2 ? 60 1 ? 3 1 Sample Output ? 576460752303423488 ?4 ?分析:题目已经明确 s64=2^66-1;--- ? sk=2^k-1, 这样我们就可以得到在 n盘下,总共要移动的盘子的步数啦,但是要我们在该盘数下,某一个盘子移动了多少步,这样我们又该如何做勒!,请大家思考….?却是是难以知道,但是我们知道 n=1,k=1 时, ans=1 , sum=1; n=2; sum=3 K=1 ans=2; K=2 ans=1; n=3 , sum=7 k=1 ans=4 ,k=2 ans=2, k=3,ans=1 由此,可以找到规律不妨假设 n,k 时, ans=2^ ( n-k );因而 ac 的话就不再话下啦!、、、/* ***@coder 龚细军*/ #include<> _int64 save[60]; void work() { for(int i=0;i<60;i++) save[i]=1LL<<(59-i); } int main() { int n,m,test; work(); scanf("%d",&test); while(test--) { scanf("%d%d",&n,&m); printf("%I64d\n",save[m+59-n]); } return 0; }?三把刀也好,六把刀也好,这些一点都不重要,我的剑和你的剑每一把的份量都不同! ?所谓强,不是指力气,也不是指技巧,而是心!