동적 프로그래밍을 사용하여 피보나치 수를 찾는 C++ 프로그램

피보나치 수열은 다음과 같습니다.

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

이 시퀀스에서 n번째 항은 (n-1) ^th 의 합입니다. 및 (n-2) ^번째 약관.

생성하기 위해 재귀 접근 방식을 사용할 수 있지만 동적 프로그래밍에서는 절차가 더 간단합니다. 모든 피보나치 수를 테이블에 저장할 수 있으며 해당 테이블을 사용하여 이 시퀀스에서 다음 항을 쉽게 생성할 수 있습니다.

입력 − 용어 번호를 입력으로 사용합니다. 10이라고 말하세요.

출력 − 10 피비나치 항은 55

알고리즘

genFibo 시리즈(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
   // 0th and 1st number of the series are 0 and 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