算法设计中的台阶问题

ITHJF

某人上台阶，他一步可迈一个台阶，两个台阶或三个台阶，共有n个台阶，编程输出他所有可能上法。
例如n=4时，则有（1 1 1 1）、（1 1 2）、（1 2 1）、（1 3）、（2 1 1）、（2 2）、（3 1）等7种不同的上法。
要求可以输入不同的n值，输出不同的结果。

ypxing

编译后运行 ./a.out 4即可

1. 
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. 
   
5. void func(int *status, int count, int deep)
   
6. {
   
7.   int i;
   
8.   if (count<=0)
   
9.   {
   
10.     if (count == 0)
    
11.     {
    
12.       for (i=0;i<deep;i++)
    
13.         printf("%d ", *(status+i));
    
14.       printf("\n");
    
15.     }
    
16.   }
    
17.   else
    
18.   {
    
19.     for (i=0;i<3;i++)
    
20.     {
    
21.       *(status+deep) = i+1;
    
22.       func(status, count-(i+1), deep+1);
    
23.     }
    
24.    
    
25.   }
    
26.   
    
27.   
    
28. }
    
29. 
    
30. 
    
31. int main(int argc, char *argv[])
    
32. {
    
33.   int i, *status;
    
34.   if (argc<2)
    
35. {
    
36.     printf("too few arguments.\n");
    
37.     return -1;
    
38. }
    
39.   i = atoi(argv[1]);
    
40.   status = (int*)malloc(sizeof(int)*i);
    
41.   func(status, i, 0);
    
42.   free(status);
    
43.   return 0;
    
44. }
    
45. 
    

复制代码

原帖由 ITHJF 于 2007-8-21 11:23 发表
某人上台阶，他一步可迈一个台阶，两个台阶或三个台阶，共有n个台阶，编程输出他所有可能上法。
例如n=4时，则有（1 1 1 1）、（1 1 2）、（1 2 1）、（1 3）、（2 1 1）、（2 2）、（3 1）等7种不同的上法。
...

[ 本帖最后由 ypxing 于 2007-8-21 12:43 编辑 ]

ITHJF

谢谢

tyc611

当初一个复试的上机题

ypxing

考研复试?

BTW. LZ还没有给俺加分呢

原帖由 tyc611 于 2007-8-21 22:46 发表
当初一个复试的上机题

daly88

动态规划问题吧。第N级楼梯可由第N-1级楼梯跨一步，N-2级楼梯跨2步，N-3级楼梯跨3步组成。
int countStep(int n)
{   
  int i;     
int step[1000];    //不超过1000级楼梯   
step[0] = 1;   
step[1] = 2;   
step[2] = 4;   
  for(i=3; i<n; j++)     {      
    step[ i ] = step[ i-1 ] + step[ i-2 ] + step[ i-3 ];   
  }   
return step[n-1];
}

[ 本帖最后由 daly88 于 2007-8-22 12:49 编辑 ]

ypxing

这个可以用动态规划吗?
似乎不是求最优解呀,而是遍历所有解

贴一下你的完整代码吧

原帖由 daly88 于 2007-8-22 12:44 发表
动态规划问题吧。第N级楼梯可由第N-1级楼梯跨一步，N-2级楼梯跨2步，N-3级楼梯跨3步组成。
int countStep(int n)
{   
  int i;     
int step[1000];    //不超过1000级楼梯   
step[0] = 1;   
st ...

ivhb

不一样吧。人家要得是所有可能的组合。
N阶可能是由 N-3阶+1+1+1, 或者N-3 + 1 + 2

daly88

N-2 + 2, N-3+3 , N-1+1，由于N-1是通过N-2,N-3计算的，所以已包含了前面的结果了。
找个数验证一下就知道了。

求解用了动态规划的思想，但这题不是求最优解。如果加上判断大小，就可以知道最少步数了。
当然这题中只有1，2，3步，求最少步数用贪婪更好。但贪婪不总是能够通。
例如步数变为1, 4, 5三种，走8级，贪婪就不是最优了。