पैसेज सैपर। भाग २

विषय के प्रकाशन के बाद, कई रोचक, उपयोगी और सुखद टिप्पणियां प्राप्त हुईं। इसके लिए धन्यवाद, मैंने इस मुद्दे का अध्ययन करना जारी रखा, गणना एल्गोरिथ्म को फिर से तैयार किया और कुछ दिलचस्प तथ्य प्राप्त किए (जिसमें विभिन्न खानों के साथ जीतने की संभावना भी शामिल है), जो मुझे लगता है, आपकी रुचि होगी।

संपूर्ण खोज के बारे में सलाह ने मुझे सोचने पर मजबूर कर दिया, क्योंकि पहले तो मैंने इसे गंभीरता से नहीं लिया, यह देखते हुए कि खोज में बहुत लंबा समय लगेगा। यह वास्तव में मामला होगा यदि खदानें पूरे क्षेत्र में बिखरी हुई थीं। लेकिन IXBT से सैपर डाउनलोड करने के बाद , मैंने महसूस किया कि यह बिल्कुल भी आवश्यक नहीं था। यह केवल उन कोशिकाओं पर विचार करने के लिए समझ में आता है जो सीधे खुले नंबरों से सटे हैं। ये संख्या अन्य कोशिकाओं में खानों की संभावना को प्रभावित नहीं करती है।

वैसे, डाउनलोड किए गए सैपर का अध्ययन करने पर, मैंने पाया कि मैदान पर शेष खानों की गणना करते समय यह पूरी तरह से ध्यान में नहीं रखता है। पहली नज़र में, यह महत्वपूर्ण नहीं है, क्योंकि, उदाहरण के लिए, एक एकल "4" के आसपास संभावना हमेशा 50/50 होगी। लेकिन ऐसे समय होते हैं जब इस कारक की अनदेखी करने से बहुत बुरे परिणाम होते हैं, उदाहरण के लिए:




खानों की संख्या को छोड़कर, डेटा बिल्कुल समान हैं, लेकिन परिणाम में अंतर बहुत महत्वपूर्ण है।
मुझे लगता है कि आप खुद अनुमान लगाते हैं कि ऐसा क्यों हो रहा है। खानों को व्यवस्थित करने के 2 तरीके हैं: इकाइयों के बीच एक खदान (पास में कोई अधिक नहीं है) या दो खदानें हैं, प्रत्येक इकाई के लिए एक। यदि पूरे क्षेत्र में 2 खदानें हैं, तो सबसे अधिक संभावना इकाइयों के बीच स्थित होगी, लेकिन दूसरा क्षेत्र के लगभग किसी भी सेल में हो सकता है, क्योंकि दोनों पास होंगे। इसके विपरीत, यदि बहुत अधिक खदानें हैं, तो संभावना यह है कि 6 कोशिकाओं के क्षेत्र में (इकाइयों के पास) एक भी खदान छोटी नहीं होगी।

अब IXBT से गणना:



किसी भी खदान की संख्या के साथ, संभावनाएं समान हैं। उनके आंकड़ों के आधार पर, मैं इस नतीजे पर पहुंचा कि विकल्पों की गणना करते समय, उनका तात्पर्य है कि वे सभी समान रूप से संभावित हैं, लेकिन, जैसा कि उदाहरण से देखा जा सकता है, यह पूरी तरह से मामला नहीं है।
प्रत्येक मामले की संभावना की गणना करने से मुझे थोड़ी परेशानी हुई। यदि गणना की प्रक्रिया में वैरिएंट की शर्तों को पूरा किया गया था, तो इस मामले की संभावना की गणना करना आवश्यक था, और प्राप्त कोशिकाओं को खानों के साथ सभी कोशिकाओं को जोड़ना (केवल वर्तमान संस्करण के लिए प्राप्त काल्पनिक खानों)। यद्यपि गणना स्वयं कठिन नहीं है, केवल कॉम्बिनेटरिक्स की मूल बातें उपयोग की जाती हैं।

इस अच्छे नोट को समाप्त करना अच्छा होगा, क्योंकि सब कुछ बहुत अच्छी तरह से हो गया था, और प्राप्त संभावनाओं को सैद्धांतिक गणना और कार्यक्रम के पहले संस्करण द्वारा पूरी तरह से पुष्टि की गई थी। लेकिन यह तब है जब खुले नंबरों की सीमा बनाने वाली कोशिकाओं की संख्या बहुत बड़ी नहीं थी। 23 से अधिक की संख्या के साथ, गणना में एक सेकंड से अधिक समय लगा, जो बहुत सुखद नहीं था। इसलिए, एक सिद्ध पद्धति को अपनाया गया था (मोंटे कार्लो, जैसा कि पिछले विषय में उल्लेख किया गया है)। उसी पड़ोसी कोशिकाओं में एक यादृच्छिक सेट उत्पन्न होता है, जिसने पुनरावृत्तियों की संख्या 10 हजार से बढ़ाकर दस लाख करने की अनुमति दी। दुर्भाग्य से, कठिन मामलों में, एक त्रुटि अभी भी जारी की जाती है, लेकिन ऐसा बहुत कम बार होता है। लेकिन सामान्य तौर पर यह सही और जल्दी से काम करता है। आप इसे यहाँ डाउनलोड कर सकते हैं ।

मुख्य लक्ष्य।

जब कार्यक्रम तैयार हो गया, तो खानों की संख्या से जीत की आवृत्ति की जांच करना दिलचस्प हो गया। जटिलता और समय के आधार पर खेल एक हजार से एक लाख तक आयोजित किए गए थे। आरेख केवल 1 से 32 तक की संख्या दिखाता है, इसलिए संभावना बहुत कम हो जाती है। शेष नीचे है।



35: 17 ( 10 ) 0.17%
40: 10 ( 100 ) 0.01%
45: 3 ( 100 ) 0.003%
50: 6 ( ) 0.0006%
60: 2 ( ) 0.0002%
70: 0 ( ) ?
75: 6 ( ) 0.0006%
76: 32 ( ) 0.0032%
77: 183 ( ) 0.0183%
78: 1552 ( ) 0.1552%
79: 25350 ( ) 2.535%

जैसा कि आप देख सकते हैं, फ़ंक्शन काफी चिकना है। मैंने इसके लिए एक अनुभवजन्य सूत्र खोजने की कोशिश की, लेकिन अभी तक कोई फायदा नहीं हुआ, इसलिए यह बहुत अच्छा होगा यदि आप मुझे बताएं।

विशेष रूप से M_org के लिए , जिन्होंने मुझसे पूछा कि क्या मैं 64 खानों के साथ गुजर सकता हूं, मैंने 10 मिलियन बार चलाई और कभी नहीं जीता। लेकिन अब मैं सुरक्षित रूप से जवाब दे सकता हूं कि यह 79 वें के साथ भी कमजोर नहीं है :)