계란 떨어뜨리기 퍼즐

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