cms建站模板app,网站建设与管理必修,今天三河燕郊确诊名单,响应式网站滑动Problem Description
用1,2,...,n表示n个盘子#xff0c;称为1号盘#xff0c;2号盘,...。号数大盘子就大。经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事#xff0c;上帝创造世界时作了三根金刚石柱…Problem Description
用1,2,...,n表示n个盘子称为1号盘2号盘,...。号数大盘子就大。经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事上帝创造世界时作了三根金刚石柱子在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定在小圆盘上不能放大圆盘在三根柱子之间一回只能移动一个圆盘。我们知道最少需要移动2^64-1次.在移动过程中发现有的圆盘移动次数多有的少 。 告之盘子总数和盘号计算该盘子的移动次数.
Input
包含多组数据首先输入T,表示有T组数据.每个数据一行是盘子的数目N(1N60)和盘号k(1kN)。
Output
对于每组数据输出一个数到达目标时k号盘需要的最少移动数。
Sample Input
2
60 1
3 1
Sample Output
576460752303423488
4 解题思路
本以为是用数组逐个记录移动次数结果没做出来查询后发现原来是可以推出公式的。。。假设有10个盘子那么
盘号移动次数2的...次方10110-109210-98410-87810-7
因此第n个盘子移动的次数为2的n-k次方 代码如下
# include stdio.h
int main (void)
{int m, n, k;long long a;while (scanf(%d\n, m)!EOF){while (m--){scanf(%d%d\n, n, k);a pow (2, n-k);printf(%lld\n,a);}}
}
