用 C++ 计算将数字表示为幂之和的方法数

给定两个输入数字 num 和 power。目标是找到 num 可以表示为唯一自然数的给定幂之和的方法数。如果 num 为 10，power 为 2，则我们可以将 10 表示为 12+32。所以共有 1 种方法。

例如

输入

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

下面程序中使用的算法如下 −

在这个方法中，我们首先检查数字本身是否为任何 numpower 的幂。如果是，则返回方法数为 1，否则递归地检查 numpower + (num+1)power 的和。

  • 输入两个整数 num 和 power。

  • 函数 sum_of_powers(int num, int power, int val) 获取 num 并返回将 ‘num’ 表示为唯一自然数的给定幂之和的方法数。

  • 计算 check=(num − pow(val, power))。如果 check 为 0，则返回 1，因为数字本身是 valpower。

  • 如果 check 小于 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

更新于：2021年1月5日

1K+ 次浏览

启动你的 职业生涯

完成课程获得认证

开始学习
广告