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

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#
的PHP

【算法题（鸡蛋掉落难题（二项式系数和二叉搜索解决方案））】给定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次试验覆盖几层？
当我们放一个鸡蛋时, 会出现两种情况。

如果鸡蛋破裂, 那么我们将进行x-1次试验和n-1个鸡蛋。
如果鸡蛋没有破裂, 那么我们将进行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 > = 1Base cases : We can't cover any floor with 0 trials or 0 eggs maxFloors(0, n) = 0 maxFloors(x, 0) = 0Since 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# 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) ?>

输出如下：