Sephiroth's boring days!!!

Love just for you.

四塔问题

 

【描述】

“汉诺塔”,是一个众所周知的古老游戏。现在我们把问题稍微改变一下:如果一共有4根柱子,而不是3根,那么至少需要移动盘子多少次,才能把所有的盘子从第1根柱子移动到第4根柱子上呢?

为了编程方便,您只需要输出这个结果mod 10000的值。

【输入】

一个正整数n。(0<n<=50000)

【输出】

一个正整数,表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。

【样例输入】

15

【样例输出】

129

【分析】

弄出前几个数,发现规律。

f[1]=1,之后分别是加2个2,加3个4,加4个8,加5个16……

  1: #include <stdio.h>
  2: #define maxn 50010
  3: 
  4: int a,b;
  5: int k=1,t;
  6: long long j=1;
  7: int n;
  8: 
  9: int main()
 10: {
 11:     freopen("hnoi.in","r",stdin);
 12:     freopen("hnoi.out","w",stdout);
 13:     
 14:     scanf("%d",&n);
 15:     b=1;
 16:     for (int i=2;i<=n;++i)
 17:     {
 18:         a=b;
 19:         if (!t)
 20:         {
 21:             t=++k;
 22:             j*=2;
 23:             j%=10000;
 24:         }
 25:         b=(a+j)%10000;
 26:         --t;
 27:     }
 28:     printf("%d\n",b);
 29:     return 0;
 30: }
 31: 

posted on 2010-09-02 11:27 Sephiroth Lee 阅读(77) 评论(0)  编辑 收藏 引用 所属分类: 信息奥赛


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


free counters