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

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

## 本文概述

``````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}首先, 在继续解决方案之前。

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) = &Sum;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``