Dado un número N, la tarea es encontrar el número de formas en que se puede dividir N, es decir, el número de formas en que N se puede expresar como una suma de números enteros positivos.
Nota: N también debe considerarse una forma de expresarlo como una suma de números enteros positivos.
Ejemplos:
Entrada: N = 5
Salida: 7
5 se puede dividir de las siguientes maneras:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
Entrada: N = 10
Salida: 42
Esta publicación ya se ha discutido en Formas de escribir n como suma de dos o más números enteros positivos . En esta publicación, se discute un enfoque eficiente.
Enfoque (Usando la recurrencia de Euler):
Si p(n) es el número de particiones de N, entonces puede ser generado por la siguiente función generadora:
Usando esta fórmula y el teorema del número pentagonal de Euler, podemos derivar la siguiente relación de recurrencia para p( n): (Consulte el artículo de Wikipedia para obtener más detalles)
donde k = 1, -1, 2, -2, 3, -3, … y p(n) = 0 para n < 0.
A continuación se muestra la implementación del enfoque anterior :
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find the number // of partitions of N long long partitions(int n) { vector<long long> p(n + 1, 0); // Base case p[0] = 1; for (int i = 1; i <= n; ++i) { int k = 1; while ((k * (3 * k - 1)) / 2 <= i) { p[i] += (k % 2 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2]; if (k > 0) k *= -1; else k = 1 - k; } } return p[n]; } // Driver code int main() { int N = 20; cout << partitions(N); return 0; }
Java
// Java implementation of above approach class GFG { // Function to find the number // of partitions of N static long partitions(int n) { long p[] = new long[n + 1]; // Base case p[0] = 1; for (int i = 1; i <= n; ++i) { int k = 1; while ((k * (3 * k - 1)) / 2 <= i) { p[i] += (k % 2 != 0 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2]; if (k > 0) { k *= -1; } else { k = 1 - k; } } } return p[n]; } // Driver code public static void main(String[] args) { int N = 20; System.out.println(partitions(N)); } } // This code is contributed by Rajput-JI
Python 3
# Python 3 implementation of # above approach # Function to find the number # of partitions of N def partitions(n): p = [0] * (n + 1) # Base case p[0] = 1 for i in range(1, n + 1): k = 1 while ((k * (3 * k - 1)) / 2 <= i) : p[i] += ((1 if k % 2 else -1) * p[i - (k * (3 * k - 1)) // 2]) if (k > 0): k *= -1 else: k = 1 - k return p[n] # Driver code if __name__ == "__main__": N = 20 print(partitions(N)) # This code is contributed # by ChitraNayal
C#
// C# implementation of above approach using System; class GFG { // Function to find the number // of partitions of N static long partitions(int n) { long []p = new long[n + 1]; // Base case p[0] = 1; for (int i = 1; i <= n; ++i) { int k = 1; while ((k * (3 * k - 1)) / 2 <= i) { p[i] += (k % 2 != 0 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2]; if (k > 0) { k *= -1; } else { k = 1 - k; } } } return p[n]; } // Driver code public static void Main(String[] args) { int N = 20; Console.WriteLine(partitions(N)); } } // This code has been contributed by 29AjayKumar
PHP
<?php // PHP implementation of above approach // Function to find the number // of partitions of N function partitions($n) { $p = array_fill(0, $n + 1, 0); // Base case $p[0] = 1; for ($i = 1; $i < $n + 1; $i++) { $k = 1; while (($k * (3 * $k - 1)) / 2 <= $i) { $p[$i] += (($k % 2 ? 1 : -1) * $p[$i - ($k * (3 * $k - 1)) / 2]); if ($k > 0) $k *= -1; else $k = 1 - $k; } } return $p[$n]; } // Driver Code $N = 20; print(partitions($N)); // This code is contributed // by mits ?>
Javascript
<script> // javascript implementation of above approach // Function to find the number // of partitions of N function partitions(n) { var p = Array(n + 1).fill(0); // Base case p[0] = 1; for (i = 1; i <= n; ++i) { var k = 1; while ((k * (3 * k - 1)) / 2 <= i) { p[i] += (k % 2 != 0 ? 1 : -1) * p[i - (k * (3 * k - 1)) / 2]; if (k > 0) { k *= -1; } else { k = 1 - k; } } } return p[n]; } // Driver code var N = 20; document.write(partitions(N)); // This code is contributed by todaysgaurav </script>
627
Complejidad de tiempo : O(N√N)
Complejidad de espacio : O(N)
Publicación traducida automáticamente
Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA