迭代算法（python递归与迭代:N级楼梯）

思考：N级楼梯,每次只能跨1或2级,走完这楼梯共有多少种走法？

解题思路：数学递推法

N级楼梯,每次只能跨1或2级,走法记为F(N)，下面用两种方法来求解F(N)

1、当N=1时，只有1级楼梯，故只能跨1级，只有1种走法，即F(1)=[(1)]=1

2、当N=2时，可以每次都只跨1级走完楼梯，或直接跨2级走完楼梯，故有2种走法，即F(2)=[(1,1),(2)]=2

3、当N>=3时，最后一步走法有两种情况：

情况1：若最后一步是跨1级，则是从N-1级楼梯直接跨1级走完楼梯的，故走完N-1级楼梯有多少种走法，这种情况就有多少种走法，有F(N-1)种走法。

情况2：若最后一步是跨2级，则是从N-2级楼梯直接跨2级走完楼梯的，故走完N-2级楼梯有多少种走法，这种情况就有多少种走法，有F(N-2)种走法。

所以，当N>=3时，共有走法：F(N)=F(n-1)+F(N-2)

递推过程

F(1)=1

F(2)=2

F(3)=F(2)+F(1)=2+1=3

F(4)=F(3)+F(2)=3+2=5

依此类推

F(N)=F(N-1)+F(N-2)

python代码实现：

（1）递归算法

import time print('n级楼梯,每次跨1级或2级,有多少种走法') ''' 1、递归算法 ''' def fun_recursive_algorithm(n): fn = 0 try: if n < 0: return fn elif n == 1: fn = 1 elif n == 2: fn = 2 elif n >= 3: fn = fun_recursive_algorithm(n-1) + fun_recursive_algorithm(n-2) except Exception as err: print('递归算法计算异常：' + str(err)) finally: return fn print('1、递归算法') for i in range(1, 50): start_time = time.time() # 开始运行时间 fn = fun_recursive_algorithm(i) end_time = time.time() # 运行结束时间 run_time = float(end_time-start_time)*1000 # 计算运行时间，即计算过程耗时（毫秒） print(f'{i}级楼梯,每次跨1级或2级,有{fn}种走法,递归算法耗时：{run_time} 毫秒')

递归算法运行结果如下：

递归算法运行结果

（2）迭代算法

import time print('n级楼梯,每次跨1级或2级,有多少种走法') ''' 2、迭代算法 ''' def fun_iterative_algorithm(n): fn = 0 # n级楼梯走法 fn_1 = 0 # n-1级楼梯走法 fn_2 = 0 # n-2级楼梯走法 try: for i in range(1, n+1): if i == 1: fn = 1 # n=1 级楼梯走法 elif i == 2: fn = 2 # n=2 级楼梯走法 fn_1 = 1 # n-1=1 级楼梯走法 elif i >= 3: fn_2 = fn_1 # 因为i+=1，所以本次的n-2 为上次的n-1 级楼梯走法 fn_1 = fn # 因为i+=1，所以本次的n-1 为上次的n 级楼梯走法 fn = fn_1 + fn_2 except Exception as err: print('迭代算法计算异常：' + str(err)) finally: return fn print('2、迭代算法') for i in range(1, 30): start_time = time.time() # 开始运行时间 fn = fun_iterative_algorithm(i) end_time = time.time() # 运行结束时间 run_time = float(end_time-start_time)*1000 # 计算运行时间，即计算过程耗时（毫秒） print(f'{i}级楼梯,每次跨1级或2级,有{fn}种走法,递归算法耗时：{run_time} 毫秒')

迭代算法运行结果如下：

迭代算法运行结果

大家可以通过这个案例来感受一下递归算法与迭代算法的区别。

思考题：

本题除了用上述数学中递推法来解题，你们还有什么方法可以解题吗？

个人感觉：其实这个问题用数学的组合方法也可以解题的，下一章，我将与各位一起探讨和使用数学中的组合方法来解题！！！