C言語で漸化式のn番目の項を求めるプログラム

問題の概要

3つの整数 a、b、c と整数 n が与えられたとします。このとき、以下の漸化式で定義される数列 S(n) の第n項を求めます。

• S(1) = a
• S(2) = b
• S(3) = c
• n > 3 のとき、S(n) = S(n-1) + S(n-2) + S(n-3)

計算例

例として、a = 5、b = 2、c = 3、n = 6 が入力された場合を考えてみましょう。このときの出力は 28 になります。その理由は以下の通りです。

• S(4) = S(3) + S(2) + S(1) = 3 + 2 + 5 = 10
• S(5) = S(4) + S(3) + S(2) = 10 + 3 + 2 = 15
• S(6) = S(5) + S(4) + S(3) = 15 + 10 + 3 = 28

解き方(アルゴリズム)

この問題は再帰呼び出しを使うと非常にシンプルに解けます。a、b、c、n を引数にとる関数 solve() を定義し、次の手順で処理を行います。

1. n が 1 の場合は a を返す
2. n が 2 の場合は b を返す
3. n が 3 の場合は c を返す
4. それ以外の場合は solve(a, b, c, n-1) + solve(a, b, c, n-2) + solve(a, b, c, n-3) を返す

C言語での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <stdio.h>

int solve(int a, int b, int c, int n){
    if(n == 1)
        return a;
    if(n == 2)
        return b;
    if(n == 3)
        return c;
    return solve(a, b, c, n-1) + solve(a, b, c, n-2) + solve(a, b, c, n-3);
}

int main(){
    int a = 5, b = 2, c = 3, n = 6;
    int res = solve(a, b, c, n);
    printf("%d", res);
}

入力

5, 2, 3, 6

出力

28

補足：計算量について

上記のような素朴な再帰実装では、同じ項を何度も繰り返し計算してしまうため、時間計算量は O(3^n) 程度まで増大します。そのため n が大きくなると処理速度が急激に低下します。実際の開発では、一度計算した結果を配列などにキャッシュする「メモ化」や、for文による反復処理を組み合わせることで、計算量を O(n) まで改善するのが一般的です。