フィボナッチ数列を表示するC++プログラム

フィボナッチ数列には、各項が前の2つの項の合計である数値が含まれています。これにより、次の整数シーケンスが作成されます-

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

フィボナッチ数列を表示するプログラム

フィボナッチ数列を表示するには、動的計画法と再帰計画法の2つの方法があります。これらはさらに次のように説明されます-

動的計画法

例

#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（）はドライバー関数です。フィボナッチ数列を作成するための実際のコードは、mainから呼び出される関数fib（）に格納されます。

フィボナッチ数列の最初のn項を格納する配列f[n]が作成されます。この配列の最初の要素と2番目の要素は、それぞれ0と1に初期化されます。

f[0] = 0;
f[1] = 1;

次に、forループを使用して、配列内の各要素を前の2つの要素の合計として格納します。

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)<<" ";

関数fib（）は、nが0または1の場合、それぞれ0または1を返します。そうでない場合は、正しい値が返されるまで、前の2つの項の合計として再帰的に呼び出します。

if (n <= 1)
return n;
return fib(n-1) + fib(n-2);