算法设计：如何解决2个鸡蛋和K层鸡蛋掉落难题？

本文概述

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

给定2个鸡蛋和k层，求最坏情况下需要的最小试验次数。这个问题是n个鸡蛋和k层的特定情况。

例子：

Input : 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 : k = 100
Output : 14

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

如果我们只有一个鸡蛋, 最坏情况的试验次数是多少？

答案是k。我们将在1层, 2层, 3层进行尝试, 在最坏的情况下, 鸡蛋会从顶层破裂。

如果我们有两个鸡蛋, 我们尝试的第一层是什么？

我们可以注意到, 如果答案是x, 那么我们尝试的第一层必须是层号x。因为在最坏的情况下, 如果鸡蛋破裂, 我们只剩下一个鸡蛋, 我们必须尝试从1到x-1的每一层。因此, 总试验次数变为1 +(x – 1)。

如果鸡蛋在第一次尝试中没有破裂, 我们将在第二层尝试什么？

我们尝试的下一层必须为x +(x – 1), 因为我们的最佳答案是x, 并且如果鸡蛋从层数x +(x-1)断开, 我们必须线性地从层数x + 1到x- 2。

我们可以概括一下吗？

如果第一个鸡蛋尚未破损, 则第i次试验必须从楼层编号x +(x – 1)+…+(x – i – 1)开始。

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

我们可以从上面观察到, 我们可以覆盖x +(x – 1)+(x – 2)…。 + 2 + 1层x试验。该表达式的值为x *(x + 1)/ 2。

给定k的最优x是多少？

从上面我们知道

x * (x + 1)/2 >= k
The optimal value of x can be written as, ⌈((-1 + √(1+8k))/2)⌉

C ++

// CPP program to find optimal number of trials
// for k floors and 2 eggs.
#include<bits/stdc++.h>
using namespace std;
  
int twoEggDrop( int k)
{
    return ceil ((-1.0 + sqrt (1 + 8*k))/2.0);
}
  
int main()
{
    int k = 100;
    cout << twoEggDrop(k);
    return 0; 
}

Java

// Java program to find 
// optimal number of trials
// for k floors and 2 eggs.
import java.io.*;
  
class GFG 
{
     static int twoEggDrop( int k)
     {
         return ( int )Math.ceil((- 1.0 +
                     Math.sqrt( 1 + 8 * k)) / 2.0 );
     }
      
     // Driver code
     public static void main (String[] args)
     {
         int k = 100 ;
         System.out.println(twoEggDrop(k));
     }
}
  
// This code is contributed
// by Mahadev.

Python3

# Python3 program to find optimal number 
# of trials for k floors and 2 eggs.
import math as mt 
  
def twoEggDrop(k):
     return mt.ceil(( - 1.0 + 
            mt.sqrt( 1 + 8 * k)) / 2 )
  
# Driver Code
k = 100
print (twoEggDrop(k))
  
# This code is contributed
# by Mohit Kumar

C#

// C# program to find optimal number 
// of trials for k floors and 2 eggs.
class GFG 
{
static int twoEggDrop( int k)
{
     return ( int )System.Math.Ceiling((-1.0 +
                 System.Math.Sqrt(1 + 8 * k)) / 2.0);
}
  
// Driver code
public static void Main ()
{
     int k = 100;
     System.Console.WriteLine(twoEggDrop(k));
}
}
  
// This code is contributed
// by mits

的PHP

<?php
// PHP program to find optimal number 
// of trials for k floors and 2 eggs.
  
function twoEggDrop( $k )
{
     return ceil ((-1.0 + 
            sqrt(1 + 8 * $k )) / 2.0);
}
  
// Driver Code
$k = 100;
echo twoEggDrop( $k );
  
// This code is contributed 
// by Akanksha Rai

输出：

14

时间复杂度：

O(1)

---