月度归档:2009年10月

4-Hanoi-Tower

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

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

【输入格式 Input Format】
一个正整数n。(0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
int main()
{
       int n, m, s, t, i, j, flag;
       scanf("%d", &n);
 
       m = 1;
       s = 1;
       t = 2;
       flag = 0;
 
       for (i = 2; i <= n; i++)
       {
              if (flag == 1)
                     break;
 
              for (j = 1; j <= i; j++)
              {
                     s = (s + t) % 10000;
                     m++;
 
                     if (m == n)
                     {
                            printf("%d\n", s);
                            flag = 1;
                            break;
                     }
              }
              t = (t * 2) % 10000;
       }
       return 0;
}