【C++】整数を4分割するかそのまま使うかで最大値を求めるアルゴリズム

このチュートリアルでは、整数を再帰的に分割するか、そのままの値を採用するかを選択して最大値を求めるプログラムをC++で解説します。

具体的には、ある整数 n が与えられたとき、以下の漸化式に従って最大値を計算します。数を2・3・4・5で割った各部分の結果を合計する場合と、そのままの値 n を採用する場合を比較し、大きい方を選びます。

F(n) = max( (F(n/2) + F(n/3) + F(n/4) + F(n/5)), n )

アルゴリズムのポイント

単純な再帰で実装すると、同じ値を何度も計算することになり非効率です。そこで本実装では、ボトムアップ方式の動的計画法（DP）を用いて、0からnまで順に各値の最大結果を配列へ記録していきます。これにより重複計算がなくなり、処理速度が大幅に向上します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
// 最大結果を計算する
int findMaximum(int size) {
    int term[size + 1];
    term[0] = 0;
    term[1] = 1;
    int i = 2;
    while (i <= size) {
        // 分割した場合とそのままの場合の大きい方を採用
        term[i] = max(i, (term[i / 2] + term[i / 3] + term[i / 4] + term[i / 5]));
        i = i + 1;
    }
    return term[size];
}
int main() {
    int number = 37;
    cout << "Maximum possible sum: " << findMaximum(number) << endl;
    return 0;
}

出力

Maximum possible sum: 57

コードの解説

配列 term には、各インデックスの値に対する最大結果が格納されます。初期条件として term[0] = 0、term[1] = 1 を設定し、2からnまで順に max(i, term[i/2] + term[i/3] + term[i/4] + term[i/5]) を計算していきます。

例えば n = 37 の場合、37を分割すると F(18) + F(12) + F(9) + F(7) の和になります。それぞれの値をさらに再帰的に分割していくことで、最終的に57という最大値が得られます。

なお、可変長配列（VLA）はGCCの拡張機能であり標準C++の仕様ではないため、移植性を高めたい場合は std::vector<int> の利用を検討するとよいでしょう。