C言語でフィボナッチ数列を生成するプログラムの解説

整数 n が与えられたとき、0 から始めて n 項目までのフィボナッチ数列を生成するのが本記事の目的です。フィボナッチ数列は次のような形で表されます。

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

この数列では、最初の 2 つの値である 0 と 1 は固定されています。それ以降は、直前の 2 つの数字を足し合わせて新しい値を作っていきます。例えば以下のようになります。

0+1=1(3番目の値)
1+1=2(4番目の値)
2+1=3(5番目の値)
…以降も同様に続きます

フィボナッチ数列の一般項 F(n) は、次の漸化式として定義できます。

Fn = Fn-1 + Fn-2
ここで、F(0)=0 および F(1)=1 は常に固定値です

フィボナッチ数列を生成する方法は複数ありますが、代表的なアプローチを 2 つ紹介します。

再帰的なアプローチ

関数が自身を呼び出すことで数列を計算する方法です。実装がシンプルで分かりやすいというメリットがありますが、計算量が指数関数的に増加してしまうため、大きな n に対しては非効率になります。

for ループを使うアプローチ

for ループを使って数列を順に生成する方法です。時間計算量を O(n) まで抑えられるため、実用的な観点から推奨される手法です。本記事でもこちらの方法を採用します。

入出力の例

入力： n=10
出力： 0 1 1 2 3 5 8 13 21 34

アルゴリズム

開始
ステップ 1 → フィボナッチ数列を出力する関数を宣言する
    void fibonacci(int n)
        変数を int a=0, b=1, c, i として宣言
        a と b を出力する
        for(i=2; i<n; ++i) のループを実行
            c = a + b を代入
            c を出力する
            a = b を代入
            b = c を代入
        ループ終了
ステップ 2 → main() 内での処理
        int 型の変数に 10 を代入
        fibonacci(n) を呼び出す
終了

C言語によるサンプルコード

#include<stdio.h>
void fibonacci(int n){
    int a=0,b=1,c,i;
    printf("%d項目までのフィボナッチ数列: ",n);
    printf("\n%d %d",a,b); // 0 と 1 を出力
    for(i=2;i<n;++i) // 0 と 1 は固定値のため、ループは 2 から開始{
        c=a+b;
        printf(" %d",c);
        a=b;
        b=c;
    }
}
int main(){
    int n=10;
    fibonacci(n);
    return 0;
}

実行結果

10項目までのフィボナッチ数列:
0 1 1 2 3 5 8 13 21 34

このように、for ループを使った実装では変数 a と b に「直前の 2 つの値」を保持しながら更新していくことで、効率的にフィボナッチ数列を求めることができます。処理は線形時間 O(n) で完了するため、n が大きくなっても安定したパフォーマンスを発揮します。