C++で級数2^0 + 2^1 + 2^2 + ... + 2^nの総和を求める2つの方法

問題の概要

この問題では、級数 2^0、2^1、2^2、…、2^n の第 n 項を表す数値 n が与えられます。求めるのは、級数 2^0 + 2^1 + 2^2 + … + 2^n の総和を計算するプログラムです。

入力例と出力例

入力:

n = 6

出力: 127

計算過程:

sum = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6
    = 1 + 2 + 4 + 8 + 16 + 32 + 64
    = 127

解法1: ループを使った素直なアプローチ

最もシンプルな解決策は、ループを使用する方法です。0 から n までの各値 i について 2^i を計算し、順に合計変数へ加算していきます。

アルゴリズム

sum = 0 で初期化
ステップ1: i = 0 から n まで繰り返し、以下を実行する
ステップ1.1: sum に 2^i を加算する (sum += 2^i)
ステップ2: sum を出力する

実装例

#include <iostream>
#include <math.h>
using namespace std;

int calcSeriesSum(int n) {
    int sum = 0;
    for (int i = 0; i <= n; i++)
        sum += pow(2, i);
    return sum;
}

int main() {
    int n = 11;
    cout << "級数 2^0 + 2^1 + 2^2 + ... + 2^" << n << " の総和は " << calcSeriesSum(n);
    return 0;
}

実行結果

級数 2^0 + 2^1 + 2^2 + ... + 2^11 の総和は 4095

この方法は直感的で分かりやすい反面、ループ処理が必要なため、時間計算量は O(n) となります。n が大きくなるほど計算時間が比例して増加するため、必ずしも効率的とは言えません。

解法2: 数学公式を使った効率的なアプローチ

この級数は公比 2 の等比級数であるため、総和は次の数学公式で一発に求められます。

総和 = 2^(n+1) − 1

この公式を使えば、ループが不要になり、O(1) の定数時間で答えを計算できます。

実装例

#include <iostream>
#include <math.h>
using namespace std;

int calcSeriesSum(int n) {
    return (pow(2, (n+1)) - 1);
}

int main() {
    int n = 11;
    cout << "級数 2^0 + 2^1 + 2^2 + ... + 2^" << n << " の総和は " << calcSeriesSum(n);
    return 0;
}

実行結果

級数 2^0 + 2^1 + 2^2 + ... + 2^11 の総和は 4095

補足: ビットシフトを使ったさらに高速な方法

2 の冪乗の計算は、ビットシフト演算子を用いることでより高速に処理できます。2^(n+1) は「1 << (n+1)」と等しいため、次のように書き換えられます。

int calcSeriesSum(int n) {
    return (1 << (n + 1)) - 1;
}

pow 関数は内部で浮動小数点演算を行うため、整数演算であるビットシフトの方が、計算速度と精度の両面で有利です。

まとめ

級数 2^0 + 2^1 + … + 2^n の総和を求めるには、ループで順に加算する方法(O(n))と、公式 2^(n+1) − 1 を使う方法(O(1))の2通りがあります。実用上は計算量の観点から公式を使った解法が推奨され、さらにビットシフトを活用すれば、高速かつ正確に計算できます。