Различные способы представления N в виде суммы K ненулевых целых чисел

Опубликовано: 16 Января, 2022

Для заданных N и K. Задача состоит в том, чтобы выяснить, сколько существует различных способов представить N как сумму K ненулевых целых чисел.

Примеры:

Input: N = 5, K = 3 
Output:
The possible combinations of integers are: 
( 1, 1, 3 ) 
( 1, 3, 1 ) 
( 3, 1, 1 ) 
( 1, 2, 2 ) 
( 2, 2, 1 ) 
( 2, 1, 2 )

Input: N = 10, K = 4 
Output: 84

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход к проблеме заключается в соблюдении последовательности и использовании комбинаций для решения проблемы. Чтобы получить число N, требуется N единиц, суммирование N единиц даст N. Задача позволяет использовать K целых чисел только для получения N.

Наблюдение:

 Возьмем N = 5 и K = 3, тогда все 
возможные комбинации чисел K: (1, 1, 3)
                                        (1, 3, 1)
                                        (3, 1, 1)
                                        (1, 2, 2)
                                        (2, 2, 1)
                                        (2, 1, 2)

Вышеупомянутое можно переписать как: (1, 1, 1 + 1 + 1)
                               (1, 1 + 1 + 1, 1)
                               (1 + 1 + 1, 1, 1)
                               (1, 1 + 1, 1 + 1)
                               (1 + 1, 1 + 1, 1)
                               (1 + 1, 1, 1 + 1)

Из вышесказанного можно сделать вывод, что из N 1, k-1 запятые должны быть помещены между N 1, а остальные места должны быть заполнены знаками «+». Все комбинации расстановки k-1 запятых и расстановки знаков «+» в оставшихся местах будут ответом. Итак, в общем, для N будет N-1 пробелов между всеми 1, и из них выберите k-1 и поместите запятую между этими 1. Между остальными единицами поместите знаки «+». Таким образом, способ выбора объектов K-1 из N-1 следующий: . Подход динамического программирования используется для расчета .

Below is the implementation of the above approach: 

C++

// CPP program to calculate Different ways to
// represent N as sum of K non-zero integers.
#include <bits/stdc++.h>
using namespace std;
 
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
    int C[n + 1][k + 1];
    int i, j;
 
    // Calculate value of Binomial Coefficient in bottom up manner
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= min(i, k); j++) {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value using previously stored values
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
 
    return C[n][k];
}
 
// Driver Code
int main()
{
    int n = 5, k = 3;
    cout << "Total number of different ways are "
         << binomialCoeff(n - 1, k - 1);
    return 0;
}

Java

// Java program to calculate
// Different ways to represent
// N as sum of K non-zero integers.
import java.io.*;
 
class GFG
{
 
// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n,
                         int k)
{
    int C[][] = new int [n + 1][k + 1];
    int i, j;
 
    // Calculate value of Binomial
    // Coefficient in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (j = 0;
             j <= Math.min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value using
            // previously stored values
            else
                C[i][j] = C[i - 1][j - 1] +
                          C[i - 1][j];
        }
    }
 
    return C[n][k];
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 5, k = 3;
    System.out.println( "Total number of " +
                     "different ways are " +
                        binomialCoeff(n - 1,
                                      k - 1));
}
}
 
// This code is contributed
// by anuj_67.

Python3

# python 3 program to calculate Different ways to
# represent N as sum of K non-zero integers.
 
# Returns value of Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
    C = [[0 for i in range(k+1)]for i in range(n+1)]
 
    # Calculate value of Binomial Coefficient in bottom up manner
    for i in range(0,n+1,1):
        for j in range(0,min(i, k)+1,1):
            # Base Cases
            if (j == 0 or j == i):
                C[i][j] = 1
 
            # Calculate value using previously stored values
            else:
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
 
    return C[n][k]
 
# Driver Code
if __name__ == "__main__":
    n = 5
    k = 3
    print("Total number of different ways are",binomialCoeff(n - 1, k - 1))
     
# This code is contributed by
# Sanjit_Prasad

C#

// C# program to calculate
// Different ways to represent
// N as sum of K non-zero integers.
using System;
 
class GFG
{
 
// Returns value of Binomial
// Coefficient C(n, k)
static int binomialCoeff(int n,
                         int k)
{
    int [,]C = new int [n + 1,
                        k + 1];
    int i, j;
 
    // Calculate value of
    // Binomial Coefficient
    // in bottom up manner
    for (i = 0; i <= n; i++)
    {
        for (j = 0;
            j <= Math.Min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i, j] = 1;
 
            // Calculate value using
            // previously stored values
            else
                C[i, j] = C[i - 1, j - 1] +
                          C[i - 1, j];
        }
    }
 
    return C[n,k];
}
 
// Driver Code
public static void Main ()
{
    int n = 5, k = 3;
    Console.WriteLine( "Total number of " +
                    "different ways are " +
                       binomialCoeff(n - 1,
                                   k - 1));
}
}
 
// This code is contributed
// by anuj_67.

PHP

<?php
// PHP program to calculate
// Different ways to represent
// N as sum of K non-zero integers.
 
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff($n, $k)
{
    $C = array(array());
    $i; $j;
 
    // Calculate value of Binomial
    // Coefficient in bottom up manner
    for ($i = 0; $i <= $n; $i++)
    {
        for ($j = 0;
             $j <= min($i, $k); $j++)
        {
            // Base Cases
            if ($j == 0 or $j == $i)
                $C[$i][$j] = 1;
 
            // Calculate value using
            // previously stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] +
                             $C[$i - 1][$j];
        }
    }
 
    return $C[$n][$k];
}
 
// Driver Code
$n = 5; $k = 3;
echo "Total number of " ,
  "different ways are " ,
   binomialCoeff($n - 1,
                 $k - 1);
 
// This code is contributed
// by anuj_67.
?>

Javascript

<script>
    // Javascript program to calculate
    // Different ways to represent
    // N as sum of K non-zero integers.
     
    // Returns value of Binomial
    // Coefficient C(n, k)
    function binomialCoeff(n, k)
    {
        let C = new Array(n + 1);
        for(let i = 0; i < n + 1; i ++)
        {
            C[i] = new Array(k + 1);
            for(let j = 0; j < k + 1; j++)
            {
                C[i][j] = 0;
            }
        }
        let i, j;
 
        // Calculate value of Binomial
        // Coefficient in bottom up manner
        for (i = 0; i <= n; i++)
        {
            for (j = 0; j <= Math.min(i, k); j++)
            {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
 
                // Calculate value using
                // previously stored values
                else
                    C[i][j] = C[i - 1][j - 1] +
                              C[i - 1][j];
            }
        }
 
        return C[n][k];
    }
     
    let n = 5, k = 3;
    document.write( "Total number of " +
                     "different ways are " +
                        binomialCoeff(n - 1,
                                      k - 1));
     
</script>
Output: 
Total number of different ways are 6

 

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.