Dados dos enteros x y n, necesitamos encontrar varias formas de expresar x como suma de potencias n-ésimas de números naturales únicos. Se da que 1 <= n <= 20.
Ejemplos:
Input : x = 100 n = 2 Output : 3 Explanation: There are three ways to express 100 as sum of natural numbers raised to power 2. 100 = 10^2 = 8^2+6^2 = 1^2+3^2+4^2+5^2+7^2 Input : x = 100 n = 3 Output : 1 Explanation : The only combination is, 1^3 + 2^3 + 3^3 + 4^3
Usamos la recursividad para resolver el problema. Primero verificamos uno por uno si el número está incluido en la sumatoria o no.
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>
Producción:
3
Este artículo es una contribución de Anjali . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA