এটি একটি বিখ্যাত ধাঁধা সমস্যা। ধরুন এন ফ্লোর সহ একটি বিল্ডিং আছে, যদি আমাদের ডিম থাকে, তাহলে আমরা কীভাবে একটি ফ্লোর খুঁজে বের করার জন্য ন্যূনতম সংখ্যক ফোঁটা খুঁজে বের করতে পারি যেখান থেকে ডিম না ভেঙ্গে ফেলা নিরাপদ।
কিছু গুরুত্বপূর্ণ বিষয় মনে রাখতে হবে -
- যখন একটি প্রদত্ত তল থেকে একটি ডিম ভাঙ্গে না, তখন এটি নীচের তলায়ও ভাঙবে না৷
- প্রদত্ত মেঝে থেকে যদি একটি ডিম ভেঙ্গে যায়, তবে তা উপরের তলাগুলির জন্য ভেঙে যাবে৷
- ডিম ভেঙ্গে গেলে তা ফেলে দিতে হবে, অন্যথায় আমরা আবার ব্যবহার করতে পারি।
ইনপুট - ডিমের সংখ্যা এবং সর্বোচ্চ মেঝে। বলুন ডিমের সংখ্যা 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
