दैनिक कोडिंग समस्या 24  एक और समस्या के समाधान के साथ आपका फिर से स्वागत है! आज, हम छतों से गिरने वाले अंडों के साथ इस वास्तव में अच्छी समस्या से निपट रहे हैं, जिसमें दो संभावित समाधान शामिल होंगे: एक बहुत ही सरल और एक अधिक चतुर समाधान। यह आखिरी हमें एक काफी प्रसिद्ध एल्गोरिदम के बारे में बात करने का मौका भी देगा।  हमेशा की तरह, आज की समस्या अद्भुत समाचार पत्र द्वारा प्रदान की गई है  , जिसे आप अपनी दैनिक कोडिंग चुनौती प्राप्त करने के लिए निःशुल्क सदस्यता ले सकते हैं। इसे जांचें, और अपनी समस्याओं को भी हल करने का प्रयास करें!   दैनिक कोडिंग समस्या  बहुत हो गई बातें तो; आइए समस्या देखें!  समस्या  यह समस्या गोल्डमैन सैक्स से एक नौकरी साक्षात्कार में पूछी गई थी। आइए समस्या देखें.      समान अंडे और   मंजिलों वाली इमारत तक पहुंच दी जाती है। आपका काम सबसे निचली मंजिल ढूंढना है जिस मंजिल से गिराए जाने पर अंडा टूट जाएगा। एक बार अंडा टूट जाए तो उसे दोबारा गिराया नहीं जा सकता। यदि एक अंडा   मंजिल से गिराने पर टूट जाता है, तो आप मान सकते हैं कि   से अधिक किसी भी मंजिल से गिराने पर भी यह टूट जाएगा। आपको N k xth x   एक एल्गोरिदम लिखें जो इस मंजिल की पहचान करने के लिए, सबसे खराब स्थिति में, न्यूनतम संख्या में ट्रायल ड्रॉप्स का पता लगाएगा।      और   , तो हमें पहली मंजिल से शुरू करके पांचवीं मंजिल तक पहुंचने तक हर मंजिल पर अंडे गिराने की कोशिश करनी होगी, इसलिए हमारा समाधान   होगा। उदाहरण के लिए, यदि N = 1 k = 5 5  तो, हमें एक इमारत की विभिन्न मंजिलों से फेंकने के लिए कुछ अंडे दिए जाते हैं। हमें दुख है कि एक निश्चित मंजिल (जिसे हम   कहेंगे) से फेंके गए अंडे जमीन पर गिरने पर नहीं टूटते। targetFloor  उस मंजिल से लेकर उसके नीचे की हर मंजिल तक, खिड़की से बाहर फेंकने पर अंडे नहीं टूटेंगे। हमें   खोजने के लिए एक कुशल तरीका खोजने के लिए कहा गया है। targetFloor  जैसा कि अनुमान लगाया गया था, हम इसे हल करने के लिए दो तरीके देखेंगे: एक बहुत ही सरल तरीका, जो समाधान को बहुत मजबूर कर देगा, लेकिन यह कुशल नहीं होगा। दूसरा अधिक कुशल होगा और कम से कम चरणों को तोड़कर समस्या को हल करने का प्रयास करेगा।  यह हमें वास्तव में प्रसिद्ध और महत्वपूर्ण एल्गोरिदम के बारे में बात करने का मौका भी देगा; उनमें से एक जिसे करने के लिए आपको जानना आवश्यक है... मूलतः कुछ भी!  पर्यावरण की स्थापना  आरंभ करने के लिए, हमें थोड़ा सा वातावरण स्थापित करने की आवश्यकता है, अर्थात् भवन और   । इमारत बनाने के लिए, हम बस एक सरणी बनाते हैं जिसमें भूतल से लेकर अंतिम मंजिल तक फर्शों की संख्या शामिल होती है। फिर, हम एक यादृच्छिक संख्या उत्पन्न करते हैं जो हमारा   होगा। targetFloor targetFloor  हम इस समस्या को एक बार फिर गो में लिखेंगे: पढ़ने योग्य होने के लिए पर्याप्त सरल, लेकिन आंतरिक यांत्रिकी को समझने के लिए पर्याप्त जटिल।   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  हम पहले सरणी बनाते हैं जो हमारी इमारत के रूप में काम करेगी: हम इसे वह आकार दे सकते हैं जो हम चाहते हैं, आकार जितना बड़ा होगा, इमारत उतनी ही ऊंची होगी। उसके बाद, हम गो में निर्मित   मॉड्यूल का उपयोग करके   का एक उदाहरण बनाते हैं। math/rand targetFlor  मूल रूप से, हम वर्तमान समय को स्रोत के रूप में उपयोग करके 0 और इमारत की ऊंचाई (... सरणी की लंबाई: डी) के बीच एक नया यादृच्छिक पूर्णांक बनाते हैं।  क्रूर बल समाधान  निःसंदेह, सबसे सरल उपाय यह होगा कि प्रत्येक मंजिल पर प्रत्येक अंडे को बाहर फेंक दिया जाए, ताकि यह देखा जा सके कि अंडे किस मंजिल पर टूटना शुरू करते हैं। चूँकि हमारे पास उस जानकारी वाला एक वेरिएबल है, कोई भी समस्या को हल करने के लिए बस एक लूप कर सकता है:   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  हालाँकि यह सबसे सरल समाधान है, दुर्भाग्य से यह अत्यधिक अक्षम है। कल्पना करें कि अगर सही मंजिल शीर्ष पर है: समस्या को हल करने के लिए 100,000 अंडे तोड़ने होंगे: यह एक बहुत बड़ा आमलेट होगा लेकिन काफी बेकार होगा!  सामान्यतया, इस समाधान की समय जटिलता O(n) है क्योंकि समाधान की जटिलता इनपुट समस्या की जटिलता तक रैखिक रूप से बढ़ती है। हालाँकि यह सबसे कारगर समाधान नहीं है जिसके बारे में हम सोच सकते हैं।  एक कुशल समाधान  आइए फिर एक कारगर समाधान के बारे में सोचें। प्रत्येक मंजिल पर एक-एक अंडा तोड़ने की बजाय, हम एक अनुमान लगा सकते हैं और उस अनुमान के परिणाम के आधार पर, अगले अनुमान को समायोजित कर सकते हैं।  यहां एक उदाहरण दिया गया है: मान लीजिए कि हमारे पास 10 मंजिलों वाली एक इमारत है, और   7वीं मंजिल है (निश्चित रूप से हम यह नहीं जानते हैं)। हम निम्नलिखित अनुमान लगा सकते हैं:  targetFloor  मूल रूप से, हम अनुमान लगाते हैं कि   इमारत की मध्य मंजिल है। हम वहां से अंडा फेंकते हैं, और संभावित परिणाम दो हैं: targetFloor  अंडा टूट जाता है, इसका मतलब है कि हम बहुत ऊपर हैं। हम इसमें शामिल, इससे ऊंची मंजिल को त्याग सकते हैं और अपने अनुमानों के साथ आगे बढ़ सकते हैं।  अंडा नहीं टूटता, इसका मतलब है कि हम बहुत नीचे हैं या सही मंजिल पर हैं। हम इससे नीचे की प्रत्येक मंजिल को शामिल करते हुए त्याग देते हैं, और  इसे देखते हुए, अब हम मध्य मंजिल या "शेष" इमारत के बारे में एक और शिक्षित अनुमान लगाते हैं, और ऊपर देखी गई समान रणनीति लागू करते हैं। हम इस दृष्टिकोण के साथ तब तक आगे बढ़ सकते हैं जब तक हमारे पास एक मंजिल न रह जाए।  यदि आप इस दृष्टिकोण को पहचानते हैं, तो आप बिल्कुल सही हैं: यह केवल "वास्तविक दुनिया" समस्या पर लागू एक   है। बाइनरी सर्च एक सरल और साफ   एल्गोरिथ्म है, जिसका अर्थ है कि प्रत्येक चरण पर, समस्या का आकार तब तक आधा हो जाता है जब तक हम समाधान नहीं ढूंढ लेते। द्विआधारी खोज -सुथरा विभाजन और जीत  इसका मतलब यह है कि यह एल्गोरिथम, पिछले वाले की तुलना में, बहुत तेज़ है। आइए कोड देखें!   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  आइए गहराई से देखें. बाइनरी खोज फ़ंक्शन 4 तर्क लेता है:    , पूर्णांकों की एक सरणी, जो वह इमारत है जिस पर हम लूपिंग कर रहे हैं; overArray    , इमारत का निचला सूचकांक; bottom    , इमारत का शीर्ष मंजिल सूचकांक; top    , वेरिएबल   यह जांचने के लिए रखता है कि क्या हम इसे बिल्डिंग में पा सकते हैं। breakFloor targetFloor  उसके बाद, हम इमारत पर लूप करते हैं जबकि     से नीचे होता है: बाइनरी खोज में, जब दो स्थितीय तर्क आपस में जुड़ते हैं और स्वैप करते हैं, तो इसका मतलब है कि खोजा गया तत्व नहीं मिला। bottom top  इसलिए, यदि एल्गोरिथ्म इस स्थिति में समाप्त होता है, तो लूप समाप्त हो जाता है और हम   लौटते हैं, जिसका अर्थ है कि जिस तत्व को हम ढूंढ रहे हैं वह सरणी में मौजूद नहीं था। यदि हम अभी भी तत्व की खोज कर रहे हैं, तो हम ऊपर की छवि में जो दिखाया गया है उसे लागू करते हैं। -1  हम   तत्व की गणना   और   के बीच के फर्श के रूप में करते हैं और हम जांचते हैं कि   । यदि ऐसा है, तो हम परिणाम के रूप में   लौटाते हैं। middlePoint bottom top middlePoint == breakFloor middlePoint  यदि ऐसा नहीं है, तो हम   या   तदनुसार समायोजित करते हैं: यदि     से बड़ा है, तो इसका मतलब है कि हम इमारत पर बहुत ऊंचे हैं इसलिए हम   संभावित मंजिल को   पर सेट करके अपनी भविष्यवाणी को कम करते हैं। bottom top middlePoint breakFloor top middlePoint — 1  यदि     से छोटा है, तो हम   के रूप में सेटिंग करके अपने   समायोजित करते हैं। middlePoint breakFloor middlePoint+1 bottom  अब सब कुछ जांचने के लिए,   फ़ंक्शन में, हम पहले की तरह पर्यावरण उत्पन्न करते हैं, और   नामक एक नया वेरिएबल बनाते हैं जो हमारे परिणाम को रखेगा। main bsFloor  यह पुष्टि करने के लिए कि हमारा एल्गोरिदम हमें सही परिणाम पर लाया है, हम   और   दोनों का प्रिंट आउट लेते हैं, जो पहले यादृच्छिक रूप से उत्पन्न हुआ था। bsFloor targetFloor  समय की जटिलता  जैसा कि हमने पहले अनुमान लगाया था, यह एल्गोरिदम रैखिक एल्गोरिदम से कहीं अधिक तेज़ है। चूँकि हम प्रत्येक चरण में इमारत को आधा करते हैं, हम log₂(n) में सही मंजिल पा सकते हैं जहाँ n   के बराबर है। len(building)  इसका मतलब है कि इस एल्गोरिदम की समय जटिलता   है। आपको रैखिक समाधान और इस अंतिम समाधान के बीच कुछ तुलना देने के लिए, यदि इमारत में 100 मंजिलें हैं, तो रैखिक एल्गोरिदम सबसे खराब स्थिति में 100 पुनरावृत्तियों को लेता है, जबकि बाइनरी खोज एल्गोरिदम लॉग₂100 = 6.64 लेता है, इसलिए 7 पुनरावृत्तियों को लेता है। O(log(n))  इसके अलावा, यह अंतिम खोज रैखिक खोज की तुलना में अधिक कुशल है क्योंकि जितनी अधिक इमारत बढ़ती है, बाइनरी खोज उतनी ही अधिक कुशल होती है। 1.000.000.000 मंजिलों वाली एक इमारत के लिए, रैखिक एक 1.000.000.000 कदम उठाता है, जबकि बाइनरी एक लॉग₂1.000.000.000 = 29.9 लेता है, इसलिए 30 कदम। बहुत बड़ा सुधार!   निष्कर्ष  यह बात है! मुझे आशा है कि आपको लेख का उतना ही आनंद आया होगा जितना मुझे चुनौती को हल करने में आया था! यदि हां, तो कृपया एक या दो तालियां बजाएं, यह एक बड़ा समर्थन होगा! यदि आपको इस प्रकार के लेख पसंद हैं और आप और अधिक देखना चाहते हैं, तो पेज का अनुसरण करें क्योंकि मैं जब भी संभव हो इस प्रकार की सामग्री जारी करता हूँ।  अंत में, यदि आपको यह लेख रोचक या उपयोगी लगा और आप कॉफ़ी की पेशकश करके अपना योगदान देना चाहते हैं, तो बेझिझक मेरी ओर से ऐसा करें  पृष्ठ!   को-फाई  और, हमेशा की तरह, पढ़ने के लिए धन्यवाद!   निकॉला    भी प्रकाशित किया गया यहाँ

Read My Stories

यह ऑडियो कहानी की मूल भाषा में निर्मित है!

जब आपको छत से अंडे फेंकने हों: दैनिक कोडिंग समस्या

About Author

टिप्पणियाँ

लेबल

इस लेख में चित्रित किया गया था

Related Stories

फ़ोरम से फ़ीड तक: सोशल मीडिया एल्गोरिदम डिजिटल इंटरैक्शन को कैसे आकार देते हैं

He/Him/Master of Discovery

क्लाउड सॉनेट 3.5 सिस्टम प्रॉम्प्ट लीक: एक फोरेंसिक विश्लेषण

जलयात्रा: डेटा झीलों के साथ उत्पादन-ग्रेड आरएजी अनुप्रयोगों का विकास

फ़ोरम से फ़ीड तक: सोशल मीडिया एल्गोरिदम डिजिटल इंटरैक्शन को कैसे आकार देते हैं

He/Him/Master of Discovery

क्लाउड सॉनेट 3.5 सिस्टम प्रॉम्प्ट लीक: एक फोरेंसिक विश्लेषण

जलयात्रा: डेटा झीलों के साथ उत्पादन-ग्रेड आरएजी अनुप्रयोगों का विकास

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps