Recuento de formas de elegir N personas que contengan al menos 4 niños y 1 niña de P Boys y Q Girls

Dados los números enteros N, P y Q, la tarea es encontrar el número de formas de formar un grupo de N personas que tenga al menos 4 niños y 1 niña de P niños y Q niñas.

Ejemplos:

Entrada: P = 5, Q = 2, N = 5
Salida: 10
Explicación: Suponga que el grupo dado es {m1, m2, m3, m4, m5} y {w1, w2}. Entonces las posibles combinaciones son:
m1 m2 m3 m4 w1
m2 m3 m4 m5 w1
m1 m3 m4 m5 w1
m1 m2 m4 m5 w1
m1 m2 m3 m5 w1
m1 m2 m3 m4 w2
m2 m3 m4 m5 w2
m1 m3 m4 m5 w2
m1 m2 m4 m5 w2
m1 m2 m3 m5 w2

Por lo tanto, la cuenta es 10.

Entrada: P = 5, Q = 2, N = 6
Salida: 7

Enfoque ingenuo: este problema se basa en la combinatoria , y los detalles del enfoque ingenuo ya se analizan en el Conjunto 1 de este problema.

Para algún valor general de P, Q y N podemos calcular el total de formas posibles utilizando la siguiente fórmula:

$_ {4}^{P}\textrm{C} \ast_{N-4}^{Q}\textrm{C} +_{5}^{P}\textrm{C} \ast_{N- 5}^{Q}\textrm{C} + . . . + _{N-2}^{P}\textrm{C} \ast _{2}^{Q}\textrm{C} + _{N-1}^{P}\textrm{C} \ast _ {1}^{Q}\textrm{C}$

dónde

$_{r}^{n}\textrm{C} = \frac{n!}{r!*(nr)!}$

En este enfoque, en cada paso estábamos calculando el valor de cada forma posible.
Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: para resolver este problema de manera eficiente, podemos usar la propiedad del Triángulo de Pascal para calcular el $_{r}^{n}\textrm{C}$ , es decir

1
1 1
1 2 1
1 3 3 1
.
.
.

que no es más que

$_ {0}^{0}\textrm{C}$
$_ {0}^{1}\textrm{C}$    $_ {1}^{1}\textrm{C}$
$_ {0}^{2}\textrm{C}$    $_ {1}^{2}\textrm{C}$    $_ {2}^{2}\textrm{C}$
$_ {0}^{3}\textrm{C}$    $_{1}^{3}\textrm{C}$    $_{2}^{3}\textrm{C}$    $_{3}^{3}\textrm{C}$
.
.
.

Siga los pasos que se mencionan a continuación:

Utilice el triángulo pascal para precalcular los valores de la combinación.
Comience iterando un ciclo desde i = 4 hasta i = P y haga lo siguiente para cada iteración.
Compruebe si (Ni) ≥ 1 y (Ni) ≤ Q .
Si se cumple la condición, cuente las formas posibles para i hombres y (Ni) mujeres , de lo contrario, omita el paso.
Suma el conteo con el número total de formas.
Devuelva el recuento total como su respuesta.

A continuación se muestra la implementación del enfoque:

C++

#include <bits/stdc++.h>
using namespace std;
 
long long int pascal[31][31];
 
// Function to calculate the pascal triangle
void pascalTriangle()
{
    pascal[0][0] = 1;
    pascal[1][0] = 1;
    pascal[1][1] = 1;
 
    // Loop to calculate values of
    // pascal triangle
    for (int i = 2; i < 31; i++) {
        pascal[i][0] = 1;
        for (int j = 1; j < i; j++)
            pascal[i][j]
                = pascal[i - 1][j]
                  + pascal[i - 1][j - 1];
        pascal[i][i] = 1;
    }
}
 
// Function to calculate the number of ways
long long int countWays(int n, int p, int q)
{
 
    // Variable to store the answer
    long long int sum = 0;
 
    // Loop to calculate the number of ways
    for (long long int i = 4; i <= p; i++) {
        if (n - i >= 1 && n - i <= q)
            sum += pascal[p][i]
                   * pascal[q][n - i];
    }
    return sum;
}
 
// Driver code
int main()
{
    pascalTriangle();
 
    int P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    cout << countWays(N, P, Q) << endl;
    return 0;
}

Java

import java.util.*;
public class GFG
{
     
static long [][]pascal = new long[31][31];
 
// Function to calculate the pascal triangle
static void pascalTriangle()
{
    pascal[0][0] = 1;
    pascal[1][0] = 1;
    pascal[1][1] = 1;
 
    // Loop to calculate values of
    // pascal triangle
    for (int i = 2; i < 31; i++) {
        pascal[i][0] = (int)1;
        for (int j = 1; j < i; j++)
            pascal[i][j]
                = pascal[i - 1][j]
                  + pascal[i - 1][j - 1];
        pascal[i][i] = 1;
    }
}
 
// Function to calculate the number of ways
static long countWays(int n, int p, int q)
{
 
    // Variable to store the answer
    long sum = 0;
 
    // Loop to calculate the number of ways
    for (int i = 4; i <= p; i++) {
        if (n - i >= 1 && n - i <= q) {
            sum += (int)pascal[p][i]
                   * (int)pascal[q][n - i];
        }
    }
    return sum;
}
 
// Driver code
public static void main(String args[])
{
    pascalTriangle();
 
    int P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    System.out.print(countWays(N, P, Q));
 
}
}
// This code is contributed by Samim Hossain Mondal.

Python3

# Python3 program for the above approach
import numpy as np
 
pascal = np.zeros((31,31));
 
# Function to calculate the pascal triangle
def pascalTriangle() :
     
    pascal[0][0] = 1;
    pascal[1][0] = 1;
    pascal[1][1] = 1;
 
    # Loop to calculate values of
    # pascal triangle
    for i in range(2, 31) :
         
        pascal[i][0] = 1;
        for j in range(1, i) :
            pascal[i][j] = pascal[i - 1][j] + pascal[i - 1][j - 1];
         
        pascal[i][i] = 1;
   
 
# Function to calculate the number of ways
def countWays(n, p, q) :
 
    # Variable to store the answer
    sum = 0;
 
    # Loop to calculate the number of ways
    for i in range(4, p + 1) :
         
        if (n - i >= 1 and n - i <= q) :
             
            sum += pascal[p][i] * pascal[q][n - i];
 
    return int(sum);
 
# Driver code
if __name__ ==  "__main__" :
 
    pascalTriangle();
 
    P = 5; Q = 2; N = 5;
 
    # Calculate possible ways for given
    # N, P, and Q
    print(countWays(N, P, Q));
 
    # This code is contributed by AnkThon

C#

using System;
class GFG
{
     
static long [,]pascal = new long[31, 31];
 
// Function to calculate the pascal triangle
static void pascalTriangle()
{
    pascal[0, 0] = 1;
    pascal[1, 0] = 1;
    pascal[1, 1] = 1;
 
    // Loop to calculate values of
    // pascal triangle
    for (int i = 2; i < 31; i++) {
        pascal[i, 0] = (int)1;
        for (int j = 1; j < i; j++)
            pascal[i, j]
                = pascal[i - 1, j]
                  + pascal[i - 1, j - 1];
        pascal[i, i] = 1;
    }
}
 
// Function to calculate the number of ways
static long countWays(int n, int p, int q)
{
 
    // Variable to store the answer
    long sum = 0;
 
    // Loop to calculate the number of ways
    for (int i = 4; i <= p; i++) {
        if (n - i >= 1 && n - i <= q) {
            sum += (int)pascal[p, i]
                   * (int)pascal[q, n - i];
        }
    }
    return sum;
}
 
// Driver code
public static void Main()
{
    pascalTriangle();
 
    int P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    Console.Write(countWays(N, P, Q));
 
}
}
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
 
    let pascal = new Array(31).fill(0).map(() => new Array(31).fill(0));
 
    // Function to calculate the pascal triangle
    const pascalTriangle = () => {
        pascal[0][0] = 1;
        pascal[1][0] = 1;
        pascal[1][1] = 1;
 
        // Loop to calculate values of
        // pascal triangle
        for (let i = 2; i < 31; i++) {
            pascal[i][0] = 1;
            for (let j = 1; j < i; j++)
                pascal[i][j]
                    = pascal[i - 1][j]
                    + pascal[i - 1][j - 1];
            pascal[i][i] = 1;
        }
    }
 
    // Function to calculate the number of ways
    const countWays = (n, p, q) => {
 
        // Variable to store the answer
        let sum = 0;
 
        // Loop to calculate the number of ways
        for (let i = 4; i <= p; i++) {
            if (n - i >= 1 && n - i <= q)
                sum += pascal[p][i]
                    * pascal[q][n - i];
        }
        return sum;
    }
 
    // Driver code
    pascalTriangle();
 
    let P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    document.write(countWays(N, P, Q));
 
// This code is contributed by rakeshsahni
 
</script>

Producción

Tiempo Complejidad: O(N)
Espacio Auxiliar: O(N ² )

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Recuento de formas de elegir N personas que contengan al menos 4 niños y 1 niña de P Boys y Q Girls | conjunto 2

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta