斐波那契求解迭代演算法

⑴ 求解一道Python編程題

斐波那契數列自第三個數開始，每個數均為之前兩個數的和。

至少有兩種方法來實現它。

最常見的利用迭代的方法，其核心思路是

fib(n) =fib(n-1) +fib(n-2)

而在n<2時直接，沒有n-2，因此直接返回1:

def fib(num): return 1 if n<2 else fib(num-1) + fib(num-2)

這是一種很簡單的實現。在階梯數不大時，它很好用。當階梯數很大時，因為二次手迭代，會比較慢。因此，可以在計算中保存中間值(1至n-1的階梯數)來減少計算量：

這種方式在計算階梯數10000時就可以保持不錯的性能。如果需要多次計算該數列,則可以利用對象來保持這個中間值列表，下列代碼中,Fibonaci實例只計算未曾計算的階梯數，在重復調用時它更具優勢：

class Fibonaci(object):

....history=[1, 1]

....def cacl(self, num):

........while len(self.history) <= num:

............self.history.append(self.history[-1] + self.history[-2])

........returnself.history[num]

if __name__ == '__main__':

....fib =Fibonaci()

....print(fib.calc(100))

....print(fib.calc(32))

....print(fib.calc(10000))

⑵ 哪個高手幫幫忙,急用!.

「斐波那契數列」的發明者，是義大利數學家列昂納多·斐波那契（Leonardo Fibonacci，生於公元1170年，卒於1240年。籍貫大概是比薩）。他被人稱作「比薩的列昂納多」。1202年，他撰寫了《珠算原理》(Liber Abaci)一書。他是第一個研究了印度和阿拉伯數學理論的歐洲人。他的父親被比薩的一家商業團體聘任為外交領事，派駐地點相當於今日的阿爾及利亞地區，列昂納多因此得以在一個阿拉伯老師的指導下研究數學。他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯研究數學。
斐波那契數列指的是這樣一個數列：1，1，2，3，5，8，13，21……
這個數列從第三項開始，每一項都等於前兩項之和。它的通項公式為：(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（又叫「比內公式」，是用無理數表示有理數的一個範例。）【√5表示根號5】
很有趣的是：這樣一個完全是自然數的數列，通項公式居然是用無理數來表達的。
[編輯本段]【該數列有很多奇妙的屬性】
比如：隨著數列項數的增加，前一項與後一項之比越逼近黃金分割0.6180339887……
如果你看到有這樣一個題目：某人把一個8*8的方格切成四塊，拼成一個5*13的長方形，故作驚訝地問你：為什麼64＝65？其實就是利用了斐波那契數列的這個性質：5、8、13正是數列中相鄰的三項，事實上前後兩塊的面積確實差1，只不過後面那個圖中有一條細長的狹縫，一般人不容易注意到。
5、-2.4、2.6、0.2、2.8、3、5.8、8.8、14.6……等，你將發現隨著數列的發展，前後兩項之比也越來越逼近黃金分割，且某一項的平方與前後兩項之積的差值也交替相差某個值。如果所有的數都要求是自然數，能找出被任意正整數整除的項的此類如果任意挑兩個數為起始，比如5、-2.4，然後兩項兩項地相加下去，形成數列，必然是斐波那契數列的某項開始每一項的倍數，如4,6,10,16,26……（從2開始每個數的兩倍）。
斐波那契數列的第n項同時也代表了集合{1,2,...,n}中所有不包含相鄰正整數的子集個數。
斐波那契數列（f(n)，f(0)=0，f(1)=1，f(2)=1，f(3)=2……）的其他性質：
1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1
2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)-1
3.f(0)+f(2)+f(4)+…+f(2n)=f(2n+1)-1
4.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)
5.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1
6.f(m+n)=f(m-1)·f(n-1)+f(m)·f(n)
7.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)
8.f(2n-1)=[f(n)]^2-[f(n-2)]^2
9.3f(n)=f(n+2)+f(n-2)
在楊輝三角中隱藏著斐波那契數列
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
……
過第一行的「1」向左下方做45度斜線，之後做直線的平行線，將每條直線所過的數加起來，即得一數列1、1、2、3、5、8……
（1）細察下列各種花，它們的花瓣的數目具有斐波那契數：延齡草、野玫瑰、南美血根草、大波斯菊、金鳳花、耬斗菜、百合花、蝴蝶花。
（2）細察以下花的類似花瓣部分，它們也具有斐波那契數：紫宛、大波斯菊、雛菊。
斐波那契數經常與花瓣的數目相結合：
3………………………百合和蝴蝶花
5………………………藍花耬斗菜、金鳳花、飛燕草
8………………………翠雀花
13………………………金盞草
21………………………紫宛
34，55，84……………雛菊
（3）斐波那契數還可以在植物的葉、枝、莖等排列中發現。例如，在樹木的枝幹上選一片葉子，記其為數0，然後依序點數葉子（假定沒有折損），直到到達與那息葉子正對的位置，則其間的葉子數多半是斐波那契數。葉子從一個位置到達下一個正對的位置稱為一個循回。葉子在一個循回中旋轉的圈數也是斐波那契數。在一個循回中葉子數與葉子旋轉圈數的比稱為葉序（源自希臘詞，意即葉子的排列）比。多數的葉序比呈現為斐波那契數的比。
（4）斐波那契數列與黃金比值
相繼的斐波那契數的比的數列：
它們交錯地或大於或小於黃金比的值。該數列的極限為。這種聯系暗示了無論（尤其在自然現象中）在哪裡出現黃金比、黃金矩形或等角螺線，那裡也就會出現斐波那契數，反之亦然。
[編輯本段]【與之相關的數學問題】
1.排列組合.
有一段樓梯有10級台階,規定每一步只能跨一級或兩級,要登上第10級台階有幾種不同的走法?
這就是一個斐波那契數列：登上第一級台階有一種登法；登上兩級台階，有兩種登法；登上三級台階，有三種登法；登上四級台階，有五種登法……
1，2，3，5，8，13……所以，登上十級，有89種
2.數列中相鄰兩項的前項比後項的極限.
就是問，當n趨於無窮大時，F(n)/F(n+1)的極限是多少？
這個可由它的通項公式直接得到，極限是(-1+√5)/2，這個就是所謂的黃金分割點，也是代表大自然的和諧的一個數字。
3.求遞推數列a(1)=1,a(n+1)=1+1/a(n).的通項公式.
由數學歸納法可以得到：a(n)=F(n+1)/F(n).將菲波那契數列的通項式代入，化簡就得結果。
[編輯本段]【斐波那契數列別名】

斐波那契數列又因數學家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為「兔子數列」。
斐波那契數列
一般而言，兔子在出生兩個月後，就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔都不死，那麼一年以後可以繁殖多少對兔子？
我們不妨拿新出生的一對小兔子分析一下：
第一個月小兔子沒有繁殖能力，所以還是一對;
兩個月後，生下一對小兔民數共有兩對;
三個月以後，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對;
－－－－－－
依次類推可以列出下表：
經過月數：---0---1---2---3---4---5---6---7---8---9--10--11--12
兔子對數：---1---1---2---3---5---8--13--21--34--55--89-144-233
表中數字1，1，2，3，5，8－－－構成了一個數列。這個數列有關十分明顯的特點，那是：前面相鄰兩項之和，構成了後一項。
這個特點的證明：每月的大兔子數為上月的兔子數，每月的小兔子數為上月的大兔子數，即上上月的兔子數，相加。
這個數列是義大利中世紀數學家斐波那契在＜算盤全書＞中提出的，這個級數的通項公式，除了具有a(n+2)=an+a(n+1)/的性質外，還可以證明通項公式為：an=1/√[（1＋√5/2) n-(1-√5/2) n](n=1,2,3.....）
[編輯本段]【斐波那挈數列通項公式的推導】
斐波那契數列：1，1，2，3，5，8，13，21……
如果設F(n)為該數列的第n項(n∈N+)。那麼這句話可以寫成如下形式：
F(0) = 0，F(1)=F(2)=1,F(n)=F(n-1)+F(n-2) (n≥3)
顯然這是一個線性遞推數列。
通項公式的推導方法一：利用特徵方程
線性遞推數列的特徵方程為：
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
則F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2
C1*X1^2 + C2*X2^2
解得C1=1/√5，C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根號5】
通項公式的推導方法二：普通方法
設常數r,s
使得F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]
則r+s=1, -rs=1
n≥3時，有
F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]
F(n-1)-r*F(n-2)=s*[F(n-2)-r*F(n-3)]
F(n-2)-r*F(n-3)=s*[F(n-3)-r*F(n-4)]
……
F(3)-r*F(2)=s*[F(2)-r*F(1)]
將以上n-2個式子相乘，得：
F(n)-r*F(n-1)=[s^(n-2)]*[F(2)-r*F(1)]
∵s=1-r，F(1)=F(2)=1
上式可化簡得：
F(n)=s^(n-1)+r*F(n-1)
那麼：
F(n)=s^(n-1)+r*F(n-1)
= s^(n-1) + r*s^(n-2) + r^2*F(n-2)
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) + r^3*F(n-3)
……
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)*F(1)
= s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)
（這是一個以s^(n-1)為首項、以r^(n-1)為末項、r/s為公差的等比數列的各項的和）
=[s^(n-1)-r^(n-1)*r/s]/(1-r/s)
=(s^n - r^n)/(s-r)
r+s=1, -rs=1的一解為 s=(1+√5)/2, r=(1-√5)/2
則F(n)=(√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
[編輯本段]【C語言程序】

main()
{
long fib[40] = {0,1};
int i;
for(i=2;i<40;i++)
{
fib[i ] = fib[i-1]+fib[i-2];
}
for(i=0;i<40;i++)
{
printf("F%d==%d\n", i, fib);
}
return 0;
}
[編輯本段]【C#語言程序】
public class Fibonacci
{
//NormRen
static void Main(string[] args)
{
int x = 0, y = 1;
for (int j = 1; j < 10; j++, y = x + y, x = y - x)
Console.Write(y + " ");
}
}
[編輯本段]【Java語言程序】
public class Fibonacci
{
public static void main(String[] args)
{
int x=1,y=1;
System.out.println(x+" ");
for(int i=1;i<=20;i++)
{
System.out.println(y+" ");
y=x+y;x=y-x;
}
}
}
[編輯本段]【Pascal語言程序】
遞推：
var
fib: array[0..40]of longint;
i: integer;
begin
fib[0] := 1;
fib[1] := 1;
for i:=2 to 39 do
fib[i ] := fib[i-1] + fib[i-2];
for i:=0 to 39 do
write('F', i, '=', fib[i ]);
end.
遞歸：
function fib(n:integer):longint;
begin
if (n=1) then exit(0);
if (n=2) then exit(1);
fib:=fib(n-2)+fib(n-1);
end;
[編輯本段]【PL/SQL程序】
declare i number :=0;
j number :=1;
x number :=1;
begin
while x<1000
loop
dbms_output.put_line(x);
x:=i+j;
i:=j;
j:=x;
end loop;
end;
[編輯本段]【數列與矩陣】
對於斐波那契數列1,1,2,3,5,8,13…….有如下定義
F(n)=f(n-1)+f(n-2)
F(1)=1
F(2)=1
對於以下矩陣乘法
F(n+1) = 1 1 * F(n)
F(n) 1 0 F(n-1)
它的運算就是
F(n+1)=F(n)+F(n-1)
F(n)=F(n)
可見該矩陣的乘法完全符合斐波那契數列的定義
設1 為B，1 1為C
1 1 0
可以用迭代得到:
斐波那契數列的某一項F(n)=(BC^(n-2))1
這就是斐波那契數列的矩陣乘法定義.
另矩陣乘法的一個運演算法則A¬^n(n為偶數)=A^(n/2)* A^(n/2).
因此可以用遞歸的方法求得答案.
時間效率：O(logn)，比模擬法O(n)遠遠高效。
代碼（PASCAL）
{變數matrix是二階方陣, matrix是矩陣的英文}
program fibonacci;
type
matrix=array[1..2,1..2] of qword;
var
c,cc:matrix;
n:integer;
function multiply(x,y:matrix):matrix;
var
temp:matrix;
begin
temp[1,1]:=x[1,1]*y[1,1]+x[1,2]*y[2,1];
temp[1,2]:=x[1,1]*y[1,2]+x[1,2]*y[2,2];
temp[2,1]:=x[2,1]*y[1,1]+x[2,2]*y[2,1];
temp[2,2]:=x[2,1]*y[1,2]+x[2,2]*y[2,2];
exit(temp);
end;
function getcc(n:integer):matrix;
var
temp:matrix;
t:integer;
begin
if n=1 then exit(c);
t:=n div 2;
temp:=getcc(t);
temp:=multiply(temp,temp);
if odd(n) then exit(multiply(temp,c))
else exit(temp);
end;
procere init;
begin
readln(n);
c[1,1]:=1;
c[1,2]:=1;
c[2,1]:=1;
c[2,2]:=0;
if n=1 then
begin
writeln(1);
halt;
end;
if n=2 then
begin
writeln(1);
halt;
end;
cc:=getcc(n-2);
end;
procere work;
begin
writeln(cc[1,1]+cc[1,2]);
end;
begin
init;
work;
end.
[編輯本段]【數列值的另一種求法】
F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]
其中[ x ]表示取距離 x 最近的整數。
[編輯本段]【數列的前若干項】
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
......
斐波那契弧線
斐波那契弧線，第一，此趨勢線以二個端點為准而畫出，例如，最低點反向到最高點線上的兩個點。三條弧線均以第二個點為中心畫出，並在趨勢線的斐波納契水平：38.2%， 50%和61.8%交叉。
斐波納契弧線，是潛在的支持點和阻力點水平價格。斐波納契弧線和斐波納契扇形線常常在圖表裡同時繪畫出。支持點和阻力點就是由這些線的交匯點得出。
要注意的是弧線的交叉點和價格曲線會根據圖表數值范圍而改變因為弧線是圓周的一部分，它的形成總是一樣的。
斐波那契扇形線
斐波那契扇形線，例如，以最低點反向到最高點線上的兩個端點畫出的趨勢線。然後通過第二點畫出一條「無形的(看不見的)」垂直線。然後，從第一個點畫出第三條趨勢線：38.2%， 50%和61.8%的無形垂直線交叉。
這些線代表了支撐點和阻力點的價格水平。為了能得到一個更為精確的預報，建議和其他斐波納契工具一起使用。
[編輯本段]【斐波那契數列的應用】
一位魔術師拿著一塊邊長為8英尺的正方形地毯，對他的地毯匠朋友說：「請您把這塊地毯分成四小塊，再把它們縫成一塊長13英尺，寬5英尺的長方
形地毯。」這位匠師對魔術師算術之差深感驚異，因為商者之間面積相差達一平方英尺呢！可是魔術師竟讓匠師用圖2和圖3的辦法達到了他的目的！
這真是不可思議的事！親愛的讀者，你猜得到那神奇的一 平方英尺究竟跑到哪兒去呢？
斐波那契數列在自然科學的其他分支，也有許多應用。例如，樹木的生長，由於新生的枝條，往往需要一段「休息」時間，供自身生長，而後才能萌發新枝。所以，一株樹苗在一段間隔，例如一年，以後長出一條新枝；第二年新枝「休息」，老枝依舊萌發；此後，老枝與「休息」過一年的枝同時萌發，當年生的新枝則次年「休息」。這樣，一株樹木各個年份的枝椏數，便構成斐波那契數列。這個規律，就是生物學上著名的「魯德維格定律」。
另外，觀察延齡草,野玫瑰,南美血根草,大波斯菊,金鳳花,耬斗菜,百合花,蝴蝶花的花瓣.可以發現它們花瓣數目具有斐波那契數:3,5,8,13,21……
斐波那契螺旋
具有13條順時針旋轉和21條逆時針旋轉的螺旋的薊的頭部
具有13條逆時針旋轉和21條逆時針旋轉的螺旋的薊的頭部
這些植物懂得斐波那契數列嗎？應該並非如此，它們只是按照自然的規律才進化成這樣。這似乎是植物排列種子的「優化方式」，它能使所有種子具有差不多的大小卻又疏密得當，不至於在圓心處擠了太多的種子而在圓周處卻又稀稀拉拉。葉子的生長方式也是如此，對於許多植物來說，每片葉子從中軸附近生長出來，為了在生長的過程中一直都能最佳地利用空間（要考慮到葉子是一片一片逐漸地生長出來，而不是一下子同時出現的），每片葉子和前一片葉子之間的角度應該是222.5度，這個角度稱為「黃金角度」，因為它和整個圓周360度之比是黃金分割數0.618033989……的倒數，而這種生長方式就決定了斐波那契螺旋的產生。向日葵的種子排列形成的斐波那契螺旋有時能達到89，甚至144條。

⑶ 浣跨敤c璇璦緙栧啓涓涓浣跨敤榪浠ｈ＄畻鏂愭嘗閭ｅ戞暟鍒椾腑絎琻欏圭殑鍑芥暟

c璇璦緙栧啓涓涓浣跨敤榪浠ｈ＄畻鏂愭嘗閭ｅ戞暟鍒椾腑絎琻欏圭殑鍑芥暟錛
#include <stdio.h>
int Fibonacci(int n)
{
if( n == 1 || n == 2) // 閫掑綊緇撴潫鐨勬潯浠訛紝奼傚墠涓ら」
return 1;
else
return Fibonacci(n-1)+Fibonacci(n-2); // 濡傛灉鏄奼傚叾瀹冮」錛屽厛瑕佹眰鍑哄畠鍓嶉潰涓ら」錛岀劧鍚庡仛鍜屻
}

int main()
{
int n;
printf("please input n: ");
scanf("%d",&n);
printf("Result: %d\n",Fibonacci(n));
return 0;
}

⑷ Python實現斐波那契數列的方法以及優化

斐波那契數列 （ 義大利語 ：Successione di Fibonacci） 的定義 ：

斐波那契數列由0和1開始，之後的每個斐波那契數就是由之前的兩數相加而得出。具體數值如下：

0，1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89， 144， 233， 377， 610,..............

特別注意 ：F(0)代表的是第一個數值，數列下標由0開始。

代碼如上，用了迭代的演算法計算每個數值，每個N值最大運行N-1次循環，演算法比遞歸要高效很多。遞歸代碼如下：