C ++程序使用动态编程查找斐波那契数

斐波那契数列就是这样，

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,……

在此序列中，第n个项是第(n-1)^个和^第(n-2)^个项的总和。

要生成，我们可以使用递归方法，但是在动态编程中，过程更简单。它可以将所有斐波那契数存储在一个表中，通过使用该表，可以轻松生成此序列中的下一项。

输入-以术语编号作为输入。说是10

输出-的10^个fibinacci术语是55

算法

genFiboSeries(n)

输入值

字数上限。

输出结果

第n个斐波纳契项。

Begin
define array named fibo of size n+2
fibo[0] := 0
fibo[1] := 1
for i := 2 to n, do
fibo[i] := fibo[i-1] + fibo[i-2]
done
return fibo[n]
End

范例程式码

#include<iostream>
using namespace std;
int genFibonacci(int n) {
   int fibo[n+2]; //array to store fibonacci values
   //系列的第0个和第1数字是0和1-
   fibo[0] = 0;
   fibo[1] = 1;
   for (int i = 2; i <= n; i++) {
      fibo[i] = fibo[i-1] + fibo[i-2]; //generate ith term using previous
      two terms
   }
   return fibo[n];
}
int main () {
   int n;
   cout << "Enter number of terms: "; cin >>n;
   cout << n<<" th Fibonacci Terms: "<<genFibonacci(n)<<endl;
}

输出结果

Enter number of terms: 10
10th Fibonacci Terms: 55