Dado un palo de tamaño N, encuentre el número de formas en que se puede cortar en K pedazos de modo que la longitud de cada pedazo sea mayor que 0.
Ejemplos:
Input : N = 5
K = 2
Output : 4
Input : N = 15
K = 5
Output : 1001
Resolver esta pregunta es equivalente a resolver la ecuación matemática x 1 + x 2 + ….. + x K = N
Podemos resolver esto usando el método de barras y estrellas en Combinatoria, de donde obtenemos el hecho de que el número de enteros positivos soluciones a esta ecuación es (N – 1) C (K – 1) , donde N C K es N! / ((N – K) ! * (K!)), donde ! significa factorial.
En C++ y Java, para valores grandes de factoriales, puede haber errores de desbordamiento. En ese caso, podemos introducir un número primo grande como 10 7 + 7 para modificar la respuesta. Podemos calcular nCr % p usando el Teorema de Lucas.
Sin embargo, Python puede manejar valores grandes sin desbordamiento.
C++
// C++ program to calculate the number of ways
// to divide a stick of length n into k pieces
#include <bits/stdc++.h>
using namespace std;
// function to generate nCk or nChoosek
unsigned long long nCr(unsigned long long n,
unsigned long long r)
{
if (n < r)
return 0;
// Reduces to the form n! / n!
if (r == 0)
return 1;
// nCr has been simplified to this form by
// expanding numerator and denominator to
// the form n(n - 1)(n - 2)...(n - r + 1)
// -----------------------------
// (r!)
// in the above equation, (n - r)! is cancelled
// out in the numerator and denominator
unsigned long long numerator = 1;
for (int i = n; i > n - r; i--)
numerator = (numerator * i);
unsigned long long denominator = 1;
for (int i = 1; i < r + 1; i++)
denominator = (denominator * i);
return (numerator / denominator);
}
// Returns number of ways to cut
// a rod of length N into K pieces.
unsigned long long countWays(unsigned long long N,
unsigned long long K)
{
return nCr(N - 1, K - 1);
}
// Driver code
int main()
{
unsigned long long N = 5;
unsigned long long K = 2;
cout << countWays(N, K);
return 0;
}
Java
// Java program to find the number of ways in which
// a stick of length n can be divided into K pieces
import java.io.*;
import java.util.*;
class GFG
{
// function to generate nCk or nChoosek
public static int nCr(int n, int r)
{
if (n < r)
return 0;
// Reduces to the form n! / n!
if (r == 0)
return 1;
// nCr has been simplified to this form by
// expanding numerator and denominator to
// the form n(n - 1)(n - 2)...(n - r + 1)
// -----------------------------
// (r!)
// in the above equation, (n-r)! is cancelled
// out in the numerator and denominator
int numerator = 1;
for (int i = n ; i > n - r ; i--)
numerator = (numerator * i);
int denominator = 1;
for (int i = 1 ; i < r + 1 ; i++)
denominator = (denominator * i);
return (numerator / denominator);
}
// Returns number of ways to cut
// a rod of length N into K pieces
public static int countWays(int N, int K)
{
return nCr(N - 1, K - 1);
}
public static void main(String[] args)
{
int N = 5;
int K = 2;
System.out.println(countWays(N, K));
}
}
Python3
# Python program to find the number # of ways in which a stick of length # n can be divided into K pieces # function to generate nCk or nChoosek def nCr(n, r): if (n < r): return 0 # reduces to the form n! / n! if (r == 0): return 1 # nCr has been simplified to this form by # expanding numerator and denominator to # the form n(n - 1)(n - 2)...(n - r + 1) # ----------------------------- # (r!) # in the above equation, (n-r)! is cancelled # out in the numerator and denominator numerator = 1 for i in range(n, n - r, -1): numerator = numerator * i denominator = 1 for i in range(1, r + 1): denominator = denominator * i return (numerator // denominator) # Returns number of ways to cut # a rod of length N into K pieces. def countWays(N, K) : return nCr(N - 1, K - 1); # Driver code N = 5 K = 2 print(countWays(N, K))
C#
// C# program to find the number of
// ways in which a stick of length n
// can be divided into K pieces
using System;
class GFG
{
// function to generate nCk or nChoosek
public static int nCr(int n, int r)
{
if (n < r)
return 0;
// Reduces to the form n! / n!
if (r == 0)
return 1;
// nCr has been simplified to this form by
// expanding numerator and denominator to
// the form n(n - 1)(n - 2)...(n - r + 1)
// -----------------------------
// (r!)
// in the above equation, (n-r)! is cancelled
// out in the numerator and denominator
int numerator = 1;
for (int i = n; i > n - r; i--)
numerator = (numerator * i);
int denominator = 1;
for (int i = 1; i < r + 1; i++)
denominator = (denominator * i);
return (numerator / denominator);
}
// Returns number of ways to cut
// a rod of length N into K pieces
public static int countWays(int N, int K)
{
return nCr(N - 1, K - 1);
}
public static void Main()
{
int N = 5;
int K = 2;
Console.Write(countWays(N, K));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to calculate the
// number of ways to divide a
// stick of length n into k pieces
// function to generate nCk or nChoosek
function nCr($n, $r)
{
if ($n < $r)
return 0;
// Reduces to the form n! / n!
if ($r == 0)
return 1;
// nCr has been simplified to this form by
// expanding numerator and denominator to
// the form n(n - 1)(n - 2)...(n - r + 1)
// -----------------------------
// (r!)
// in the above equation, (n - r)! is cancelled
// out in the numerator and denominator
$numerator = 1;
for ($i = $n; $i > $n - $r; $i--)
$numerator = ($numerator * $i);
$denominator = 1;
for ($i = 1; $i < $r + 1; $i++)
$denominator = ($denominator * $i);
return (floor($numerator / $denominator));
}
// Returns number of ways to cut
// a rod of length N into K pieces.
function countWays($N, $K)
{
return nCr($N - 1, $K - 1);
}
// Driver code
$N = 5;
$K = 2;
echo countWays($N, $K);
return 0;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
//Javascript Implementation
// to calculate the number of ways
// to divide a stick of length n into k pieces
// function to generate nCk or nChoosek
function nCr(n,r)
{
if (n < r)
return 0;
// Reduces to the form n! / n!
if (r == 0)
return 1;
// nCr has been simplified to this form by
// expanding numerator and denominator to
// the form n(n - 1)(n - 2)...(n - r + 1)
// -----------------------------
// (r!)
// in the above equation, (n - r)! is cancelled
// out in the numerator and denominator
var numerator = 1;
for (var i = n; i > n - r; i--)
numerator = (numerator * i);
var denominator = 1;
for (var i = 1; i < r + 1; i++)
denominator = (denominator * i);
return Math.floor(numerator / denominator);
}
// Returns number of ways to cut
// a rod of length N into K pieces.
function countWays(N,K)
{
return nCr(N - 1, K - 1);
}
// Driver code
var N = 5;
var K = 2;
document.write(countWays(N, K));
// This code is contributed by shubhamsingh10
</script>
Producción :
4
Ejercicio:
Amplíe el problema anterior con 0 piezas de longitud permitidas. Sugerencia: el número de soluciones se puede encontrar de manera similar al escribir cada x i como y i – 1, y obtenemos una ecuación y 1 + y 2 + ….. + y K = N + K . El número de soluciones para esta ecuación es (N + K – 1) C (K – 1)
Este artículo es una contribución de Deepak Srivatsav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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