C++で漸化式のn番目の項を求めるアルゴリズム

概要

数列 b_n が次の漸化式で定義されているとします。

• b₁ = 1
• b_n+1 / b_n = 2ⁿ

このとき、与えられた n に対して log₂(b_n) の値を求めるのが本記事の目的です。

入出力例

入力1

6

出力1

15

説明： 後述の通り log₂(b_n) = n(n − 1) / 2 となるため、(6 × (6 − 1)) / 2 = 15 が出力されます。

入力2

200

出力2

19900

解法の考え方(一般項の導出)

まず、漸化式の関係を n の降順に書き並べます。

• b_n+1 / b_n = 2ⁿ
• b_n / b_n−1 = 2ⁿ⁻¹
• …
• b₂ / b₁ = 2¹

これらの式をすべて辺々掛け合わせると、左辺の分子と分母が打ち消し合い、次のようになります。

(b_n+1 / b_n) × (b_n / b_n−1) × … × (b₂ / b₁) = 2^{n + (n−1) + … + 1}

つまり、

b_n+1 / b₁ = 2^n(n+1)/2

ここでは、1 + 2 + 3 + … + n = n(n+1)/2 という等差数列の和の公式を利用しています。

初期値 b₁ = 1 を代入すると、

b_n+1 = 2^n(n+1)/2

さらに、n を n+1 で置き換えることで、

b_n = 2^n(n−1)/2

両辺の底を2とする対数を取れば、目的の一般項が得られます。

log₂(b_n) = n(n − 1) / 2

C++による実装例

// 与えられた漸化式の n 番目の項を求める C++ プログラム
#include <bits/stdc++.h>
using namespace std;

// 必要な値を返す関数
int sum(int n1) {
    // 答えを計算する
    int ans1 = (n1 * (n1 - 1)) / 2;
    // 答えを返す
    return ans1;
}

// メイン関数
int main() {
    // n の値を設定
    int n = 200;
    // 関数を呼び出して結果を出力
    cout << sum(n);
    return 0;
}

出力

19900

計算量と実装上の注意点

この解法は、漸化式を閉じた形(一般項の公式)に変換してから計算しているため、計算量は O(1) となります。n の値がどれだけ大きくても、一定時間で答えを求められるのが大きな利点です。

ただし、int 型は約21億までしか表現できないため、n が大きくなると乗算時にオーバーフローを起こします。n が約46,000を超えるようなケースでは、long long 型を使用するか、必要に応じて多倍長整数(任意精度演算)の利用を検討してください。