本文共 13060 字，大约阅读时间需要 43 分钟。

斐波那契数列

1. 介绍

    斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：

$F(0)=0，F(1)=1,F(n)=F(n-1)+F(n-2)（n\ge 3，n\in N\ast ）$

2. 思路

$F(n)=F(n-1)+F(n-2)$其实就是在不断调用自身，只不过变量不一样了而已，而且这是有结束条件的，即当n=1时，就可以停止，所以，这里我们可以考虑用递归来做！

关于递归的介绍，有兴趣的读者可以去看看我的这篇博客:

3. 代码

3.1 代码

思路中可以用递归，那我们就用递归实现一下:

'''TOPIC: 用递归计算斐波那契数列author: Bluetime: 2020-08-19QQ: 2458682080'''# 递归求斐波那契数列的第n项def fibnacci(n):    # 结束条件    # 这里为什么当n=2也是结束条件呢？    # 因为n=0时，f(0)=0;n=1时，f(1)=1;所以n=2时，f(2)=f(0)+f(1)=1.当然，你就像让n=1时再停止也可以。    if n == 1 or n == 2:        return 1    # 调用自己    else:        return fibnacci(n - 1) + fibnacci(n - 2)# 调用一下，求个n=5的结果print(fibnacci(20))

答案是5

3.2 代码分析

我们来分析一下刚才上面代码的运行过程:

第一步: 计算f(5)，f(5) = f(4) + f(3) 第二步: 计算f(4)和f(3)，f(4) = f(3) + f(2) ，f(3) = f(2) + f(1) 第三步: 计算f(3) 、f(2) 、f(0) 、 f(1) ，f(3) = f(2) + f(1)，f(2) = f(1) + f(0) 最后一步: f(0) = f(1) = 1 最后可以发现: $f(5)=f(4)+f(3)$          $=f(3)+f(2)+f(2)+f(1)$          $=f(2)+f(1)+f(1)+f(0)+f(1)+f(0)+f(1)$          $=f(1)+f(0)+f(1)+f(1)+f(0)+f(1)+f(0)+f(1)$ 可以发现算f(5)的时候，先同时算f(4)和f(3)，算f(5)的f(4)的时候又要算一次f(3)即相同的问题算了好多遍 所以递归效率低——递归会重复计算子问题

4. 思路改进

那我们想个办法，把已经算过的值，储存起来，这样要用的时候，调用一下，是不是每次就不用重新算了，这样就大大增加效率！

引出今天的主题: 动态规划(DP)的思想 = 最优子结构(递推式) + 重复子问题

5. 代码改进

# 非递归求斐波那契数列def fibnacci_no_recurision(n):    # 还是当n=2时停止    f = [0, 1, 1]    if n > 2:        for i in range(n - 2):            # 根据递推式所得，把每个求出来的结果放在列表里，每次计算，只要取出列表最后两个进行相加就好！            num = f[-1] + f[-2]            f.append(num)    return f[n]# 调用一下，求个n=50的结果print(fibnacci_no_recurision(50))

结果为:12586269025

同时调用一下两个函数，并求n=35，为什么只求n=35呢？不求个n=100、1000呢？因为我发现递归方法当n>40时，就需要等待很久，所以为了节省时间，我取了n=35.并且还记录了两个函数的运行时间:

s = time.time()print(fibnacci(35))e = time.time()s1 = time.time()print(fibnacci_no_recurision(35))e1 = time.time()print(e-s)print(e1-s1)

结果为:

922746592274653.0014479160308840.0

可以看到结果都一样，但是递归方法需要运行3.001447916030884

秒，而动态规划所用的非递归方法瞬间就出来了！！ 我在用非递归方法求个50000:

s1 = time.time()print(fibnacci_no_recurision(50000))e1 = time.time()

结果为:

10777734893072974780279038855119480829625106769411579784902309210032744735364652304984884440204760298493194332832740549533075398173304830674148353871755545405198446200873464249380723258213016701908119882516186149595860854099373751065304487446378299685138932566366816331317320459189318988631355996126556155463897640305571514053979226012432273048290007169088637862067551770083226932808784986627405883653759375827450870474419297680883496131129712885928517675484841510325238514653349215282524590844666984111015871828873018945063113415156237982458936004175689957201265961576289909593557314021380296857653905570895358471126839623211953601897333881142381405152645937409271523265040595837508152137323684815932367284475751194675574645544221265422202756962839375367590591559554638785642568966671167614673848038014349098033214712655252451441525498320487349301660567688206687717599197444449359350886395080148005443314685565499363349941391430720896733195422137696645198550043060203665070030522917230418089342380519209534100071587298936033864576702431887096457989654137471646679065779362678661964577757572520152520684937150004609567185931421233419906262154598939330771320596137016373010876759996062556877066675916760914095778774516636682875387821974189963277342283010924769826268739285764905634800594103107675266962584166457877785074142207044411309144936684251959101769187614484643968699835405354287762534648795517562448621598174081264567742257528037538383998459337573962016024160688422725234871406764621530305862046251136114340424337987605786521179227686592471663544319879434638430039398908214535092629652339020593692386735252942061317505516258823577741140713588261257732122224150755748039980222142749487407992105723590846073217575107092302450405358217802990016835520896224784928216963899531014044324639764833681031661824548351448285723251650314665035984582673172119931733651458099361430083269895664075625073496408871923134229258901935448837447431797271534411027140658815205808000207038331489477688876491912177977809799255929873569642023906239834652778042633088219330516798838892952665041398253702877526319175896814622504849381000376147751883382348322186208958469375348695531491287216014177056273136430812889486131382191630252935023718191599642598082376340239449313320626054746122722795294263311646780881550956464994662455576497376848600537385049017342660397392483247166252335319648866947881427342764454190081843133112856345289982133669806520660934333650439715927246376704680563777189480017264709202691475630476904560611354492385920158547610835385227028321460581684063993649540405203123064296570439708188582181602873194739735428853493268738807025270393190140254250476749280036221571756063612215757715483071348898016484178054076827845670245315562416030118846952119012478936418489556604239542340602750863919005437145653073159742613761306773870118432485549093134828845103044688100236012123585426908351933368510637976436207782806271090319808395388212792644295497458622406795069064499393738682130450194937278786077589726815250138074765165676352639386872791823065238962934794218127752757670670808346612100600514497911937551941902727282646908375155877184726133943340055507316107591891969682958608568611270202726433744765944163485753555593506386458780751151016728432668393952953815166324634116914765274138852717336399798597714797012073824418623536888084311270707054435383939699916807298609976437873303612604520791793962156047837588579681607803769620053551053861013367005570304725938296000476827589046389460379954864215454663645913009073186929315570880890861955270519673195216564968790356212550867010425374047656886435834529325854954526563855782389420259841737017217268642518315942132152148876680135082597812483999462190873450166253687064231579160034961832282442216825886307554027744730063382571250538797947620074378298003853691717495927783973464863276390162187113718925956105807071527625813599532658976238885614311887840438444730525710554192235385969105373603521638735505604031533524991210855340120959780280399509670754839742302154328871736362475666236533808668644301651753663526108193224241612330921643127884071977280870320502424552960872740261492897281599282639371060272062474392032477054902119329804424877545848652367250362615039002729239996663732026197940813355745532722622246050208999925583740664109623632346190052793017847915649889627188525915798535140551873173727602252592783850325955338117235760688410030225328693898695125469912018606992508246994011523327023462156979379123399581755990614382599573885038974416472341712313892427647661396588478488650154542960647217285760555946637149127315054803258455565395329787110051423268421224180123835103996691990643643453550465807878903016148329702260410291082840214095082261007402618234936346914466175764642902091694923703314506636773093530282514655930401283571770522500272082715701624759588709830239510382378633174528274628374878310545296852419495509493002705583228820775946174932387789136739862121264878265127881402414763935436509599050446177263980732327372564004412894047568750820950252768771470720020689209058543955474910230746899526559882737546660795547221857686783391799172723114209031102617096729728204298764819184985285871383777015598892102145657159790789710552242588319468190281987083495289317956666736477135853264473788026558716248736920011332459964959795124916650178642244974010506601849459039240356803742181461947113676070131350289607822791580727038824599589447148875111345893718873602276619082723189396901123069748968588331749184799971204885072473458830955611565692911607733633116684175464536468816246208578135731805220674671407114821260621306999398566468244182672529792624521633837344117699300203675996000417830700966471695207104309845307794042420674453673137387995532750246035651579444910511090706656014044399413037806518542097303663232360862438084278078367539574637285909040627338744505608337909073465249801787370766709391395521059773735449066916553911023749926430029145608718986332567098742145026049841988165873325268313006051818169404811205877692754034452489826374819163914085209777190260980185262643010687275800502768096517926517167781874174382571534626991244472495653951321575340984187412359527463198029486058056114562054301930335965793240522747001347549872355814382521404256096283876061105276247186654884537163882220646282420465301243860990665170294869760322311743565972879284227230624602887884933581471051415118436726925197039330793895962509407495195188880989256551359888857010340556087547872091095326694878623455428623953621983347385511935141265834030990718066422213098600677213976864397939977918748999115927903759371009591771701685725514906092130965769879394449113164911337897518105803830229838810220083060919543224096017183651299743931045269187655672787050047431095082340370002362036937888536613752505676229739873650960719226639112135756594074948215832759200554412806993379667746773240780439163495980251182499711778821818309498633761643078133966035202473091829017576417961897018676666446572212322538116861166909125126655931220884673957328824609842273006187306145506655171588227094231839976758592374993000335149848534188335760972195249120542422672582715984900509011539720602535062265746786706227296925749982968098625774672253126943770231083633344140943551909896676556944154671736557350437357392787765090983741782708455354063170050694920785764834782890109931862053077379666644767710989589011538754911826985503250005520013095120854328948832487031042825930442307542343906952726476602204673243559835004600726843153580727101211272853841367607853787831039179584119549764134869288210587595324238991903580842254930016270003530330520884837483349296933883763181362303716702033591966709448870361470630358292989008961436313300961900579142424806910519687110367513463869165131041074080042577050769704559105578587230755956069154449046996520591560039083745177402638501946454888891676883581643117706417617885564796376208582843491124863662970001133696686194801902141218281649681715727359370955277074180793896107464720568525569236986835108016637308964949243582544253507068862013378348697955507470973708042719933244661404888611822201291541623187269276889389692926455091049167900395801763523659550583244263422043001263125490305957606224958624126349910577201226962848407318812053548304469435939647541646635873621644087819439493948269419230665450132682272992307908167018341377386715633942570842741075484304617390111420898959269220256075764867563122062364760003202582214988657473078690660880075931727170588006310670760256942460891382746865673850922613623618778218658833579968123293930285888615311956755586386775355740372051346530191814647413943645086328863212378691447596137053726352401308962371789856453184357612933631378957881001288139989114510173099882783672791400569904868917706442538694807113519672970928242029848124088788804316093483661357223273057743001283652196719941249502185347584760105431016471834652334626021749925707301166131890116958371361963460103764014859524943035315457518073817035386721488886728576267964721624171533818466035293691680612158691069681335692987018630939743771880049628524298398463987863839029048794976828576106888266616227177226266222502777351380617439921398595646907822359279948154362791544225371385631516597782533568221055248864005027657816507218047641647462339162213993412962649182149256062045013743042778573425603296904711809004301142074918198558725792255252087056546692406314635362755264048302265899925443977115624488072982772428311999650761190436094787128526632348228828651932561131247320137755862125287560871024796087120431801164586270791982797777816137112912950952433917313462395832857336326596480156502869885150064689099206598475455101724276161762406517399169395045979824965215912561332126467478511958374166434242929791014206047600954923198574490307276721573374356686311155903794505662865300805757807630608034828006420697935191642209749680654279524089079326599081023787152725232421700911366146841241587244979889103175286866434601053571819344469221094459994147683011042698769060387854175621161813213306708085932060538070206980718230633304686156292327050451964191480310597056280136081750093319142918858087519626054584746041942062572247536767423726292346776310542606854971917837866881978680521257617726404094951121557618826982236683815396821868676292629075572056751037324516475684294442369921249124048746428158068675080672445106451244419223433625181376458280337646120957199361973645564621492106335887030818230426659304936695376803722039703749078196901112665240202976183053642523735531250.14955782890319824

只用时0.14955782890319824秒！！！

为什么效率比递归快？因为我们把之前算过的都放在列表里，使用时直接取出来用就好了！

转载地址：http://gbiwi.baihongyu.com/