C++で交互フィボナッチ数列を出力する方法

フィボナッチ数とは、一般に 0, 1 または 1, 1 の2つの固定された数から始まり、それ以降の各項が直前の2つの項の和となる数列として定義されるものです。

例えば、フィボナッチ数列の最初の12項は「0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89」となります。

この数列を一般化すると、n番目の項は(n-1)番目の項と(n-2)番目の項の和に等しくなります。これをもとに、フィボナッチ数列のn番目の項を求める漸化式は次のように表せます。

T_n = T_n-1 + T_n-2

この式を使って5番目の項を求める場合、すでに分かっている3番目と4番目の項を代入して計算します。

T₅ = T₄ + T₃

T₅ = 5 + 3 = 8

交互フィボナッチ数列(Alternate Fibonacci Series)とは、通常のフィボナッチ数列と同じ値を持ちながら、数列の中から1つおきの要素だけを出力したものです。例えば、交互フィボナッチ数列の最初の4つの要素は「0, 1, 3, 8」になります。

交互フィボナッチ数列を出力するプログラムを作成するには、上記の漸化式を使って数列の各要素を順に計算し、その中から交互の値だけを出力します。

アルゴリズム

Step 1 : 数列の最初の2つの値を n1 = 0、n2 = 1 として初期化する。
Step 2 : i = 2 から n までループし、以下のステップ3〜5を実行する。
Step 3 : 次の要素を n3 = n1 + n2 として計算する。
Step 4 : n1 = n2、n2 = n3 と更新する。
Step 5 : i % 2 == 0 の場合、n3 を出力する。

C++による実装例

#include <iostream>
using namespace std;
int main(){
   int n1=0,n2=1,n3,i,number;
   cout<<"Enter the number of elements to be present in the series: ";
   cin>>number;
   cout<<"Alternate Fibonacci Series is : ";
   cout<<n1<<" ";
   for (i=2;i<(number*2);++i){
      n3=n1+n2;
      n1=n2;
      n2=n3;
      if(i%2==0)
         cout<<n3<<" ";
   }
   return 0;
}

コードの解説

まず、ユーザーに出力したい項数(number)を入力してもらい、数列の最初の値である0を出力します。続いて、i = 2 から number × 2 までループ処理を行い、各反復ごとに直前の2つの値の和として次のフィボナッチ数を計算します。そして、反復回数が偶数の場合(i % 2 == 0)にのみ値を出力することで、1つおきの要素、つまり交互フィボナッチ数列を取得できます。

出力結果

Enter the number of elements to be present in the series: 4
Alternate Fibonacci Series is : 0 1 3 8