原题：

有一100阶层的楼梯，有三种走楼梯方式，一次走一阶，一次走两阶，一次走三阶。用算法实现，走完100阶总共有多少种走法

解答：

f(n)=f(n-1)+f(n-2)+f(n-3）

有两个要点：1，结果大于int32，需要用到高精度。 2，直接递归会有大量重复运算，需要缓存每一步的结果

 

1. #include "stdio.h" 
2.  
3. void addCache(char count[], char d[]); 
4. void reverse(int index); 
5. void lastMove(int stepOver); 
6.  
7. char result[100]; 
8. char cache[101][100]; 
9.  
10. void main() 
11. { 
12.     for (int i = 0; i < 101; i++) 
13.     { 
14.         cache[i][0] = 0; 
15.         for (int j = 1; j < 100; j++) 
16.         { 
17.             cache[i][j] = 0; 
18.         } 
19.     } 
20.     cache[0][0] = '0'; 
21.     cache[1][0] = '1'; 
22.     cache[2][0] = '2'; 
23.     cache[3][0] = '4'; 
24.  
25.     int floor = 100; 
26.     lastMove(floor); 
27.  
28.     reverse(floor); 
29.     printf("total: %s", result); 
30. } 
31.  
32. void lastMove(int stepOver) 
33. { 
34.     if (stepOver > 3) 
35.     { 
36.         for (int i = 1; i <= 3; i++) 
37.         { 
38.             int index = stepOver - i; 
39.             if (cache[index][0] == 0)//not cached 
40.             { 
41.                 lastMove(index); 
42.             } 
43.             addCache(cache[stepOver], cache[index]); 
44.         } 
45.          
46.     }  
47.     else 
48.     { 
49.         printf("error\n"); 
50.     } 
51. } 
52.  
53. void addCache(char count[], char d[]) 
54. { 
55.     int j = 0; 
56.     while (d[j] != 0) 
57.     { 
58.         int in = d[j] - '0'; 
59.         for (int i = j; i < 100; i++) 
60.         { 
61.             if (in == 0) 
62.             { 
63.                 break; 
64.             } 
65.             if (count[i] == '\0') 
66.             { 
67.                 count[i] = '0'; 
68.             } 
69.              
70.             int curNum = count[i] - '0' + in; 
71.             if (curNum > 9) 
72.             { 
73.                 in = curNum / 10; 
74.                 curNum -= in * 10; 
75.             } 
76.             else 
77.             { 
78.                 in = 0; 
79.             } 
80.             count[i] = curNum + '0'; 
81.         } 
82.          
83.         j++; 
84.     } 
85.      
86. } 
87.  
88. void reverse(int index) 
89. { 
90.     int length = 0; 
91.     for (int i = 0; i < 100; i++) 
92.     { 
93.         if (cache[index][i] == 0) 
94.         { 
95.             length = i; 
96.             break; 
97.         } 
98.     } 
99.      
100.     for (i = 0; i < length; i++) 
101.     { 
102.         result[length - 1 - i] = cache[index][i]; 
103.     } 
104.     result[length] = 0; 
105. } 

 

本文转自 dogegg250 51CTO博客，原文链接：http://blog.51cto.com/jianshusoft/620918，如需转载请自行联系原作者