用 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+ 次瀏覽

啟動你的 職業生涯

完成課程獲得認證

開始學習
廣告