資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式顯示斐波那契數列
斐波那契數列包含一些數字，其中每個數字都是前兩個數字的和。這產生了以下整數序列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377…….
定義斐波那契數的遞推關係如下：
F(n) = F(n-1) + F(n-2) F(0)=0 F(1)=1
顯示斐波那契數列的程式
有兩種方法可以顯示斐波那契數列，即使用動態規劃和遞迴程式設計。這些方法將進一步解釋如下：
動態規劃
示例
#include<iostream>
using namespace std;
void fib(int n) {
int f[n];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i < n; i++) {
f[i] = f[i-1] + f[i-2];
}
for (i = 0; i < n; i++) {
cout<<f[i]<<" ";
}
}
int main () {
int n = 10;
fib(n);
getchar();
return 0;
}以上程式的輸出如下所示。
輸出
0 1 1 2 3 5 8 13 21 34
在程式中，main()是驅動函式。建立斐波那契數列的實際程式碼儲存在fib()函式中，該函式從main中呼叫。
建立一個數組f[n]，它將儲存斐波那契數列的前n項。該陣列的第一和第二元素分別初始化為0和1。
f[0] = 0; f[1] = 1;
然後使用for迴圈將每個元素儲存在陣列中，作為其前兩個元素的和。
for (i = 2; i < n; i++) {
f[i] = f[i-1] + f[i-2];
}最後顯示斐波那契數列。
for (i = 0; i < n; i++) {
cout<<f[i]<<" ";
}遞迴程式設計
讓我們看看如何使用遞迴顯示斐波那契數列。
示例
#include<iostream>
using namespace std;
int fib(int n) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main () {
int n = 10, i;
for(i=0;i<n;i++)
cout<<fib(i)<<" ";
return 0;
}輸出
0 1 1 2 3 5 8 13 21 34
在上面的程式中，設定了一個for迴圈，使用遞迴建立斐波那契數列的每一項。這是透過為數列中的每一項呼叫函式fib()來完成的。
for(i=0;i<n;i++) cout<<fib(i)<<" ";
如果n為0或1，則函式fib()分別返回0或1。如果不是，它將遞迴呼叫自身，作為前兩項的和，直到返回正確的值。
if (n <= 1) return n; return fib(n-1) + fib(n-2);
更新於： 2020年6月23日
15K+ 瀏覽量
廣告