走台阶
小明上台阶，每次可以走1个台阶或2个台阶，请问上到n层台阶总共有多少种走法？
先用递归的算法：
台阶数 | 上到最高层台阶的方法 | 几种走法 | 规律 | |
1 | 1 | 1 | ||
2 | 1+1 2 | 2 | ||
3 | 1+1+1 1+2 2+1 | 3 | 3=2+1 | |
4 | 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 | 5 | 5=3+2 | |
5 | 1+1+1+1+1 1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1 2+2+1 2+1+2 1+2+2 | 8 | 8=5+3 | f(n) = f(n-1)+f(n-2) |
递归算法总结：
1.找到不规律的部分，写成 if... return
2.找到 f(n)和 f(n-1)或者f(n-1) 以及f(n-2)的关系 即最后一个和前面一个或两个或更多个的关系
递推算法：
1 | 1 | a |
2 | 2 | b a |
3 | 3 | b(a+b) a |
4 | 5 | b(a+b) a |
5 | 8 | b(a+b) |
for i in range(3,n+1):
c = a+b
a = b
b = c
递推算法总结：
写循环：
后面的 和 前面一个或者几个的关系 如 c=a+b
然后a,b是如何变化的 如 a = b b = c
算法心得：
| 留言与评论（共有 0 条评论） “” |
