यह एक प्रसिद्ध पहेली समस्या है। मान लें कि n मंजिलों वाली एक इमारत है, अगर हमारे पास m अंडे हैं, तो हम कैसे पता लगा सकते हैं कि उस मंजिल को खोजने के लिए न्यूनतम बूंदों की संख्या क्या है जिससे अंडे को बिना तोड़े गिराना सुरक्षित है।
याद रखने के लिए कुछ महत्वपूर्ण बिंदु -
- जब एक अंडा दिए गए मंजिल से नहीं टूटता है, तो यह किसी भी निचली मंजिल से भी नहीं टूटेगा।
- यदि एक अंडा दिए गए मंजिल से टूटता है, तो यह सभी ऊपरी मंजिलों के लिए टूटेगा।
- जब एक अंडा टूटता है, तो इसे त्याग दिया जाना चाहिए, अन्यथा हम इसे फिर से उपयोग कर सकते हैं।
इनपुट और आउटपुट
इनपुट: अंडों की संख्या और अधिकतम मंजिल। मान लें अंडों की संख्या 4 है और अधिकतम मंजिल 10 है। आउटपुट: अंडों की संख्या दर्ज करें: 4 अधिकतम मंजिल दर्ज करें: 10 न्यूनतम परीक्षणों की संख्या: 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 + minTrial[i-1, k-1] और minTrial[i, j-k] का अधिकतम यदि res < minTrial[i, j], तो minTrial[i,j] := res किया किया किया minTrial[eggs, floors] वापस करें अंत
उदाहरण
#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]; //ith अंडे और jवीं मंजिल के लिए न्यूनतम परीक्षण संग्रहीत करने के लिए int res; for (int i = 1; i <= eggs; i++) { //पहली मंजिल से जांच के लिए एक परीक्षण, और 0वीं मंजिल के लिए कोई परीक्षण नहीं minTrial[i][1] = 1; minTrial[i][0] = 0; } for (int j = 1; j <= floors; j++) //जब अंडा 1 है, तो हमें प्रत्येक मंजिल के लिए 1 परीक्षण चाहिए minTrial[1][j] = j; for (int i = 2; i <= eggs; i++) { //2 या 2 से अधिक अंडों के लिए 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
