首页 > 代码库 > HDU 2064 (递推) 汉诺塔III
HDU 2064 (递推) 汉诺塔III
将柱子从左到右依次编号为A、B、C
设将n个盘子从一端移动到另一端的最少步数为f(n)
则f(n)和f(n-1)的递推关系为：f(n) = 3 × f(n-1) + 2
初始状态A柱子上面有n个盘子，将上面的n-1个移到C柱子上需要f(n-1)，然后将最下面的盘子移动到B柱子1步
再将n-1个移回到A柱子上也需要f(n-1)，将最下面的盘子移到C柱子1步，最后将A柱子上的移到C上面f(n-1)
通项公式也很容易归纳出来：f(n) = 3n - 1
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 unsigned long long a[40]; 8 9 int main(void)10 {11 #ifdef LOCAL12 freopen("2064in.txt", "r", stdin);13 #endif14 15 a[0] = 0;16 for(int i = 1; i <= 35; ++i)17 a[i] = a[i - 1] * 3 + 2;18 int n;19 while(scanf("%d", &n) == 1)20 cout << a[n] << endl;21 return 0;22 }
HDU 2064 (递推) 汉诺塔III
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。