鸡蛋丢拼图

这是一个著名的难题问题。假设有一幢n层的建筑物，如果我们有m个鸡蛋，那么我们如何才能找到从地板上放下不伤鸡蛋的安全下落所需的最小滴数。

有一些重要的事情要记住-

• 当鸡蛋没有从给定的地板破损时，它也不会在任何较低的地板破损。

• 如果鸡蛋从给定的地板上破裂，那么它将在所有较高的地板上破裂。

• 当鸡蛋破裂时，必须将其丢弃，否则，我们可以再次使用它。

输入输出

Input:
鸡蛋的数量和最大底数。 假设鸡蛋数为4，最大下蛋量为10。
Output:
Enter number of eggs: 4
Enter max Floor: 10
Minimum number of trials: 4

算法

eggTrialCount(eggs, floors)

输入：鸡蛋数量，最大下限。

输出-获得最少的试用次数。

Begin
   define matrix of size [eggs+1, floors+1]
   for i:= 1 to eggs, do
      minTrial[i, 1] := 1
      minTrial[i, 0] := 0
   done

   for j := 1 to floors, do
      minTrial[1, j] := j
   done

   for i := 2 to eggs, do
      for j := 2 to floors, do
         minTrial[i, j] := ∞
         for k := 1 to j, do
            res := 1 + max of minTrial[i-1, k-1] and minTrial[i, j-k]
            if res < minTrial[i, j], then
               minTrial[i,j] := res
         done
      done
   done

   return minTrial[eggs, floors]
End

示例

#include<iostream>
using namespace std;

int max(int a, int b) {
   return (a > b)? a: b;
}

int eggTrialCount(int eggs, int floors) {    //minimum trials for worst case
   int minTrial[eggs+1][floors+1];    //为第i个鸡蛋和第j层存储最少的试验
   int res;

   for (int i = 1; i <= eggs; i++) {    //一楼一试，0楼不试
      minTrial[i][1] = 1;
      minTrial[i][0] = 0;
   }

   for (int j = 1; j <= floors; j++)    //当鸡蛋是1的时候，我们每层需要1次试验。
      minTrial[1][j] = j;

   for (int i = 2; i <= eggs; i++) {    //2个或2个以上的鸡蛋
      for (int j = 2; j <= floors; j++) {    //第二层或以上
         minTrial[i][j] = INT_MAX;
         for (int k = 1; k <= j; k++) {
            res = 1 + max(minTrial[i-1][k-1], minTrial[i][j-k]);
            if (res < minTrial[i][j])
               minTrial[i][j] = res;
         }
      }
   }

   return minTrial[eggs][floors];    //number of trials for asked egg and floor
}

int main () {
   int egg, maxFloor;
   cout << "Enter number of eggs: "; cin >> egg;
   cout << "Enter max Floor: "; cin >> maxFloor;
   cout << "Minimum number of trials: " << eggTrialCount(egg, maxFloor);
}

输出结果

Enter number of eggs: 4
Enter max Floor: 10
Minimum number of trials: 4