计算将数字表示为幂和的方法-yiteyi-C++库

给定两个整数x和n，我们需要找到很多方法将x表示为唯一自然数的n次幂和。给出了1<=n<=20。例如：

null

Input  : x = 100         n = 2Output : 3Explanation: There are three ways to express 100 as sum of natural numbersraised to power 2.100 = 10^2 = 8^2+6^2 = 1^2+3^2+4^2+5^2+7^2Input  : x = 100         n = 3Output : 1Explanation : The only combination is,1^3 + 2^3 + 3^3 + 4^3

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们使用递归来解决这个问题。我们首先逐个检查这个数字是否包含在求和中。

C++

                         // C++ program to count number of ways                       
                         // to express x as sum of n-th power                       
                         // of unique natural numbers.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // num is current num.                       
                         int                                     countWaysUtil(                                     int                                     x,                                     int                                     n,                                     int                                     num)                       
                         {                       
                                                 // Base cases                       
                                                 int                                     val = (x -                                     pow                                     (num, n));                       
                                                 if                                     (val == 0)                       
                                                 return                                     1;                       
                                                 if                                     (val < 0)                       
                                                 return                                     0;                       
           
                                                 // Consider two possibilities, num is                       
                                                 // included and num is not included.                       
                                                 return                                     countWaysUtil(val, n, num + 1) +                       
                                                 countWaysUtil(x, n, num + 1);                       
                         }                       
           
                         // Returns number of ways to express                       
                         // x as sum of n-th power of two.                       
                         int                                     countWays(                                     int                                     x,                                     int                                     n)                       
                         {                       
                                                 return                                     countWaysUtil(x, n, 1);                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     x = 100, n = 2;                       
                                                 cout << countWays(x, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number of ways                       
                         // to express x as sum of n-th power                       
                         // of unique natural numbers.                       
                         public                                     class                                     GFG {                       
           
                                                 // num is current num.                       
                                                 static                                     int                                     countWaysUtil(                                     int                                     x,                                     int                                     n,                                     int                                     num)                       
                                                 {                       
                                                 // Base cases                       
                                                 int                                     val = (                                     int                                     ) (x - Math.pow(num, n));                       
                                                 if                                     (val ==                                     0                                     )                       
                                                 return                                     1                                     ;                       
                                                 if                                     (val <                                     0                                     )                       
                                                 return                                     0                                     ;                       
                                   
                                                 // Consider two possibilities, num is                       
                                                 // included and num is not included.                       
                                                 return                                     countWaysUtil(val, n, num +                                     1                                     ) +                       
                                                 countWaysUtil(x, n, num +                                     1                                     );                       
                                                 }                       
                                   
                                                 // Returns number of ways to express                       
                                                 // x as sum of n-th power of two.                       
                                                 static                                     int                                     countWays(                                     int                                     x,                                     int                                     n)                       
                                                 {                       
                                                 return                                     countWaysUtil(x, n,                                     1                                     );                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     x =                                     100                                     , n =                                     2                                     ;                       
                                                 System.out.println(countWays(x, n));                       
                                                 }                       
                         }                       
                         // This code is contributed by Sumit Ghosh                       

Python3

                         # Python program to count number of ways                       
                         # to express x as sum of n-th power                       
                         # of unique natural numbers.                       
           
                         # num is current num.                       
                         def                                     countWaysUtil(x,n,num):                       
           
                                                 # Base cases                       
                                                 val                                     =                                     (x                                     -                                     pow                                     (num, n))                       
                                                 if                                     (val                                     =                                     =                                     0                                     ):                       
                                                 return                                     1                       
                                                 if                                     (val <                                     0                                     ):                       
                                                 return                                     0                       
                                   
                                                 # Consider two possibilities, num is                       
                                                 # included and num is not included.                       
                                                 return                                     countWaysUtil(val, n, num                                     +                                     1                                     )                                     +                                               
                                                 countWaysUtil(x, n, num                                     +                                     1                                     )                       
           
                                   
                         # Returns number of ways to express                       
                         # x as sum of n-th power of two.                       
                         def                                     countWays(x,n):                       
                                                 return                                     countWaysUtil(x, n,                                     1                                     )                       
           
                                   
                         # Driver code                       
                         x                                     =                                     100                       
                         n                                     =                                     2                       
           
                         print                                     (countWays(x, n))                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program to count number of ways                       
                         // to express x as sum of n-th power                       
                         // of unique natural numbers.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 // num is current num.                       
                                                 static                                     int                                     countWaysUtil(                                     int                                     x,                       
                                                 int                                     n,                                     int                                     num)                       
                                                 {                       
                                   
                                                 // Base cases                       
                                                 int                                     val = (                                     int                                     ) (x - Math.Pow(num, n));                       
                                                 if                                     (val == 0)                       
                                                 return                                     1;                       
                                                 if                                     (val < 0)                       
                                                 return                                     0;                       
                                   
                                                 // Consider two possibilities,                       
                                                 // num is included and num is                       
                                                 // not included.                       
                                                 return                                     countWaysUtil(val, n, num + 1)                       
                                                 + countWaysUtil(x, n, num + 1);                       
                                                 }                       
                                   
                                                 // Returns number of ways to express                       
                                                 // x as sum of n-th power of two.                       
                                                 static                                     int                                     countWays(                                     int                                     x,                                     int                                     n)                       
                                                 {                       
                                                 return                                     countWaysUtil(x, n, 1);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     x = 100, n = 2;                       
                                   
                                                 Console.WriteLine(countWays(x, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to count number of ways                       
                         // to express x as sum of n-th power                       
                         // of unique natural numbers.                       
           
                         // num is current num.                       
                         function                                     countWaysUtil(                                     $x                                     ,                                     $n                                     ,                                     $num                                     )                       
                         {                       
                                   
                                                 // Base cases                       
                                                 $val                                     = (                                     $x                                     - pow(                                     $num                                     ,                                     $n                                     ));                       
                                                 if                                     (                                     $val                                     == 0)                       
                                                 return                                     1;                       
                                                 if                                     (                                     $val                                     < 0)                       
                                                 return                                     0;                       
           
                                                 // Consider two possibilities, num is                       
                                                 // included and num is not included.                       
                                                 return                                     (countWaysUtil(                                     $val                                     ,                                     $n                                     ,                                     $num                                     + 1) +                       
                                                 countWaysUtil(                                     $x                                     ,                                     $n                                     ,                                     $num                                     + 1));                       
                         }                       
           
                         // Returns number of ways to express                       
                         // x as sum of n-th power of two.                       
                         function                                     countWays(                                     $x                                     ,                                     $n                                     )                       
                         {                       
                                                 return                                     countWaysUtil(                                     $x                                     ,                                     $n                                     , 1);                       
                         }                       
           
                         // Driver code                       
                         $x                                     = 100;                                     $n                                     = 2;                       
                         echo                                     (countWays(                                     $x                                     ,                                     $n                                     ));                       
           
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to count number of ways                       
                         // to express x as sum of n-th power                       
                         // of unique natural numbers.                       
           
                         // num is current num.                       
                         function                                     countWaysUtil(x, n, num)                       
                         {                       
                                                 // Base cases                       
                                                 let val = (x - Math.pow(num, n));                       
                                                 if                                     (val == 0)                       
                                                 return                                     1;                       
                                                 if                                     (val < 0)                       
                                                 return                                     0;                       
           
                                                 // Consider two possibilities, num is                       
                                                 // included and num is not included.                       
                                                 return                                     countWaysUtil(val, n, num + 1) +                       
                                                 countWaysUtil(x, n, num + 1);                       
                         }                       
           
                         // Returns number of ways to express                       
                         // x as sum of n-th power of two.                       
                         function                                     countWays(x, n)                       
                         {                       
                                                 return                                     countWaysUtil(x, n, 1);                       
                         }                       
           
                         // Driver code                       
           
                                                 let x = 100, n = 2;                       
                                                 document.write(countWays(x, n));                       
                                   
                         // This code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出：

本文由 安贾利 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章