C++で累乗の合計として数値を表現する方法を数えます

例

入力

num=30

出力

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

説明

The ways in which we can express 30 as sum of powers:
12 + 22 + 52 and 12 + 22 + 32 + 42

入力

num=35

出力

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

説明

The ways in which we can express ‘num’ as sum of powers: 22 + 32

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、最初に、数値自体が任意の数値の累乗であるかどうかを確認します ^power 。はいの場合はウェイを1として返し、そうでない場合は再帰的に合計num ^power をチェックします。 +（num + 1） ^パワー 。

• 入力として2つの整数numとpowerを取ります。

• 関数sum_of_powers（int num、int power、int val）は、numを取り、「num」を指定された累乗で累乗された一意の自然数の合計として表す方法の数を返します。

• check =（num − pow（val、power））を取ります。チェックが0の場合、数値自体がval ^power であるため、1を返します。 。

• チェックが0未満の場合は、0を返します。

• それ以外の場合は、temp =val+1を取ります。

• （sum_of_powers（check、power、temp）+ sum_of_powers（num、power、temp））の合計を返します。

• 最後に、値を返す方法を取得します。

例

#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