이것은 유명한 퍼즐 문제입니다. 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