c++實(shí)現(xiàn)斐波那契數(shù)列

c++實(shí)現(xiàn)斐波那契數(shù)列斐波那契數(shù)列是由萊昂納多·斐波那契在1202年提出的一種數(shù)列，其規(guī)律是前兩個(gè)數(shù)之和等于第三個(gè)數(shù)，以此類推。具體而言，數(shù)列的第一個(gè)和第二個(gè)數(shù)為0和1，之后每個(gè)數(shù)均為前兩個(gè)數(shù)之和。因此，斐波那契數(shù)列的前幾個(gè)數(shù)字為0、1、1、2、3、5、8、13、21等。斐波那契數(shù)列在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和自然科學(xué)領(lǐng)域都有廣泛的應(yīng)用。

在C++中實(shí)現(xiàn)斐波那契數(shù)列并不難，可以采用遞歸或非遞歸的方式實(shí)現(xiàn)。

1.遞歸

首先，我們可以用遞歸的方式實(shí)現(xiàn)斐波那契數(shù)列。具體而言，我們定義一個(gè)函數(shù)fib(n)，用來(lái)計(jì)算斐波那契數(shù)列的第n個(gè)數(shù)字。函數(shù)的代碼如下：

```

intfib(intn)

{

if(n<2)

returnn;

else

returnfib(n-1)+fib(n-2);

}

```

在這段代碼中，我們首先判斷n是否小于2。如果n小于2，則直接返回n。否則，我們遞歸調(diào)用fib函數(shù)，計(jì)算斐波那契數(shù)列的前兩個(gè)數(shù)之和。由于遞歸的調(diào)用會(huì)比較耗時(shí)，在計(jì)算大數(shù)位的斐波那契數(shù)列時(shí)，會(huì)出現(xiàn)運(yùn)行時(shí)間過(guò)長(zhǎng)的情況。

2.非遞歸

為了加快計(jì)算斐波那契數(shù)列的速度，我們可以采用非遞歸的方式實(shí)現(xiàn)。具體而言，我們可以通過(guò)for循環(huán)或while循環(huán)來(lái)計(jì)算斐波那契數(shù)列的第n個(gè)數(shù)字。這種方式可以大大減少遞歸的調(diào)用次數(shù)，從而提高計(jì)算速度。

（1）for循環(huán)方式

我們可以采用for循環(huán)來(lái)計(jì)算斐波那契數(shù)列的第n個(gè)數(shù)字。具體而言，我們用一個(gè)數(shù)組來(lái)存儲(chǔ)計(jì)算結(jié)果，從而避免重復(fù)計(jì)算。函數(shù)的代碼如下：

```

intfib(intn)

{

if(n<2)

returnn;

intf[n+1];

f[0]=0;

f[1]=1;

for(inti=2;i<=n;i++)

f[i]=f[i-1]+f[i-2];

returnf[n];

}

```

在這段代碼中，我們首先判斷n是否小于2。如果n小于2，則直接返回n。否則，我們定義一個(gè)數(shù)組f來(lái)保存計(jì)算結(jié)果。數(shù)組f的前兩個(gè)數(shù)分別為0和1。然后，我們通過(guò)for循環(huán)來(lái)計(jì)算斐波那契數(shù)列的第n個(gè)數(shù)字，將結(jié)果存儲(chǔ)到數(shù)組f中。最后，我們返回?cái)?shù)組f的第n個(gè)數(shù)字。

（2）while循環(huán)方式

另一種非遞歸的方式是采用while循環(huán)。具體而言，我們定義三個(gè)變量來(lái)分別保存前兩個(gè)數(shù)字和當(dāng)前數(shù)字。我們通過(guò)while循環(huán)來(lái)不斷計(jì)算當(dāng)前數(shù)字，直到計(jì)算出第n個(gè)數(shù)字為止。函數(shù)的代碼如下：

```

intfib(intn)

{

if(n<2)

returnn;

intf1=0,f2=1,f3;

inti=2;

while(i<=n)

{

f3=f1+f2;

f1=f2;

f2=f3;

i++;

}

returnf3;

}

```

在這段代碼中，我們定義了三個(gè)變量f1、f2和f3來(lái)保存前兩個(gè)數(shù)字和當(dāng)前數(shù)字。我們首先判斷n是否小于2。如果n小于2，則直接返回n。否則，我們通過(guò)while循環(huán)來(lái)不斷計(jì)算當(dāng)前數(shù)字。計(jì)算出當(dāng)前數(shù)字之后，我們將f1和f2分別向后移動(dòng)一個(gè)數(shù)位，然后將當(dāng)前數(shù)字存儲(chǔ)到f3中。最后，我們返回f3。

總結(jié)

本文介紹了兩種方式來(lái)計(jì)算斐波那契數(shù)列：遞歸和非遞歸。遞歸的方式會(huì)比較耗時(shí)，在計(jì)算大數(shù)位的斐波那契數(shù)列時(shí)會(huì)出現(xiàn)運(yùn)行時(shí)間過(guò)長(zhǎng)的情況。非遞歸的方式可以避免重復(fù)計(jì)算，從而提高計(jì)算速度