C++で整数Nを3つの部分に分割する方法の総数を求める

正の整数Nが与えられたとき、Nを3つの部分に分割する方法が何通りあるかを求めるのが本記事の目的です。各部分は同じ値でも異なる値でも構いません。Nの範囲は[1, 5000]とします。

この問題は、3つの部分に対応する3重のforループを使って解けます。最も内側のループの中で、3つの値の合計がNと一致するかどうかを判定し、一致していればカウントを1つ増やします。

具体例で確認してみましょう。

入力 − N = 5

出力 − Nを3つに分割する方法の数：2

説明 − 5は(1, 1, 3)と(1, 2, 2)の2通りで表せます。

入力 − N = 9

出力 − Nを3つに分割する方法の数：7

説明 − 9は(1, 1, 7)、(1, 2, 6)、(1, 3, 5)、(1, 4, 4)、(2, 2, 5)、(2, 3, 4)、(3, 3, 3)の7通りで表せます。

プログラムで使用しているアプローチ

• 1〜5000の範囲の値を持つ整数Nを用意します。
• 関数divideN(int n)は、引数nを受け取り、nを3つの部分に分割できる方法の総数を返します。
• 方法の数を格納するため、変数countを0で初期化します。
• 3つの部分それぞれに対応する3重のforループで走査します。
• 最も外側のループは1≦i＜n、内側のループはi≦j＜n、最も内側のループはj≦k＜nの範囲で回します。
• i、j、kの合計がnと一致するかを判定し、一致していればcountをインクリメントします。
• すべてのループが終了した時点で、countにはnを3つに分割する方法の総数が格納されています。
• 結果としてcountを返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int divideN(int n){
    int count = 0;
    for (int i = 1; i < n; i++){
        for (int j = i ; j < n; j++){
            for (int k = j; k < n; k++){
                int sum=i+j+k;
                if(sum==n)
                    { count++; }
            }
        }
    }
    return count;
}
int main(){
    int N=500;
    cout <<endl<< "Number of ways to divide N in 3 parts : "<<divideN(N);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

Number of ways to divide N in 3 parts: 20833

計算量に関する補足

このアプローチは3重ループを使用するため、時間計算量はO(N³)です。ただし、内側のループ開始位置を前のループ変数に依存させて重複する組み合わせを除外している点がポイントです。Nの最大値が5000であれば全探索でも十分に動作しますが、より大きなNを扱う場合は、整数の分割数に関する数学的性質（nをちょうど3つの正整数の和で表す方法の数は約n²/12となる）を利用することで、効率的に答えを求めることも可能です。