斐波那契数列的两种解法：１.递归２.字典

爱被打了一巴掌 2022-12-24 10:59 108阅读 0赞

１.递归求解斐波那契数列数列

def fbnq(n):
        if n ==0:
            return 0
        elif n ==1:
            return 1
        else:
            return fbnq(n-2) + fbnq(n-1)
    dic={ }
    for n in range(30):
        dic[n] = fbnq(n)
    print(dic)

\{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811, 29: 514229\}

２.解决斐波那契数列用到了递归的思想，缺点就是时间开销和空间开销比较大，因为每一个数字都重复计算了很多次，解决方法是把计算出来的数值保存到字典当中，避免重复计算，下面贴出代码。

def fbnq(n):
        dic = { 0: 0, 1: 1}
        if n in dic:
            return dic[n]
        else:
            for i in range(2,n+1):
                dic[i] = dic[i-2] + dic[i-1]
        return dic
    print(fbnq(30))

\{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811, 29: 514229, 30: 832040\}

发表评论取消回复

表情：

评论列表（有 0 条评论，108人围观）

还没有评论，来说两句吧...

相关阅读

相关斐波那契数列的两种创建方式（递归和循环）

两种创建斐波那契数列的方式递归方式开始创建时间复杂度 O(2 ^ n)：以循环方式创建时间复杂度 O(n) 下面请看第一种：

今天药忘吃喽~/ 2023年02月23日 08:52/ 0 赞/ 21 阅读

相关斐波那契数列的递归算法与非递归算法

一、斐波那契数列由于斐波纳挈数列是以兔子的繁殖引入的，因此也叫“兔子数列”。它指的是这样一个数列：0,1,1,2,3,5,8,13......从这组数可以很明显看出这样一个

￡神魔★判官ぃ/ 2023年02月21日 06:58/ 0 赞/ 34 阅读

相关斐波那契数列的两种解法：１.递归２.字典

１.递归求解斐波那契数列数列 def fbnq(n): if n ==0: return 0 elif n =

爱被打了一巴掌/ 2022年12月24日 10:59/ 0 赞/ 109 阅读

相关递归的概念，阶乘，斐波那契列数：

9 递归的概述：求5的阶乘。5！ = 5\4\3\2\1；//120 递归：把大问题拆成很多的小问题，然后再把小问题拆成更多的小问题。当我们把很多小问题解决了，那么小

约定不等于承诺〃/ 2022年06月06日 01:47/ 0 赞/ 173 阅读

相关 C语言经典算法（八）——递归实现斐波那契数列的两种方法

后继续整理算法并写出自己的理解和备注。 C++实现的：递归实现斐波那契数列 1、递归实现斐波那契数列Fib(n) <1> 题目描述:输入n值，求解第n项的斐波那契数列值

快来打我*/ 2022年06月02日 06:10/ 0 赞/ 178 阅读

相关递归求斐波那契数列的兔子问题

package gxx20; import java.util.Scanner; //斐波那契数列：第n个月有m只兔子 //1,1,2,3,

快来打我*/ 2022年05月29日 06:27/ 0 赞/ 192 阅读

相关算法斐波那契数列的递归

做一个豁达而努力的自己。斐波那契数列的数学函数定义： ![20180330174703571][] 用递归的代码实现： include <iostrea

桃扇骨/ 2022年05月28日 06:07/ 0 赞/ 169 阅读

相关 javascript 递归实现斐波那契数

斐波那契： 1 1 2 3 5 8 ..... 特点：后面的数等于前面两个数之和，即 f

我会带着你远行/ 2022年05月28日 05:28/ 0 赞/ 202 阅读

相关【10】斐波那契数列的循环和递归实现

面试题10：斐波那契数列【0】目录：【1】题目【2】分析【3】测试代码【4】测试结果【5】算法优劣分析【1】题目：写一个函数

浅浅的花香味﹌/ 2022年05月27日 09:24/ 0 赞/ 193 阅读

相关斐波那契_尾递归

(1)计算任意数n的阶乘 5! 54321 8! 87654321 ''' 递归函数通过两个条件出发回的过程: (1) 当

悠悠/ 2021年11月13日 18:50/ 0 赞/ 314 阅读