丢鸡蛋拼图的C程序-DP-11？
这是一个著名的难题问题。假设有一栋建筑物有n层，如果我们有m个鸡蛋，那么我们如何才能找到从地板上放下不伤鸡蛋的安全下落所需的最小跌落次数。
有一些重要的事情要记住-
当鸡蛋没有从给定的地板破损时，它也不会在任何较低的地板破损。
如果鸡蛋从给定的地板上破裂，那么它将在所有较高的地板上破裂。
当鸡蛋破裂时，必须将其丢弃，否则我们可以再次使用它。
输入 -鸡蛋数和最大下限。假设鸡蛋数为4，最大下蛋量为10。
输出 -最少试验次数4。
算法
eggTrialCount（鸡蛋，地板）
输入 -鸡蛋数量，最大下限。
输出 -获得最少的试验次数。
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<stdio.h>
#define MAX_VAL 9999
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]; //to store minimum trials for i-th egg
and jth floor
int res, i, j, k;
for (i = 1; i <= eggs; i++) { //one trial to check from first floor, and
no trial for 0th floor
minTrial[i][1] = 1;
minTrial[i][0] = 0;
}
for (j = 1; j <= floors; j++) //when egg is 1, we need 1 trials for
each floor
minTrial[1][j] = j;
for (i = 2; i <= eggs; i++){ //for 2 or more than 2 eggs
for (j = 2; j <= floors; j++) { //for second or more than second
floor
minTrial[i][j] = MAX_VAL;
for (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;
printf("Enter number of eggs: ");
scanf("%d", &egg);
printf("Enter max Floor: ");
scanf("%d", &maxFloor);
printf("Minimum number of trials: %d", eggTrialCount(egg, maxFloor));
}输出结果
Enter number of eggs: 4 Enter max Floor: 10 Minimum number of trials: 4