Fibonacci数列

Fibonacci数列

Fibonacci数列是一个很常见的递推数列，也称"兔子数列"。Fibonacci数列中蕴含很多信息，比如"黄金分割"就蕴含在Fibonacci数列中。
**

一.递推公式

$$\begin{array}{l}{F}_0=0\\ F_1=1\\ F_n=F_{n-1}+F_{n-2}(\mathrm{n}\ge 2)\end{array}$$

斐波那契数：0,1,1,2,3,5,8,13,21,34,55,89,144,233,…
**
特别指出：0不是第一项，而是第零项
**

当n趋于无穷大时，相邻两个数的比值$$F(n)/F(n-1)->0.6180339887...$$这就是著名的黄金分割数。

二.计算Fibonacci数列

两个问题：

1. 如何更快地计算第n个Fibonacci数列
2. Fibonacci数增长太快了，需要处理大数

链接：面试题10- I. 斐波那契数列

1.递归方式

class Solution:

    def fib(self,n):
        """
        :param n: int
        :return: int
        """
        
        if n==0:
            return 0
        
        if n==1:
            return 1
        
        return self.fib(n-1)+self.fib(n-2)

2.记忆化递归

图片链接：链接

class Solution:

    def fib(self,n):

        if n==0 or n==1:
            return n

        nums = [-1]*(n+1)
        nums[0]=0
        nums[1]=1

        def helper(n,nums):

            if nums[n]>=0:
                return nums[n]

            nums[n]=helper(n-1,nums)+helper(n-2,nums)

            return nums[n]

        helper(n,nums)

        return nums[n]

3.动态规划

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

以下两种方法可以参考：斐波那契数列

4.初等代数解法

5.线性代数(矩阵)

以上两种解法的结果都是一样的，使用：

$$F_n=\frac{\sqrt{5}}{5}\cdot \left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right]$$

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# author:LQ6H


class Solution:
    def Fib(self,n):

        import math

        if n==0 or n==1:
            return n

        a = math.sqrt(5)

        res = a/5*(((1+a)/2)**n-((1-a)/2)**n)

        return int(res)%1000000007

三.应用模型

两个常见的例子：

1. 楼梯问题
   :::info
   有一楼梯共N级，刚开始人在第一级，若每次只能跨上一级或两级，要走上第N级，共有多少种走法？
   :::
   **
   :::info
   假设到第n级总共的走法为F(n)。如何到达第n级？可以分成两种情况：

2. 第一次跳1级，剩下n-1个台阶，跳法是F(n-1)

3. 第一次跳2级，剩下n-2个台阶，跳法是F(n-2)

即：F(n)=F(n-1) + F(n-2)。这是一个Fibonacci数列
:::

题目链接：爬楼梯
**

2. 矩形覆盖问题
   :::info
   用2x1的小矩形覆盖2n个大矩形，总共有多少种方法？
   :::

:::info
假设方法总共有F(n)，分成两种情况：

1. 第一次放1格，剩下n-1个格子，方法有F(n-1)种
2. 第一次放2格，剩下n-2个格子，方法有F(n-2)种
   :::