C++で級数 1/(1*2) + 1/(2*3) + 1/(3*4) + … の総和を求める方法

この問題では、級数「1/(1*2) + 1/(2*3) + … + 1/(n*(n+1))」の第 n 項までの項数 n が与えられます。私たちのタスクは、この級数の総和を求めるプログラムを作成することです。

例で問題を理解しよう

入力

n = 3

出力

0.75

説明 − 総和 = 1/(1*2) + 1/(2*3) + 1/(3*4) = 1/2 + 1/6 + 1/12 = (6+2+1)/12 = 9/12 = 3/4 = 0.75

この問題に対する最もシンプルな解決策は、ループを使用する方法です。級数の各要素の値を順番に計算し、それらを合計値に加算していきます。

アルゴリズム

sum = 0 で初期化
ステップ1: i = 1 から n まで繰り返し、以下を実行する:
    ステップ1.1: sum を更新する → sum += 1/(i*(i+1))
ステップ2: sum を出力する。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
double calcSeriesSum(int n) {
    double sum = 0.0;
    for (int i = 1; i <= n; i++)
    sum += ((double)1/(i*(i+1)));
    return sum;
}
int main() {
    int n = 5;
    cout<<"Sum of the series 1/(1*2) + 1/(2*3) + 1/(3*4) + 1/(4*5) + ... is "<<calcSeriesSum(n);
    return 0;
}

出力

Sum of the series 1/(1*2) + 1/(2*3) + 1/(3*4) + 1/(4*5) + ... is 0.833333

この解法はループを使用しているため、n が大きくなると計算時間が増加し、あまり効率的とは言えません。時間計算量は O(n) になります。

効率的な解法：一般公式を利用する

より効率的なアプローチは、級数の総和に対する一般公式を導出することです。この級数は「テレスコーピング級数（望遠鏡級数）」と呼ばれるもので、各項を部分分数に分解すると、隣接する項同士が打ち消し合い、最初の項と最後の項だけが残るという性質があります。

級数は 1/(1*2) + 1/(2*3) + 1/(3*4) + 1/(4*5) + …
第 n 項は 1/n(n+1)
an = 1/n(n+1)
an = ((n+1) - n)/n(n+1)
an = (n+1)/n(n+1) - n/n(n+1)
an = 1/n - 1/(n+1)

したがって、級数の総和は
sum = 1/(1*2) + 1/(2*3) + 1/(3*4) + 1/(4*5) + …

各項を上記の式に当てはめると、
sum = 1/1 - 1/2 + 1/2 - 1/3 + 1/3 - 1/4 + 1/4 - 1/5 + … + 1/n - 1/(n+1)

中間の項がすべて打ち消し合うため、
sum = 1 - 1/(n+1)
sum = (n+1-1)/(n+1) = n/(n+1)

つまり、この級数の総和は単純な式「n/(n+1)」で表せるため、ループ不要で O(1) の時間計算量で答えを求めることができます。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
double calcSeriesSum(int n) {
    return ((double)n/ (n+1));
}
int main() {
    int n = 5;
    cout<<"Sum of the series 1/(1*2) + 1/(2*3) + 1/(3*4) + 1/(4*5) + ... is "<<calcSeriesSum(n);
    return 0;
}

出力

Sum of the series 1/(1*2) + 1/(2*3) + 1/(3*4) + 1/(4*5) + ... is 0.833333