08《算法入門教程》遞歸算法之斐波那契數(shù)列

本節(jié)內(nèi)容是遞歸算法系列之一：斐波那契數(shù)列遞歸求解，主要介紹了斐波那契數(shù)列的定義，然后用遞歸的實(shí)現(xiàn)思想分析了一下斐波那契數(shù)列，最后給出了基于 Java 代碼應(yīng)用遞歸思想實(shí)現(xiàn)斐波那契數(shù)列的代碼實(shí)現(xiàn)及簡(jiǎn)單講解。

成都一家集口碑和實(shí)力的網(wǎng)站建設(shè)服務(wù)商，擁有專業(yè)的企業(yè)建站團(tuán)隊(duì)和靠譜的建站技術(shù)，十余年企業(yè)及個(gè)人網(wǎng)站建設(shè)經(jīng)驗(yàn) ,為成都超過千家客戶提供網(wǎng)頁設(shè)計(jì)制作,網(wǎng)站開發(fā),企業(yè)網(wǎng)站制作建設(shè)等服務(wù),包括成都營(yíng)銷型網(wǎng)站建設(shè)，高端網(wǎng)站設(shè)計(jì)，同時(shí)也為不同行業(yè)的客戶提供成都網(wǎng)站建設(shè)、做網(wǎng)站的服務(wù),包括成都電商型網(wǎng)站制作建設(shè),裝修行業(yè)網(wǎng)站制作建設(shè)，傳統(tǒng)機(jī)械行業(yè)網(wǎng)站建設(shè),傳統(tǒng)農(nóng)業(yè)行業(yè)網(wǎng)站制作建設(shè)。在成都做網(wǎng)站,選網(wǎng)站制作建設(shè)服務(wù)商就選創(chuàng)新互聯(lián)公司。

斐波那契數(shù)列（Fibonacci sequence），也稱之為黃金分割數(shù)列，由意大利數(shù)學(xué)家列昂納多?斐波那契（Leonardo Fibonacci）提出。斐波那契數(shù)列指的是這樣的一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……，這個(gè)數(shù)列從第 3 項(xiàng)開始，每一項(xiàng)都等于前面兩項(xiàng)之和。在數(shù)學(xué)上，斐波那契數(shù)列可以被遞推的方法定義如下：

斐波那契數(shù)列是數(shù)學(xué)上面一個(gè)經(jīng)典的例子，并且在日常生活中有很多應(yīng)用，他還與黃金分割有著密不可分的聯(lián)系，而且當(dāng) n 趨向于無窮大時(shí)，前一項(xiàng)與后一項(xiàng)的比值越來越逼近黃金分割值 0.618。

在這一節(jié)中，我們就需要利用遞歸的思想去求解斐波那契數(shù)列，當(dāng)給出一個(gè)斐波那契中第幾項(xiàng)的數(shù)字，然后求解出對(duì)應(yīng)的斐波那契數(shù)值。在之前，我們已經(jīng)定義了遞歸算法的相關(guān)概念，并且明確了需要應(yīng)用遞歸時(shí)候的三要素：

接下來，我們將利用遞歸的知識(shí)來解決斐波那契數(shù)列問題，明確在斐波那契數(shù)列求解問題中的遞歸三要素分別是什么。

例如，當(dāng)我們求解斐波那契數(shù)列中的 F (5) 時(shí)，按照定義，我們有：

在說明斐波那契數(shù)列的遞歸描述之后，我們看看如何用 Java 代碼來實(shí)現(xiàn)對(duì)斐波那契數(shù)列的計(jì)算。

運(yùn)行結(jié)果如下：

代碼中的第 4 行至第 8 行分別調(diào)用斐波那契數(shù)列計(jì)算函數(shù)，計(jì)算出斐波那契數(shù)列中對(duì)應(yīng) n=1,2,3,4,5 時(shí)斐波那契數(shù)列的取值，進(jìn)行結(jié)果比較，判斷斐波那契數(shù)列程序?qū)崿F(xiàn)是否正確。代碼中的第 12 行至第 20 行是斐波那契數(shù)列應(yīng)用遞歸方法進(jìn)行斐波那契數(shù)列的計(jì)算，按照遞歸的三要素進(jìn)行計(jì)算處理。

本節(jié)主要介紹了用遞歸思想求解斐波那契數(shù)列，在學(xué)完本節(jié)課程之后，我們了解到了什么是斐波那契數(shù)列，并且將遞歸算法在斐波那契數(shù)列中進(jìn)行了實(shí)際應(yīng)用，需要掌握斐波那契數(shù)列的遞歸求解方法，并自己可以實(shí)現(xiàn)相關(guān)的代碼實(shí)現(xiàn)，并清楚里面的每一步邏輯。

匯編實(shí)現(xiàn)斐波那契數(shù)列前30項(xiàng)（基于給出的程序修改）

算到第 25 項(xiàng)，就超出 16 位二進(jìn)制數(shù)了。

需要用到 32 位數(shù)的運(yùn)算方法。

樓主提供的這些程序，基本都不能用了。

必須重新編寫程序。

程序已經(jīng)編好，輸出如下：

……

28: 0514229

29: 0832040

30: 1346269

哪位高手能不能幫我用匯編語言編寫一個(gè)程序，就是表示出斐波那契數(shù)列的前20個(gè)數(shù)？

;剛剛寫好，呵呵，本人測(cè)試通過了，希望對(duì)您有幫助，為了方便你看，我加了些注釋，有問題可以問我...

ASSUME CS:CODE,DS:DATA

DATA SEGMENT

BUFF DB 10

DB ?

DB 10 DUP(?)

RESULT DW ?

RESULT_SHOW DB 10 DUP(?)

DATA ENDS

CODE SEGMENT

START:

MOV AX,DATA

MOV DS,AX

LEA DX,BUFF

MOV AH,0AH

INT 21H

MOV DI,0

L0: ;統(tǒng)計(jì)一共有多少個(gè)數(shù)字組成

CMP BYTE PTR DS:[DI+2],0DH

JZ GO

INC DI

JMP L0

GO: ;計(jì)算第n個(gè)斐波那契數(shù),把數(shù)字字符串轉(zhuǎn)換為十進(jìn)制數(shù)

MOV BL,10

MOV AX,1

MOV SI,DI ;為后面判斷輸入的是不是只輸入一個(gè)數(shù)有用

MOV CX,DI

L2: PUSH AX

SUB BYTE PTR DS:[DI+1],30H

MUL BYTE PTR DS:[DI+1]

ADD RESULT,AX

POP AX

MUL BL

DEC DI

LOOP L2

;分兩種情況：1.輸入的是1；2.輸入的不是1

CMP SI,1

JNZ L7

CMP BYTE PTR RESULT,1

JNZ L7

MOV AX,RESULT

JZ L4

L7: MOV AX,1

MOV BX,0

MOV CX,RESULT

DEC CX

L3: ;第n個(gè)斐波那契數(shù)存放到AX中

PUSH AX

ADD AX,BX

POP BX

LOOP L3

L4:

;顯示這個(gè)斐波那契數(shù)

MOV DX,0

LEA SI,RESULT_SHOW

MOV DI,0 ;利用DI來累計(jì)一共有多少個(gè)數(shù)字

L5:

MOV CX,10

CALL DIVDW

ADD CL,30H

MOV DS:[SI],CL

CMP AX,0

JZ L6

INC SI

INC DI

JMP L5

L6:

MOV DL,DS:[SI]

MOV AH,2

INT 21H

CMP DI,0

JZ OK

DEC SI

DEC DI

JMP L6

OK:

MOV AX,4C00H

INT 21H

;參數(shù)： (AX)=DWORD型低16位數(shù)據(jù)

; (DX)=DWORD型高16位數(shù)據(jù)

; (CX)=除數(shù)

;返回： (DX)=結(jié)果的高16位，(AX)=結(jié)果的低16位

; (CX)=余數(shù)

;32位除16位，可以防止溢出！

DIVDW: ;子程序定義開始,功能是分離各個(gè)數(shù)字出來

PUSH AX

MOV AX,DX

MOV DX,0

DIV CX

MOV BX,AX

POP AX

DIV CX

MOV CX,DX

MOV DX,BX

RET ;子程序定義結(jié)束

CODE ENDS

END START

go語言 使用遞歸與循環(huán)兩種方式計(jì)算斐波那契數(shù)列

給定一個(gè)正整數(shù)n計(jì)算出對(duì)應(yīng)斐波那契數(shù)列對(duì)應(yīng)的值

說明:

用mackbookpro i7 2.7GHZ筆記本進(jìn)行測(cè)試，結(jié)果如下:

備注: 當(dāng)n=80時(shí)，由于測(cè)試等待時(shí)間過長(zhǎng)，強(qiáng)制中斷了執(zhí)行。

從測(cè)試結(jié)果看出，當(dāng)n逐漸增大，遞歸方式計(jì)算斐波拉契數(shù)列的時(shí)間復(fù)雜性急劇增加。當(dāng)n值較大時(shí)可以考慮用循環(huán)方式代替。

類似的方式也可以用于，求階乘、遍歷目錄、漢諾塔等問題的解決。在后期的文章中，我將這些內(nèi)容進(jìn)行補(bǔ)充，敬請(qǐng)期待，謝謝。

Go語言 斐波那契數(shù)列的解法

這么寫效率很低，沒有剪枝，存在大量的重復(fù)計(jì)算。

反正你測(cè)試用例是有限的，那我騙過你的測(cè)試用例就行了??；)

網(wǎng)站名稱：go語言算斐波那契數(shù)列,實(shí)現(xiàn)斐波那契數(shù)列
轉(zhuǎn)載源于：http://chinadenli.net/article8/hegoop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、移動(dòng)網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站收錄、網(wǎng)站導(dǎo)航、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)