C++で数値を「累乗の和」として表現する方法の数を求める

2つの整数 num と power が入力として与えられます。この問題の目的は、num を「相異なる自然数の累乗の和」として表現する方法が何通りあるかを求めることです。例えば、num が 10、power が 2 の場合、10 は 1² + 3² と表現できるため、方法は合計 1 通りとなります。

入力例と出力例

入力

num=30

出力

Count of ways to express a number as sum of powers are: 2

説明

30 を累乗の和として表現する方法は、以下の 2 通りがあります。

12 + 22 + 52
12 + 22 + 32 + 42

入力

num=35

出力

Count of ways to express a number as sum of powers are: 1

説明

35 を累乗の和として表現する方法は、以下の 1 通りです。

12 + 32 + 52

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

このアプローチでは、まず対象の数がそのまま何らかの val^power と一致するかどうかを確認します。一致していれば方法の数として 1 を返し、そうでなければ「現在の自然数 val の累乗を使う場合」と「使わない場合」の 2 つの分岐に分けて再帰的に探索を進めます。

• 2つの整数 num と power を入力として受け取ります。
• 関数 sum_of_powers(int num, int power, int val) は、num を「指定した指数を持つ相異なる自然数の累乗の和」として表現する方法の数を返します。
• check = (num − pow(val, power)) を計算します。check が 0 であれば、num 自体が val^power と一致することを意味するため、1 を返します。
• check が 0 未満の場合は、これ以上累乗を加えることができないため 0 を返します。
• それ以外の場合は temp = val + 1 として、次の自然数へ処理を進めます。
• sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp) の和を返します。これは「val の累乗を使用した場合」と「使用しなかった場合」の両方を探索することに相当します。
• 再帰がすべて完了すると、num を表現する方法の総数が得られます。

このアルゴリズムは、各自然数について「その累乗を和に含めるかどうか」を選択しながら部分集合を列挙していく、ナップサック問題にも似た典型的な再帰パターンに基づいています。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int sum_of_powers(int num, int power, int val){
    int check = (num - pow(val, power));
    if(check == 0){
        return 1;
    }
    else if(check < 0){
        return 0;
    } else {
        int temp = val + 1;
        return sum_of_powers(check, power, temp) + sum_of_powers(num, power, temp);
    }
}
int main(){
    int num = 25, power = 2;
    cout<<"Count of ways to express a number as sum of powers are: "<<sum_of_powers(num, power, 1);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が生成されます。

Count of ways to express a number as sum of powers are: 2