Rompecabezas de caída de huevos (coeficiente binomial y solución de búsqueda binaria)

Dados n huevos yk pisos, encuentre el número mínimo de intentos necesarios en el peor de los casos para encontrar el piso debajo del cual todos los pisos son seguros. Un piso es seguro si dejar caer un huevo no lo rompe. Por favor vea n huevos yk pisos. para declaraciones completas

Ejemplo

Input : n = 2, k = 10
Output : 4
We first try from 4-th floor. Two cases arise,
(1) If egg breaks, we have one egg left so we
    need three more trials.
(2) If egg does not break, we try next from 7-th
    floor. Again two cases arise.
We can notice that if we choose 4th floor as first
floor, 7-th as next floor and 9 as next of next floor,
we never exceed more than 4 trials.

Input : n = 2. k = 100
Output : 14

Hemos discutido el problema de 2 huevos y k pisos . También hemos discutido una solución de programación dinámica para encontrar la solución. La solución de programación dinámica se basa en la naturaleza recursiva del problema. Veamos la fórmula recursiva discutida desde una perspectiva diferente.

¿Cuántos pisos podemos cubrir con x intentos?  
Cuando se nos cae un huevo se dan dos casos. 

  1. Si el huevo se rompe, nos quedan pruebas x-1 y huevos n-1.
  2. Si el huevo no se rompe, nos quedan x-1 pruebas y n huevos
Let maxFloors(x, n) be the maximum number of floors 
that we can cover with x trials and n eggs. From above 
two cases, we can write.

maxFloors(x, n) = maxFloors(x-1, n-1) + maxFloors(x-1, n) + 1
For all x >= 1 and n >= 1

Base cases : 
We can't cover any floor with 0 trials or 0 eggs
maxFloors(0, n) = 0
maxFloors(x, 0) = 0

Since we need to cover k floors, 
maxFloors(x, n) >= k           ----------(1)

The above recurrence simplifies to following,
Refer this for proof.

maxFloors(x, n) = ∑xCi
                  1 <= i <= n   ----------(2)
Here C represents Binomial Coefficient.

From above two equations, we can say.
&Sum;xCj  >= k
1 <= i <= n
Basically we need to find minimum value of x
that satisfies above inequality. We can find
such x using Binary Search.

C++

// C++ program to find minimum
// number of trials in worst case.
#include <bits/stdc++.h>
 
using namespace std;
 
// Find sum of binomial coefficients xCi
// (where i varies from 1 to n).
int binomialCoeff(int x, int n, int k)
{
    int sum = 0, term = 1;
    for (int i = 1; i <= n; ++i) {
        term *= x - i + 1;
        term /= i;
        sum += term;
        if (sum > k)
            return sum;
    }
    return sum;
}
 
// Do binary search to find minimum
// number of trials in worst case.
int minTrials(int n, int k)
{
    // Initialize low and high as 1st
    // and last floors
    int low = 1, high = k;
 
    // Do binary search, for every mid,
    // find sum of binomial coefficients and
    // check if the sum is greater than k or not.
    while (low < high) {
        int mid = (low + high) / 2;
        if (binomialCoeff(mid, n, k) < k)
            low = mid + 1;
        else
            high = mid;
    }
 
    return low;
}
 
/* Driver code*/
int main()
{
    cout << minTrials(2, 10);
    return 0;
}

Java

// Java program to find minimum
// number of trials in worst case.
class Geeks {
 
    // Find sum of binomial coefficients xCi
    // (where i varies from 1 to n). If the sum
    // becomes more than K
    static int binomialCoeff(int x, int n, int k)
    {
        int sum = 0, term = 1;
        for (int i = 1; i <= n && sum < k; ++i) {
            term *= x - i + 1;
            term /= i;
            sum += term;
        }
        return sum;
    }
 
    // Do binary search to find minimum
    // number of trials in worst case.
    static int minTrials(int n, int k)
    {
        // Initialize low and high as 1st
        // and last floors
        int low = 1, high = k;
 
        // Do binary search, for every mid,
        // find sum of binomial coefficients and
        // check if the sum is greater than k or not.
        while (low < high) {
            int mid = (low + high) / 2;
            if (binomialCoeff(mid, n, k) < k)
                low = mid + 1;
            else
                high = mid;
        }
 
        return low;
    }
 
    /* Driver code*/
    public static void main(String args[])
    {
        System.out.println(minTrials(2, 10));
    }
}
 
// This code is contributed by ankita_saini

Python3

# Python3 program to find minimum
# number of trials in worst case.
 
# Find sum of binomial coefficients
# xCi (where i varies from 1 to n).
# If the sum becomes more than K
 
 
def binomialCoeff(x, n, k):
 
    sum = 0
    term = 1
    i = 1
    while(i <= n and sum < k):
        term *= x - i + 1
        term /= i
        sum += term
        i += 1
    return sum
 
# Do binary search to find minimum
# number of trials in worst case.
 
 
def minTrials(n, k):
 
    # Initialize low and high as
    # 1st and last floors
    low = 1
    high = k
 
    # Do binary search, for every
    # mid, find sum of binomial
    # coefficients and check if
    # the sum is greater than k or not.
    while (low < high):
 
        mid = int((low + high) / 2)
        if (binomialCoeff(mid, n, k) < k):
            low = mid + 1
        else:
            high = mid
 
    return int(low)
 
 
# Driver Code
print(minTrials(2, 10))
 
# This code is contributed
# by mits

C#

// C# program to find minimum
// number of trials in worst case.
using System;
 
class GFG {
 
    // Find sum of binomial coefficients
    // xCi (where i varies from 1 to n).
    // If the sum becomes more than K
    static int binomialCoeff(int x, int n, int k)
    {
        int sum = 0, term = 1;
        for (int i = 1; i <= n && sum < k; ++i) {
            term *= x - i + 1;
            term /= i;
            sum += term;
        }
        return sum;
    }
 
    // Do binary search to find minimum
    // number of trials in worst case.
    static int minTrials(int n, int k)
    {
        // Initialize low and high
        // as 1st and last floors
        int low = 1, high = k;
 
        // Do binary search, for every
        // mid, find sum of binomial
        // coefficients and check if the
        // sum is greater than k or not.
        while (low < high) {
            int mid = (low + high) / 2;
            if (binomialCoeff(mid, n, k) < k)
                low = mid + 1;
            else
                high = mid;
        }
 
        return low;
    }
 
    // Driver Code
    public static void Main()
    {
        Console.WriteLine(minTrials(2, 10));
    }
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

PHP

<?php
// PHP program to find minimum
// number of trials in worst case.
 
// Find sum of binomial coefficients
// xCi (where i varies from 1 to n).
// If the sum becomes more than K
function binomialCoeff($x, $n, $k)
{
    $sum = 0; $term = 1;
    for ($i = 1; $i <= $n &&
         $sum < $k; ++$i)
    {
        $term *= $x - $i + 1;
        $term /= $i;
        $sum += $term;
    }
    return $sum;
}
 
// Do binary search to find minimum
// number of trials in worst case.
function minTrials($n, $k)
{
    // Initialize low and high as
    // 1st and last floors
    $low = 1; $high = $k;
 
    // Do binary search, for every
    // mid, find sum of binomial
    // coefficients and check if
    // the sum is greater than k or not.
    while ($low < $high)
    {
        $mid = ($low + $high) / 2;
        if (binomialCoeff($mid, $n, $k) < $k)
            $low = $mid + 1;
        else
            $high = $mid;
    }
 
    return (int)$low;
}
 
// Driver Code
echo minTrials(2, 10);
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

Javascript

<script>
 
// Javascript program to find minimum
// number of trials in worst case.
 
// Find sum of binomial coefficients xCi
// (where i varies from 1 to n). If the sum
// becomes more than K
function binomialCoeff(x, n, k)
{
    var sum = 0, term = 1;
    for(var i = 1; i <= n && sum < k; ++i)
    {
        term *= x - i + 1;
        term /= i;
        sum += term;
    }
    return sum;
}
 
// Do binary search to find minimum
// number of trials in worst case.
function minTrials(n, k)
{
     
    // Initialize low and high as 1st
    //and last floors
    var low = 1, high = k;
 
    // Do binary search, for every mid,
    // find sum of binomial coefficients and
    // check if the sum is greater than k or not.
    while (low < high)
    {
        var mid = parseInt((low + high) / 2);
        if (binomialCoeff(mid, n, k) < k)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}
 
// Driver code
document.write(minTrials(2, 10));
 
// This code is contributed by shivanisinghss2110
 
</script>
Producción

4

Complejidad de tiempo: O(n Log k)

Otro enfoque:

El enfoque con O(n * k^2) se ha discutido anteriormente, donde dp[n][k] = 1 + max(dp[n – 1][i – 1], dp[n][k – i] ) para i en 1…k. Verificó todas las posibilidades en ese enfoque.

Considere el problema de una manera diferente:

dp[m][x] means that, given x eggs and m moves,
what is the maximum number of floors that can be checked

The dp equation is: dp[m][x] = 1 + dp[m - 1][x - 1] + dp[m - 1][x],
which means we take 1 move to a floor.
If egg breaks, then we can check dp[m - 1][x - 1] floors.
If egg doesn't break, then we can check dp[m - 1][x] floors.

C++

// C++ program to find minimum number of trials in worst
// case.
#include <bits/stdc++.h>
using namespace std;
 
int minTrials(int n, int k)
{
    // Initialize 2D of size (k+1) * (n+1).
    vector<vector<int> > dp(k + 1, vector<int>(n + 1, 0));
    int m = 0; // Number of moves
    while (dp[m][n] < k) {
        m++;
        for (int x = 1; x <= n; x++) {
            dp[m][x] = 1 + dp[m - 1][x - 1] + dp[m - 1][x];
        }
    }
    return m;
}
 
/* Driver code*/
int main()
{
    cout << minTrials(2, 10);
    return 0;
}
 
// This code is contributed by Arihant Jain (arihantjain01)

Producción

4

Optimización a DP unidimensional

La solución anterior se puede optimizar para DP unidimensional de la siguiente manera:

C++

// C++ program to find minimum number of trials in worst
// case.
#include <bits/stdc++.h>
using namespace std;
 
int minTrials(int n, int k)
{
    // Initialize array of size (n+1) and m as moves.
    int dp[n + 1] = { 0 }, m;
    for (m = 0; dp[n] < k; m++) {
        for (int x = n; x > 0; x--) {
            dp[x] += 1 + dp[x - 1];
        }
    }
    return m;
}
 
/* Driver code*/
int main()
{
    cout << minTrials(2, 10);
    return 0;
}
 
// This code is contributed by Arihant Jain (arihantjain01)

Producción

4

Análisis de Complejidad:

  • Complejidad temporal: O(n * log k)
  • Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por kartik 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 *