Dado un número x, imprime todas las sucesiones no crecientes posibles con suma igual a x.
Ejemplos:
Input: x = 3 Output: 1 1 1 2 1 3 Input: x = 4 Output: 1 1 1 1 2 1 1 2 2 3 1 4
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
La idea es usar una función recursiva, una array arr[] para almacenar todas las secuencias una por una y una variable de índice curr_idx para almacenar el siguiente índice actual en arr[]. A continuación se muestra el algoritmo.
1) Si la suma actual es igual a x, imprima la secuencia actual.
2) Coloque todos los números posibles desde 1 hasta x-curr_sum en curr_idx en la array. Aquí curr_sum es la suma de los elementos actuales en arr[]. Después de colocar un número, recurra a curr_sum + number y curr_idx+1.
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program to generate all non-increasing // sequences of sum equals to x #include<bits/stdc++.h> using namespace std; // Utility function to print array // arr[0..n-1] void printArr(int arr[], int n) { for(int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } // Recursive Function to generate all // non-increasing sequences // with sum x // arr[] --> Elements of current sequence // curr_sum --> Current Sum // curr_idx --> Current index in arr[] void generateUtil(int x, int arr[], int curr_sum, int curr_idx) { // If current sum is equal to x, // then we found a sequence if (curr_sum == x) { printArr(arr, curr_idx); return; } // Try placing all numbers from // 1 to x-curr_sum at current index int num = 1; // The placed number must also be // smaller than previously placed // numbers and it may be equal to // the previous stored value, i.e., // arr[curr_idx-1] if there exists // a previous number while (num <= x - curr_sum && (curr_idx == 0 || num <= arr[curr_idx - 1])) { // Place number at curr_idx arr[curr_idx] = num; // Recur generateUtil(x, arr, curr_sum + num, curr_idx + 1); // Try next number num++; } } // A wrapper over generateUtil() void generate(int x) { // Array to store sequences on by one int arr[x]; generateUtil(x, arr, 0, 0); } // Driver code int main() { int x = 5; generate(x); return 0; }
Java
// Java program to generate all non-increasing // sequences of sum equals to x class GFG { // Utility function to print array // arr[0..n-1] static void printArr(int arr[], int n) { for (int i = 0; i < n; i++) System.out.printf("%d ", arr[i]); System.out.println(""); } // Recursive Function to generate all // non-increasing sequences with sum x // arr[] --> Elements of current sequence // curr_sum --> Current Sum // curr_idx --> Current index in arr[] static void generateUtil(int x, int arr[], int curr_sum, int curr_idx) { // If current sum is equal to x, then // we found a sequence if (curr_sum == x) { printArr(arr, curr_idx); return; } // Try placing all numbers from 1 to // x-curr_sum at current index int num = 1; // The placed number must also be // smaller than previously placed // numbers and it may be equal to // the previous stored value, i.e., // arr[curr_idx-1] if there exists // a previous number while (num <= x - curr_sum && (curr_idx == 0 || num <= arr[curr_idx - 1])) { // Place number at curr_idx arr[curr_idx] = num; // Recur generateUtil(x, arr, curr_sum+num, curr_idx + 1); // Try next number num++; } } // A wrapper over generateUtil() static void generate(int x) { // Array to store sequences on by one int arr[] = new int [x]; generateUtil(x, arr, 0, 0); } // Driver program public static void main(String[] args) { int x = 5; generate(x); } } // This code is contributed by Smitha.
Python3
# Python3 program to generate all # non-increasing sequences of sum # equals to x # Utility function to print array # arr[0..n-1] def printArr(arr, n): for i in range(0, n): print(arr[i], end = " ") print("") # Recursive Function to generate # all non-increasing sequences # with sum x arr[] --> Elements # of current sequence # curr_sum --> Current Sum # curr_idx --> Current index in # arr[] def generateUtil(x, arr, curr_sum, curr_idx): # If current sum is equal to x, # then we found a sequence if (curr_sum == x): printArr(arr, curr_idx) return # Try placing all numbers from # 1 to x-curr_sum at current # index num = 1 # The placed number must also be # smaller than previously placed # numbers and it may be equal to # the previous stored value, i.e., # arr[curr_idx-1] if there exists # a previous number while (num <= x - curr_sum and (curr_idx == 0 or num <= arr[curr_idx - 1])): # Place number at curr_idx arr[curr_idx] = num # Recur generateUtil(x, arr, curr_sum + num, curr_idx + 1) # Try next number num += 1 # A wrapper over generateUtil() def generate(x): # Array to store sequences # on by one arr = [0] * x generateUtil(x, arr, 0, 0) # Driver program x = 5 generate(x) # This code is contributed # by Smitha.
C#
// C# program to generate all non-increasing // sequences of sum equals to x using System; class GFG { // Utility function to print array // arr[0..n-1] static void printArr(int []arr, int n) { for (int i = 0; i < n; i++) Console.Write( arr[i]); Console.WriteLine(); } // Recursive Function to generate all // non-increasing sequences with sum x // arr[] --> Elements of current sequence // curr_sum --> Current Sum // curr_idx --> Current index in arr[] static void generateUtil(int x, int []arr, int curr_sum, int curr_idx) { // If current sum is equal to x, then // we found a sequence if (curr_sum == x) { printArr(arr, curr_idx); return; } // Try placing all numbers from 1 to // x-curr_sum at current index int num = 1; // The placed number must also be // smaller than previously placed // numbers and it may be equal to // the previous stored value, i.e., // arr[curr_idx-1] if there exists // a previous number while (num <= x - curr_sum && (curr_idx == 0 || num <= arr[curr_idx - 1])) { // Place number at curr_idx arr[curr_idx] = num; // Recur generateUtil(x, arr, curr_sum+num, curr_idx + 1); // Try next number num++; } } // A wrapper over generateUtil() static void generate(int x) { // Array to store sequences on by one int []arr = new int [x]; generateUtil(x, arr, 0, 0); } // Driver program public static void Main() { int x = 5; generate(x); } } // This code is contributed by nitin mittal.
PHP
<?php // PHP program to generate all // non-increasing sequences // of sum equals to x // function to print array // arr[0..n-1] function printArr($arr, $n) { for ($i = 0; $i < $n; $i++) echo $arr[$i] , " "; echo " \n"; } // Recursive Function to generate // all non-increasing sequences // with sum x // arr[] --> Elements of current sequence // curr_sum --> Current Sum // curr_idx --> Current index in arr[] function generateUtil($x, $arr, $curr_sum, $curr_idx) { // If current sum is equal to x, // then we found a sequence if ($curr_sum == $x) { printArr($arr, $curr_idx); return; } // Try placing all numbers from // 1 to x-curr_sum at current index $num = 1; // The placed number must also be // smaller than previously placed // numbers and it may be equal to // the previous stored value, i.e., // arr[curr_idx-1] if there exists // a previous number while ($num <= $x - $curr_sum and ($curr_idx == 0 or $num <= $arr[$curr_idx - 1])) { // Place number at curr_idx $arr[$curr_idx] = $num; // Recur generateUtil($x, $arr, $curr_sum + $num, $curr_idx + 1); // Try next number $num++; } } // A wrapper over generateUtil() function generate($x) { // Array to store // sequences on by one $arr = array(); generateUtil($x, $arr, 0, 0); } // Driver Code $x = 5; generate($x); // This code is contributed by anuj_67. ?>
Javascript
<script> // Javascript program to generate all // non-increasing sequences of sum equals to x // Utility function to print array // arr[0..n-1] function printArr(arr, n) { for(let i = 0; i < n; i++) document.write(arr[i] + " "); document.write("</br>"); } // Recursive Function to generate all // non-increasing sequences with sum x // arr[] --> Elements of current sequence // curr_sum --> Current Sum // curr_idx --> Current index in arr[] function generateUtil(x, arr, curr_sum, curr_idx) { // If current sum is equal to x, then // we found a sequence if (curr_sum == x) { printArr(arr, curr_idx); return; } // Try placing all numbers from 1 to // x-curr_sum at current index let num = 1; // The placed number must also be // smaller than previously placed // numbers and it may be equal to // the previous stored value, i.e., // arr[curr_idx-1] if there exists // a previous number while (num <= x - curr_sum && (curr_idx == 0 || num <= arr[curr_idx - 1])) { // Place number at curr_idx arr[curr_idx] = num; // Recur generateUtil(x, arr, curr_sum + num, curr_idx + 1); // Try next number num++; } } // A wrapper over generateUtil() function generate(x) { // Array to store sequences on by one let arr = new Array(x); generateUtil(x, arr, 0, 0); } // Driver code let x = 5; generate(x); // This code is contributed by divyeshrabadiya07 </script>
Producción:
1 1 1 1 1 2 1 1 1 2 2 1 3 1 1 3 2 4 1 5
Este artículo es una contribución de Ashish Gupta . 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