C++で最初のn個の自然数の総和の合計を求める方法

問題の概要

本記事では、「最初のn個の自然数の総和の合計」を求める問題を扱います。具体的には、1からnまでの各自然数kについて「1からkまでの合計」を計算し、それらをすべて足し合わせた最終的な値を求めます。

まず、具体例を見ながら概念を理解しましょう。

入力 : 4
出力 : 20
説明 :
最初の1個の自然数の合計 = 1
最初の2個の自然数の合計 = 1 + 2 = 3
最初の3個の自然数の合計 = 1 + 2 + 3 = 6
最初の4個の自然数の合計 = 1 + 2 + 3 + 4 = 10
したがって、総和の合計 = 1 + 3 + 6 + 10 = 20

このように、各段階の部分和(1, 3, 6, 10, ...)は「三角数」と呼ばれる数列であり、その累積を求めるのがこの問題の目的です。

C++による実装

以下のコードでは、各iに対して i*(i+1)/2(すなわち1からiまでの合計)を計算し、それを順次加算していきます。

#include <iostream>
using namespace std;
int sumofSum(int n){
    int sum = 0;
    for (int i=1; i<=n; i++)
        sum += i*(i+1)/2;
    return sum;
}
int main(){
    int n = 4;
    cout<<"sum of sum first "<<n<<" natural numbers is "<<sumofSum(n);
    return 0;
}

実行結果

sum of sum first 4 natural numbers is 20

計算量と数学的な公式

上記のループを使った方法の時間計算量はO(n)です。しかし、数学的に式を変形すると、閉形式の公式が存在します。

Σ k(k+1)/2(k=1〜n)= n(n+1)(n+2)/6

この公式を利用すれば、ループなしでO(1)の計算量で答えを求められます。例えばn=4の場合、4×5×6÷6 = 20となり、先ほどの実行結果と一致します。大きなnを扱う場合には、この公式版の実装が大幅な高速化につながります。