算法与Python

算法与Python 知识量:10 - 40 - 100

8.1 爬楼梯问题><

问题- 8.1.1 -

小源家住在二楼,每次回家都需要经过一个有10层台阶的楼梯。小源每次可以选择一步走一级台阶或者一步走两级台阶。请计算他从楼下到家一共有多少种走法。

问题求解- 8.1.2 -

这是一个经典的斐波那契数列问题,可以使用动态规划来解决。

可以定义两个变量,f0 和 f1,分别表示走0层和1层台阶的走法数量。根据题目,f0 = 1, f1 = 2。然后使用一个循环来计算走2层到10层台阶的走法数量。

在每一层台阶上,小明有两种选择:从上一层走一步上来,或者从上两层走两步上来。所以,对于第n层台阶,走法数量 fn = fn-1 + fn-2。

最后,返回f10,即走10层台阶的走法数量。

下面是使用Python实现的代码:

def count_ways(n):  
    if n == 0:  
        return 1  
    elif n == 1:  
        return 2  
    else:  
        f0, f1 = 1, 2  
        for i in range(2, n + 1):  
            fn = f0 + f1  
            f0, f1 = f1, fn  
        return fn  
  
print(count_ways(10))  # 输出:110