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