C 프로그램 계란 떨어뜨리기 퍼즐 - DP-11

이것은 유명한 퍼즐입니다. n층 건물이 있다고 가정하고, m개의 계란이 있다면, 계란을 깨지 않고 안전하게 떨어뜨릴 수 있는 바닥에 필요한 최소 방울 수를 어떻게 찾을 수 있을까요?

기억해야 할 몇 가지 중요한 사항이 있습니다 -

• 계란이 특정 층에서 깨지지 않으면 어떤 낮은 층에서도 깨지지 않습니다.
• 특정 층에서 달걀이 깨지면 그 위의 모든 층에서도 달걀이 깨집니다.
• 계란이 깨지면 폐기해야 하며, 아니면 다시 사용할 수 있습니다.

Enter - 계란의 수와 최대 층수. 계란의 개수는 4개이고 최대 층수는 10개라고 가정합니다.

Output- 최소 시도 횟수 4.

Algorithm

eggTrialCount(계란, 바닥)

Input− 계란 수, 최대 층.

출력 − 최소 계란 수 테스트를 받으세요.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!