數(shù)據(jù)平移示例)

1、軟件課程設(shè)計軟件課程設(shè)計1 基礎(chǔ)題一基礎(chǔ)題一Fibonacci（斐波那契）數(shù)列）數(shù)列v1202年，意大利數(shù)學(xué)家斐波那年，意大利數(shù)學(xué)家斐波那契出版了他的契出版了他的，在書中第一次提到了著名的在書中第一次提到了著名的Fibonacci數(shù)列，定義如下：數(shù)列，定義如下： vf(1)=1,f(2)=1,f(n)=f(n-1)+f(n-2) n2 v現(xiàn)在我們的任務(wù)就是求出現(xiàn)在我們的任務(wù)就是求出Fibonacci數(shù)列的第數(shù)列的第n項。項。這是一個有趣的古典數(shù)學(xué)問題：有一對兔子，從出生后這是一個有趣的古典數(shù)學(xué)問題：有一對兔子，從出生后的第的第3個月起，每個月都生一對兔子。小兔子長到第個月起，每個月都生一對兔子

2、。小兔子長到第3個月后個月后每個月又生一對兔子。假設(shè)所有兔子都不死，問每個月的兔每個月又生一對兔子。假設(shè)所有兔子都不死，問每個月的兔子總數(shù)為多少對？子總數(shù)為多少對？ v可以看到每個月兔子的對數(shù)依次為：可以看到每個月兔子的對數(shù)依次為： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 。這就是。這就是Fibonacci數(shù)列數(shù)列。v怎么樣用怎么樣用c+程序來實驗這個序列？程序來實驗這個序列？v一設(shè)計要求一設(shè)計要求編程序，使用如下所謂的簡單變量編程序，使用如下所謂的簡單變量“數(shù)據(jù)平移數(shù)據(jù)平移”方法來方法來求出求出Fibonacci數(shù)列的第數(shù)列的第n項（的

3、具體項值）并顯示在屏項（的具體項值）并顯示在屏幕上（正整數(shù)幕上（正整數(shù)n通過鍵盤輸入）：說明變量通過鍵盤輸入）：說明變量old1=1，old2=1，newitem；新的；新的Fibonacci項項newitem總是總是“距距它最近它最近”的前兩項（的前兩項（old1與與old2）的累加和。而后通過）的累加和。而后通過“old1=old2; old2=newitem;”進(jìn)行所謂的進(jìn)行所謂的“數(shù)據(jù)平移數(shù)據(jù)平移”。接著計算另一個新的接著計算另一個新的Fibonacci項項newitem，依次循環(huán)，依次循環(huán)，直到求出數(shù)列的第直到求出數(shù)列的第n項時為止。項時為止。vFibonacci數(shù)列的計算公式如下：

4、數(shù)列的計算公式如下： fib（1） = 1；fib（2） = 1；fib（n） = fib（n-1） + fib（n-2）；）； /對大于等于對大于等于3的任意的任意nv這個數(shù)列有如下特點(diǎn)：這個數(shù)列有如下特點(diǎn)：第第1，2兩個數(shù)為兩個數(shù)為1，1。即。即fib（1） = 1；fib（2） = 1；從第從第3個數(shù)開始，該數(shù)是其前面兩個數(shù)之和。個數(shù)開始，該數(shù)是其前面兩個數(shù)之和。即：即： fib（n） = fib（n-1） + fib（n-2）；（）；（n=） 題中給出了幾個變量：題中給出了幾個變量：old1,old2,newnewitem, 其中其中old1和和old2的初始值都為，的初始值都為，ne

5、witem是新的是新的Fibonacci項，它的值為項，它的值為“距它最近距它最近”的前兩項（的前兩項（old1與與old2）的累加和。）的累加和。v可以列出：可以列出： newitem1=old1+old2, 初始變量初始變量 newitem1=old1+old2,經(jīng)過一次運(yùn)算，經(jīng)過一次運(yùn)算， 變量變量 newitem2=old2+newitem1，那么數(shù)列變成了，那么數(shù)列變成了old1,old2,newitem1,newitem2, 其中：其中：newitem1=old1+old2newitem2=old2+newitem1那么此時新產(chǎn)生的數(shù)列中原先的三個變量都已經(jīng)發(fā)生了那么此時新產(chǎn)生的數(shù)

6、列中原先的三個變量都已經(jīng)發(fā)生了變化，即：變化，即： old1=old2; old2=newitem1v比較：比較：newitem1=old1+old2newitem2=old2+newitem1原先的數(shù)列為原先的數(shù)列為old1,old2,newitem1運(yùn)算后的數(shù)列為運(yùn)算后的數(shù)列為old1,old2,newitem1,newitem2那么現(xiàn)在的數(shù)列中的那么現(xiàn)在的數(shù)列中的“old1”,“old2”分別被新數(shù)列中的分別被新數(shù)列中的“old2”,“newitem1”所代替，依此類推，以后的數(shù)列中的所代替，依此類推，以后的數(shù)列中的old1，old2都將在不斷的變換，如圖所示：都將在不斷的變換，如圖所示

7、：對對比比v newitem1=old1+old2 newitem2=old2+newitem1 newitem3=newitem1+newitem2 newitem4=newitem2+newitem3 (old1) (old2)數(shù)數(shù)據(jù)據(jù)平平移移fib（n） = fib（n-1） + fib（n-2）v可以看出，可以看出， Fibonacci（斐波那契）數(shù)列其實是一（斐波那契）數(shù)列其實是一個遞歸數(shù)列，我們編程時的主要算法就是運(yùn)用遞歸個遞歸數(shù)列，我們編程時的主要算法就是運(yùn)用遞歸的思想的思想v概要設(shè)計：概要設(shè)計：方法一：用以上所謂的簡單變量方法一：用以上所謂的簡單變量“數(shù)據(jù)平移數(shù)據(jù)平移”方法來方

8、法來求出求出Fibonacci數(shù)列的第數(shù)列的第n項。項。即用即用old1=old2; old2=newItem;進(jìn)行進(jìn)行“數(shù)據(jù)平移數(shù)據(jù)平移”。方法二：用遞歸算法實現(xiàn)求出方法二：用遞歸算法實現(xiàn)求出Fibonacci數(shù)列的第數(shù)列的第n項。項。我們現(xiàn)在用方法二即遞歸算法來求出我們現(xiàn)在用方法二即遞歸算法來求出Fibonacci數(shù)列的第數(shù)列的第n項項v二詳細(xì)設(shè)計與編碼：二詳細(xì)設(shè)計與編碼：#include long int fun(int a)void main()if(a=1|a=2)return 1;else return fun(a-1)+fun(a-2);int n;cout請輸入要求出的請輸入要

9、求出的Fibonacci數(shù)列的第數(shù)列的第n項（項（大于大于等于等于3的任意整數(shù)，最好比較小的任意整數(shù)，最好比較小）：）：n;coutfun(n)48，實驗時結(jié)果可能會產(chǎn)生溢出，實驗時結(jié)果可能會產(chǎn)生溢出#includeint fun(int a)if(a=1|a=2)return 1;elseint old1=1;int old2=1;int newItem;for(int i=1;ia-1;i+)newItem=old1+old2;old1=old2;old2=newItem;vreturn newItem;vvvvoid main()vvint n;vcout請輸入要求出的請輸入要求出的Fi

10、bonacci數(shù)列的第數(shù)列的第n項（大于等于項（大于等于3的任意整數(shù)，最好比較?。旱娜我庹麛?shù)，最好比較?。簄;vint m=fun(n);vcoutmendl;v五生活中有關(guān)五生活中有關(guān)Fibonacci數(shù)列的實例數(shù)列的實例v從某一葉子開始，使其位從某一葉子開始，使其位置對著自己，然后向上尋置對著自己，然后向上尋找第二片亦對著自己的葉找第二片亦對著自己的葉子，若數(shù)一數(shù)那兩片葉子子，若數(shù)一數(shù)那兩片葉子之間的其它葉子數(shù)目，這之間的其它葉子數(shù)目，這必定是費(fèi)布納西數(shù)列中的必定是費(fèi)布納西數(shù)列中的某一項。例如：在兩片同某一項。例如：在兩片同向的葉子之間有些相隔五向的葉子之間有些相隔五片，有些相隔八片，

11、有些片，有些相隔八片，有些相隔十三片等等。相隔十三片等等。 v在兩片同向的葉子之間有在兩片同向的葉子之間有些相隔五片些相隔五片,有些相隔八片，有些相隔八片，有些相隔十三片等等有些相隔十三片等等 .必定是必定是Fibonacci數(shù)列中數(shù)列中的某一項。的某一項。 v花瓣的數(shù)目花瓣的數(shù)目 你對植物稍曾注意，會發(fā)現(xiàn)大多數(shù)花朵的花瓣數(shù)目是你對植物稍曾注意，會發(fā)現(xiàn)大多數(shù)花朵的花瓣數(shù)目是3，5，8，13，21，34，55，89， 例如百合花是三瓣，梅例如百合花是三瓣，梅花五瓣，飛燕草八瓣，孤挺花十三瓣。向日葵不是花五瓣，飛燕草八瓣，孤挺花十三瓣。向日葵不是21瓣，就瓣，就是是34瓣。雛菊都是瓣。雛菊都是34，55，或，或89瓣。其它數(shù)目則鮮少出現(xiàn)。瓣。其它數(shù)目則鮮少出現(xiàn)。這個數(shù)列這個數(shù)列(3,5,8,13,21,34,55,89,)有個模式，非常有趣。有個模式，非常有趣?？吹交ò攴倍嗫吹交ò攴倍?多過一百瓣多過一百瓣)的花朵，你不妨數(shù)數(shù)看，保的花朵，你不妨數(shù)數(shù)看，保證不是證不是144瓣，就是瓣，就是233瓣。