二蛋问题:
给你2个鸡蛋。
您可以进入一栋 100 层高的建筑。
鸡蛋可能非常坚硬或非常脆弱,这意味着如果从一楼掉下它可能会破裂,或者如果从 100 楼掉下来甚至可能不会破裂。两个鸡蛋是相同的。
你需要弄清楚一座 100 层高的建筑物的最高楼层,一个鸡蛋可以掉下来而不会破裂。
现在的问题是你需要做多少滴。在此过程中,您可以打碎 2 个鸡蛋。
我知道动态编程解决这个问题的方法。我想跟踪解决方案以及最少的尝试次数。即我必须尝试获得最少尝试次数的楼层。
# include <stdio.h>
# include <limits.h>
// A utility function to get maximum of two integers
int max(int a, int b) { return (a > b)? a: b; }
/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
/* A 2D table where entery eggFloor[i][j] will represent minimum
number of trials needed for i eggs and j floors. */
int eggFloor[n+1][k+1];
int res;
int i, j, x;
// We need one trial for one floor and0 trials for 0 floors
for (i = 1; i <= n; i++)
{
eggFloor[i][1] = 1;
eggFloor[i][0] = 0;
}
// We always need j trials for one egg and j floors.
for (j = 1; j <= k; j++)
eggFloor[1][j] = j;
// Fill rest of the entries in table using optimal substructure
// property
for (i = 2; i <= n; i++)
{
for (j = 2; j <= k; j++)
{
eggFloor[i][j] = INT_MAX;
for (x = 1; x <= j; x++)
{
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
if (res < eggFloor[i][j])
eggFloor[i][j] = res;
}
}
}
// eggFloor[n][k] holds the result
return eggFloor[n][k];
}
/* Driver program to test to pront printDups*/
int main()
{
int n = 2, k = 36;
printf ("\nMinimum number of trials in worst case with %d eggs and "
"%d floors is %d \n", n, k, eggDrop(n, k));
return 0;
}