ডিম ড্রপিং ধাঁধা

এটি একটি বিখ্যাত ধাঁধার সমস্যা৷ ধরুন এন ফ্লোর সহ একটি বিল্ডিং আছে, যদি আমাদের ডিম থাকে, তাহলে আমরা কীভাবে একটি ফ্লোর খুঁজে বের করার জন্য ন্যূনতম সংখ্যক ফোঁটা খুঁজে বের করতে পারি যেখান থেকে ডিম না ভেঙ্গে ফেলা নিরাপদ।

কিছু গুরুত্বপূর্ণ বিষয় মনে রাখতে হবে -

• যখন একটি প্রদত্ত তল থেকে একটি ডিম ভাঙ্গে না, তখন এটি নীচের তলায়ও ভাঙবে না৷
• প্রদত্ত মেঝে থেকে যদি একটি ডিম ভেঙ্গে যায়, তবে তা উপরের তলাগুলির জন্য ভেঙে যাবে৷
• ডিম ভেঙ্গে গেলে তা ফেলে দিতে হবে, অন্যথায় আমরা আবার ব্যবহার করতে পারি।

ইনপুট এবং আউটপুট

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