10斐波那契数列&Python跳台阶问题汇总

本篇记录了斐波那契数列的Python实现：递归与循环两种解法，以及一些化用的题目。

Python实现

递归

按传统的递归方式，简洁、优雅。写出来却是 $O(n^2)$ 的算法

def fibo(n):
    """肥波那契函数"""
    if n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

$O(n)$ 的算法

上面“简洁”的算法其实重复算了好多项。比如算fibo(6)，它就算了三个fibo(3)、五个fibo(2)。从理论上分析，只要不多算，那就是 $O(n)$ 的算法——大约是算了n次fibo(n-1) + fibo(n-2)。

思路也很简洁：构建一个循环，在每次循环中，都有两个变量储存下一次循环的fibo(n-1)与fibo(n-2)。当然，循环开始和终止的边界条件是需要注意的。（拿几个数去试一试就行了）

def fibo(n):
    if n < 3:
        return 1
    frist = 1
    second = 1
    third = 1  # 没有这个会怎样？
    count = 3
    while count <= n:
        third = second + frist
        frist = second
        second = third
        count += 1
    return third

if __name__ == '__main__':
    print(fibo(2))  # 1
    print(fibo(6))  # 8

还有一种简洁的写法：

    """假设输入值为整数，第1项为零。"""
    a, b = 0, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return a

变体

跳台阶12

一个台阶总共有n级，如果一次可以跳一级或者两级，求总共有多少种跳法？

假设存在函数 $f$ ，使得 $f(n)$ 即为所求；
当台阶数 $n=0$ 和 $n=1$ 时， $f(n)=1$ （没有跳法是为一种跳法）；
当 $n\gt 1$ 时， $f(n) = f(n-1) + f(n-2)$ ；

看得出来是斐波那契数列吗？就用上面的算法就行了吗？检验一下，两级台阶的时候，总共2种跳法，写个测试，发现输出是1 ！= 2。。（好吧，肉眼可见）

def fibo(n):
    """假设输入值为整数"""
    [...]

def test_two():
    assert fibo(2) == 2  # error，1 ！= 2

怎么回事？分析得不对吗？原来，函数fibo(n)里的n=1代表第一种情况，而这里的第一种情况是台阶数n = 0。故可把输入改成fibo(n - 1)，或者把函数里的参数改一改。

跳台阶123

一个台阶总共有n级，如果一次可以跳一级、两级或者三级，求总共有多少种跳法？

改一下就好，理解不了就先用定义把写个代码：

def result123(n):
    """假设输入值为整数"""
    if n <= 1: return 1
    elif n == 2: return 2
    elif n == 3: return 4
    frist = 1
    second = 2
    third = 4
    for i in range(4, n + 1):
        result = frist + second + third
        frist = second
        second = third        
        third = result
    return result

if __name__ == '__main__':
    print(result123(2))  # 2
    print(result123(3))  # 4
    print(result123(4))  # 7
    print(result123(5))  # 13

跳台阶23

一个台阶总共有n级，如果一次可以跳两级或者三级，求总共有多少种跳法？

还是差不多，只是要从头分析。可以检验一下：

def result23(n):
    """假设输入值为整数"""
    if n <= 4: return 1
    elif n <= 6: return 2
    frist = 1  # n = 4
    second = 2  # n = 5
    third = 2  # n = 6
    for i in range(7, n + 1):
        result = frist + second
        frist = second
        second = third        
        third = result
    return result

if __name__ == '__main__':
    print(result23(4))  # 1
    print(result23(6))  # 2
    print(result23(7))  # 3
    print(result23(10))  # 7

跳台阶n

一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求总共有多少种跳法。

还是先分析：
$f(n) = f(n-1) + f(n-2) + \dots + f(1)\\f(n-1) = f(n-2) + f(n-3) + \dots + f(1)\\f(n)-f(n-1) = f(n-1)\\ f(n) = 2f(n-1)=2^{n-1}$

求个指数总会吧？

最后编辑于：2019.01.17 14:55:51