Python之求斐波那契数列前n项

Dear 丶 2024-04-18 12:59 38阅读 0赞

### 文章目录 ###

*  2021-1-26更新
 *  前言
 *  解法
 *   *  1、暴力递归
     *  2、优化1：备忘录递归解法
     *  3、优化2：动态规划数组迭代法
     *  4、优化3：动态规划双变量交替法
 *  写在最后

时间复杂度为O(1)，空间复杂度为O(1)的最优解：

def fibo(n):
    	# 定义交替变量
    	a, b = 0, 1
    	for i in range(n):
    		# 打印变量
    		print(a,end='\t')
    		# 像走路一样，变量交替行进
    		a,b = b, a + b
    		
    n = eval(input("请输入一个整数："))
    print('斐波那契前n项'.center(20,'-'))
    fibo(n)

运行截图：  
![在这里插入图片描述][20190906220656826.png]

--------------------

# 2021-1-26更新 #

# 前言 #

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契以兔子繁殖示例引入，又称为“兔子数列”，指的是这样的数列：0、1、1、2、3、5、8、13、21、34、……在数学上的定义为：\**F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2) (n >= 2, n∈N*)\*\*斐波那契数列应用于现代物理、准晶体结构、化学等领域……（参考：[百度百科——斐波那契数列][Link 1]）

# 解法 #

## 1、暴力递归 ##

在计算机领域中，斐波那契数列作为一道经典的算法题，自然是必须了解的，最简单、最常见的做法便是**递归**：

def fibo(n):
        if n == 1 or n == 2:
            return 1;
        else:
            return fibo(n - 1) + fibo(n - 2)

学校老师在讲解递归时通常也举此例，递归解法虽然简洁易懂，但有个很大的问题，时间复杂度特别地高！递归算法的时间复杂度计算方法：子问题个数乘以解决一个子问题需要的时间。

斐波那契数列中一个问题分成两个相等规模的子问题，显然子问题的个数为O(2^n)，而解决一个子问题的时间只有一个操作：fibo(n - 1) + fibo(n - 2)，时间为O(1)，因此，该复杂度为O(2 ^n)，指数级。贴一张图感受一下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70_pic_center]  
求F(10)和F(30)、F(30)和F(39)分别差了两个数量级！这是因为递归存在大量的重复计算，也就是重叠子问题。测试代码见下方：

from time import perf_counter
    
    def fibo(n):
    	……
    	
    x = eval(input())
    start = perf_counter()
    print("第{0}项是：{1}".format(x, fibo(x)))
    print("运行时间是：{:.5f}s".format(perf_counter() - start))

## 2、优化1：备忘录递归解法 ##

原始的递归解法之所以耗时，是因为重复计算，存在重叠子问题。因此，可以使用一个字典，将计算过的问题记下来，遇到下一个问题时先“翻阅”\[备忘录\]，如果时解决过的问题，直接将答案拎出来即可。

def fibo(n):
        if n < 1:
            return 0;
    	# 初始化备忘录为0
        memo = [0 for i in range(0, n + 1)]
        return helper(memo, n)
    
    def helper(memo, n):
    	# base case（基例）
        if n == 1 or n == 2:
            return 1
    	# 重叠子问题（已经计算）
        if memo[n] != 0:
            return memo[n]
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2)
        return memo[n]
    
    print(fibo(10))

其中`[0 for i in range(0, n + 1)]`为列表生成式，共有n+1的元素，实际上只需n长度即可，由于python列表元素下标从0开始，而又需要用到n下标，所以必须是range(0, n+1)。使用了备忘录的递归算法的不存在冗余计算，子问题数量与输入规模成正比，为O(n)，效率与动态规划相差无几，由于是从上往下推，因此这种方法又叫做自顶向下（memo\[n\] = helper(memo, n - 1) + helper(memo, n - 2)）。

## 3、优化2：动态规划数组迭代法 ##

与备忘录相反的方法是自底向上，从已知条件出发，一步步往后推：F(1) + F(2) = F(3)，……，直到推出目标结果，不需要递归，直接由循环完成计算。

def fibo(n):
        if n < 1:
            return 0
        if n == 1 or n == 2:
            return 1
        dp = [i for i in range(0, n + 1)]
        dp[1] = dp[2] = 1
        for i in dp[3:n+1]:
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

这种解法与备忘录不同在于方法层面，也就是求解的方向不同。复杂度都一样，为T(1)、S(n)。其中`dp[i] = dp[i - 1] + dp[i - 2]`也被叫做**状态转移方程**。

## 4、优化3：动态规划双变量交替法 ##

由Fibonacci 数列的数学公式可以发现，关键变量只有两个状态：F(n) = F(n -1) + F(n -2)；因此可以使用变量代替数组，将空间进一步压缩。

def fibo(n):
        if n < 1:
            return 0
        if n == 1 or n == 2:
            return 1
        prev = curr = 1;
        for i in range(3, n + 1):
            tmp = prev + curr
            prev = curr
            curr = tmp
        return curr

当然，由于python语法特性，可以省略临时变量tmp，同样，如果不考虑n<1的情况，代码可以简写为如下形式：

def fibo(n):
        if n == 1 or n == 2:
            return 1
        prev = curr = 1;
        for i in range(3, n + 1):
            prev, curr = curr, prev + curr
        return curr

这种将空间复杂度降低的方法叫做**状态压缩**，经过优化后的复杂度达到了O(1)！由于斐波那契数列并不存在求最值问题，严格来说并不能称为动态规划问题，以上解法是用动态求解的思想解决的重叠子问题，非常值得学习！

# 写在最后 #

青蛙跳台阶也是一种斐波那契数列（形似），学完后就可以去Leetcode刷题啦，传送门：

1.  509. 斐波那契数
2.  剑指 Offer 10- II. 青蛙跳台阶问题

本期斐波那契数列就介绍到这里啦，我是严光君，咱们下期再见~  
  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70_pic_center 1]  
`创造不易，少侠请留步…… 动起可爱的双手，点个赞再走呗~ ٩(๑>◡<๑)۶`

[20190906220656826.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7b058b8621b9418f8d1df9caea0ba4f0.png
[Link 1]: https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7611d0966879432daf3a8fef1d96bed1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTEwOTg1_size_16_color_FFFFFF_t_70_pic_center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4480030552774945a2458eafcc63ad7b.jpg