鱼C论坛

 找回密码
 立即注册
查看: 2828|回复: 1

[技术交流] 032:汉诺塔III

[复制链接]
发表于 2018-2-17 14:26:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面。现在我们改变游戏的玩法,不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到下盘的上面。Daisy已经做过原来的汉诺塔问题和汉诺塔II,但碰到这个问题时,她想了很久都不能解决,现在请你帮助她。现在有N个圆盘,她至少多少次移动才能把这些圆盘从最左边移到最右边?
输入:
包含多组数据,每次输入一个N值(1<=N=35)。
输出:
对于每组数据,输出移动最小的次数。
样例输入:
1
3
12
样例输出:
2
26
531440

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-2-17 14:27:17 | 显示全部楼层
若移动k个圆盘从第一根柱子到第三根柱子需要Fun(k)次移动,那么,先移动K-1个圆盘道第三根柱子需要Fun(k-1)次移动,再将最大的圆盘移动到中间柱子需要1次移动,然后将k-1个圆盘移动回第一根柱子同样需要Fun(k-1)次移动,移动最大的盘子到第三根柱子需要1次移动,最后将k-1个圆盘也移动到第三根柱子需要Fun(k-1)次移动,这样递归公式就是Fun(k)=3*Fun(k-1)+2。而递归的出口是k=1时,F(1)=2

  1. #include<cstdio>
  2. #include<cstring>

  3. long long F(int num)
  4. {
  5.         if(num==1)
  6.                 return 2;
  7.         else
  8.                 return 3*F(num-1)+2;
  9. }
  10. int main()
  11. {
  12.         int n;
  13.         while(scanf("%d",&n)!=EOF)
  14.         {
  15.                 printf("%lld\n",F(n));
  16.         }
  17. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 19:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表