Dados N y K. La tarea es averiguar de cuántas maneras diferentes hay para representar N como la suma de K enteros distintos de cero.
Ejemplos:
Entrada: N = 5, K = 3
Salida: 6
Las posibles combinaciones de números enteros son:
( 1, 1, 3 )
( 1, 3, 1 )
( 3, 1, 1 )
( 1, 2, 2 )
( 2, 2, 1 )
( 2, 1, 2 )Entrada: N = 10, K = 4
Salida: 84
El enfoque del problema es observar una secuencia y usar combinaciones para resolver el problema. Para obtener un número N, se requieren N 1, la suma de N 1 dará N. El problema le permite usar K enteros solo para hacer N.
Observación:
Let's take N = 5 and K = 3, then all
possible combinations of K numbers are: ( 1, 1, 3 )
( 1, 3, 1 )
( 3, 1, 1 )
( 1, 2, 2 )
( 2, 2, 1 )
( 2, 1, 2 )
The above can be rewritten as: ( 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 )
De lo anterior, se puede sacar la conclusión de que de los N 1, se deben colocar k-1 comas entre los N 1 y los lugares restantes se deben llenar con signos ‘+’. Todas las combinaciones de colocar comas k-1 y colocar signos ‘+’ en los lugares restantes serán la respuesta. Entonces, en general, para N habrá N-1 espacios entre todos los 1, y de esos, elija k-1 y coloque una coma entre esos 1. Entre los demás 1, coloque los signos ‘+’. Entonces, la forma de elegir objetos K-1 de N-1 es 
. El enfoque de programación dinámica se utiliza para calcular .
A continuación se muestra la implementación del enfoque anterior:
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;
}
C
// C program to calculate Different ways to
// represent N as sum of K non-zero integers.
#include <stdio.h>
int min(int a, int b)
{
int min = a;
if(min > b)
min = b;
return min;
}
// 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;
printf("Total number of different ways are %d",binomialCoeff(n - 1, k - 1));
return 0;
}
// This code is contributed by kothavvsaakash.
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>
Total number of different ways are 6
Complejidad temporal: O(N * K)
Espacio auxiliar: O(N * K)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA