算法题：鸡蛋掉落难题（二项式系数和二叉搜索解决方案）

2021年3月24日14:21:14 发表评论 682 次浏览

本文概述

给定n个鸡蛋和k个地板, 找到在最坏情况下找到所有地板都安全的地板所需的最少试验次数。如果从地板上扔鸡蛋不会破坏鸡蛋, 则地板是安全的。请参阅n个鸡蛋和k层地板。完整的陈述

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

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

我们已经讨论了这个问题2个鸡蛋和k层。我们还讨论了动态编程解决方案寻找解决方案。动态编程解决方案基于问题的以下递归性质。让我们从另一个角度来看待讨论的递归公式。

我们可以用x次试验覆盖几层？

当我们放一个鸡蛋时, 会出现两种情况。

  1. 如果鸡蛋破裂, 那么我们将进行x-1次试验和n-1个鸡蛋。
  2. 如果鸡蛋没有破裂, 那么我们将进行x-1次试验和n个鸡蛋
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 sum = 0, term = 1; 
     for ( int i = 1; i <= n; ++i) { 
         term *= x - i + 1; 
         term /= i; 
         sum += term; 
     } 
     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) 
             low = mid + 1; 
         else
             high = mid; 
     } 
  
     return low; 
} 
  
/* Driver program to test above function*/
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 program to test above function*/
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 = (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)
?>

输出如下：

4

时间复杂度：O(n Log k)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: