資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究求解雞蛋掉落難題的 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
更新於： 2019 年 7 月 30 日
265 次瀏覽
廣告