C++プログラム:数をそのまま使うか分割するかの選択による最大値の求め方

この記事では、整数Nが与えられたとき、その数を「そのままの値として使う」か「分割する」かを選択して得られる最大値を求めるC++プログラムの作成方法を解説します。

問題の概要

与えられた数Nに対して、次の2つの選択肢のうち、より大きい方の値を採用します。

• そのまま採用する:N自体の値を使用する
• 分割する:Nを2、3、4、5で割ったそれぞれの値に対する関数の結果の合計を使用する。つまり F(N/2) + F(N/3) + F(N/4) + F(N/5)

したがって、F(N)は次のように定義できます。

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

具体例で問題を理解しましょう。

• 入力:N = 8
• 出力:9

出力の解説

計算の流れは以下の通りです。

F(8) = F(8/2) + F(8/3) + F(8/4) + F(8/5)
= F(4) + F(2) + F(2) + F(1)
= 4 + 2 + 2 + 1
= 9

結果の9は元の値8よりも大きいため、この場合は分割を選択した方が有利であることが分かります。

解法のアプローチ

基本となるアイデアは、分割後の値に対して同じ関数を繰り返し呼び出すことです。しかし、単純な再帰処理では同じ値が何度も計算され、非常に非効率になってしまいます。

そこで動的計画法(DP)の概念を活用します。配列Fを用意し、F(0)からF(N)までの値を小さい順に計算しながら格納していきます。こうすることで、一度計算した結果を再利用でき、重複計算を排除しながら効率的に解を求めることが可能です。

本アルゴリズムの計算量は、時間・空間のいずれもO(N)です。

実装例(C++)

#include <iostream>
using namespace std;
int calcMaximumValue(int N) {
    int F[N + 1];
    int divVal = 0;
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i <= N; i++) {
        divVal = ( F[i / 2] + F[i / 3] + F[i / 4] + F[i / 5] );
        if(divVal > i)
            F[i] = divVal;
        else
            F[i] = i;
    }
    return F[N];
}
int main() {
    int N = 8;
    cout<<"そのまま使うか分割するかで得られる最大値 = "<<calcMaximumValue(N);
    return 0;
}

実行結果

そのまま使うか分割するかで得られる最大値 = 9