Formas de escribir N como suma de dos o más enteros positivos | Conjunto-2

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:
5 se puede dividir de las siguientes maneras: 

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:
\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right)
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)
p(n) = p(n - 1) + p (n - 2) - p(n - 5) - p(n - 7) + \cdots + (-1)^{|{k} - 1|} \frac{k(3k - 1)}{2}
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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *