C++でf[i] = f[i-1] − f[i-2]という規則に従う数列のN番目の項を求める方法

数列 f の各項が f[i] = f[i-1] − f[i-2] という規則に従うとき、初項 f[0] = X、第2項 f[1] = Y が与えられた場合に、この数列のN番目の項を求める問題を考えます。

例えば、X = 2、Y = 3、N = 3 のとき、答えは -2 になります。実際に順番に計算してみると、f[0] = 2、f[1] = 3、f[2] = 3 − 2 = 1、f[3] = 1 − 3 = −2 となるためです。

周期性に着目した効率的な解法

この数列を詳しく観察すると、6項ごとに同じパターンが繰り返されるという重要な性質があります。つまり、最初の6項さえ求めてしまえば、N番目の項は「N mod 6」番目の項と必ず一致します。

この性質を利用すれば、Nがどれほど大きな値であっても、ループで毎回計算することなく、定数時間 O(1) で答えを導き出すことができます。

C++での実装例

#include <iostream>
using namespace std;

int searchNthTerm(int x, int y, int n) {
    int terms[6];
    terms[0] = x;
    terms[1] = y;
    for (int i = 2; i <= 5; i++)
        terms[i] = terms[i - 1] - terms[i - 2];
    return terms[n % 6];
}

int main() {
    int x = 2, y = 3, n = 3;
    cout << "Term at index " << n << " is: " << searchNthTerm(x, y, n);
}

実行結果

Term at index 3 is: -2

アルゴリズムのポイント

• 漸化式に基づいて最初の6項だけを配列に計算して格納する
• N番目の項は terms[N % 6] を参照するだけで取得できる
• 計算量は O(1)、使用メモリも定数であり、非常に効率的

このように、一見するとN回の反復計算が必要に思える漸化式の問題でも、数列の周期性を見抜くことで大幅に処理を高速化できます。同様の周期性を持つ漸化式の問題には広く応用できるテクニックなので、ぜひ覚えておきましょう。