本文主要是介绍【递推】【DP】-HDU-1995-汉诺塔⑤，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1995
题目描述：计算汉诺塔中某个盘子的移动次数
解题思路：
想了好久，突然顿悟！
思路如下，所谓递推，即是前者与后者存在直接联系，由前者可以直接推出后者，因此必须有一端是已知的，这题里显然最下面的盘子只被动了一次，这就是开端，然后我们考虑紧挨着的两张盘子的递推关系，发现上面盘子是紧挨着的下面盘子移动次数的二倍，因为移动过程如下：
【注：柱子A、B、C，紧挨着的两盘子：上方盘子 i ，下方盘子 j 】
①：i 以上的盘子A移到C。
②：i 从A移到B。
③：i 以上的盘子C移到B。
④：j 从A移到C。
⑤：i 以上的盘子B移到A。
⑥：i 从B移到C。
⑦：i 以上的盘子A移到C。
然后天空飘来五个字，AC不是事。
AC代码：
#include <iostream>using namespace std;int num,ans;long long f(int x)
{long long ans=1;int i;for(i=1;i<=x;i++)ans*=2;return ans;
}int main()
{int n,k,T;cin>>T;while(T--){cin>>n>>k;cout<<f(n-k)<<endl;}return 0;
}
AC截图：
这篇关于【递推】【DP】-HDU-1995-汉诺塔⑤的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
