এটি একটি বিখ্যাত পাজল সমস্যা। ধরুন একটি বিল্ডিং আছে n তলার, যদি আমাদের m টি ডিম থাকে, তবে আমরা কিভাবে ন্যূনতম ড্রপ দিয়ে সেই তলা খুঁজে বের করব যেখান থেকে ডিম ড্রপ করলে সেটি ভাঙবে না।
কিছু গুরুত্বপূর্ণ পয়েন্ট মনে রাখতে হবে −
- যদি একটি ডিম কোনো তলা থেকে না ভাঙে, তবে সেটি যেকোনো নিচের তলা থেকেও ভাঙবে না।
- যদি একটি ডিম কোনো তলা থেকে ভাঙে, তবে সেটি সব উপরের তলা থেকেও ভাঙবে।
- যদি ডিম ভাঙে, তবে সেটি ফেলে দিতে হবে, অন্যথায় আবার ব্যবহার করা যাবে।
ইনপুট এবং আউটপুট
ইনপুট: ডিমের সংখ্যা এবং সর্বোচ্চ তলা। মান লইয়ে নিই ডিম ৪টি এবং সর্বোচ্চ তলা ১০। আউটপুট: Enter number of eggs: 4 Enter max Floor: 10 Minimum number of trials: 4
এলগরিদম
eggTrialCount(eggs, floors)
ইনপুট: ডিমের সংখ্যা, সর্বোচ্চ তলা।
আউটপুট: ন্যূনতম ট্রায়ালের সংখ্যা পান।
শুরু
[eggs+1, floors+1] আকারের একটি ম্যাট্রিক্স সংজ্ঞায়িত করুন
i := 1 থেকে eggs পর্যন্ত, করুন
minTrial[i, 1] := 1
minTrial[i, 0] := 0
শেষ লুপ
j := 1 থেকে floors পর্যন্ত, করুন
minTrial[1, j] := j
শেষ লুপ
i := 2 থেকে eggs পর্যন্ত, করুন
j := 2 থেকে floors পর্যন্ত, করুন
minTrial[i, j] := ∞
k := 1 থেকে j পর্যন্ত, করুন
res := 1 + max(minTrial[i-1, k-1] এবং minTrial[i, j-k]) এর
যদি res < minTrial[i, j], তবে
minTrial[i, j] := res
শেষ লুপ
শেষ লুপ
শেষ লুপ
return minTrial[eggs, floors]
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
using namespace std;
int max(int a, int b) {
return (a > b) ? a : b;
}
int eggTrialCount(int eggs, int floors) {
// ওয়ার্স্ট কেসের জন্য ন্যূনতম ট্রায়াল
int minTrial[eggs+1][floors+1]; // i-তম ডিম এবং j-তম তলার জন্য ন্যূনতম ট্রায়াল স্টোর করুন
int res;
for (int i = 1; i <= eggs; i++) {
// প্রথম তলা থেকে চেক করতে ১ ট্রায়াল, এবং ০ তলার জন্য কোনো ট্রায়াল নেই
minTrial[i][1] = 1;
minTrial[i][0] = 0;
}
for (int j = 1; j <= floors; j++) // যখন ডিম ১টি, প্রতিটি তলার জন্য ১ ট্রায়াল লাগে
minTrial[1][j] = j;
for (int i = 2; i <= eggs; i++) {
// ২ বা ২-এর বেশি ডিমের জন্য
for (int j = 2; j <= floors; j++) {
// ২য় বা ২য়ের উপরের তলার জন্য
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]; // চাওয়া ডিম এবং তলার জন্য ট্রায়ালের সংখ্যা
}
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
