首页 > 后端开发 > C++ > C程序的蛋掉落谜题 - DP-11

C程序的蛋掉落谜题 - DP-11

王林
发布: 2023-08-30 11:53:03
转载
572 人浏览过

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
登录后复制

以上是C程序的蛋掉落谜题 - DP-11的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板