数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程语言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚
法律丢鸡蛋问题
这是一个著名的谜题。假设有一幢有 n 层楼高的建筑，我们有 m 个鸡蛋，我们如何才能找出可以安全地从某个楼层扔鸡蛋而不打碎它的最小扔数。
有一些重要的事项需要记住 -
- 如果鸡蛋从某一层楼扔下没打碎，那么从任何更低楼层扔下都不会打碎。
- 如果鸡蛋从某一层楼扔下打碎了，那么从所有更高楼层扔下都会打碎。
- 如果鸡蛋打碎了，它就必须扔掉，否则我们还可以再次使用它。
输入和输出
Input: The number of eggs and the maximum floor. Say the number of eggs are 4 and the maximum floor is 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]; //to store minimum trials for ith egg and jth floor
int res;
for (int 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 (int j = 1; j <= floors; j++) //when egg is 1, we need 1 trials for each floor
minTrial[1][j] = j;
for (int i = 2; i <= eggs; i++) { //for 2 or more than 2 eggs
for (int j = 2; j <= floors; j++) { //for second or more than second floor
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
更新于： 16-Jun-2020
545 次浏览
广告