🗡️ 🐵 🅿️ खेल "समुद्री लड़ाई": जहाजों की व्यवस्था ⛲️ 🤳🏽 💞

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

मैं ध्यान देता हूं कि नक्षत्र की पीढ़ी न केवल एक कृत्रिम प्रतिद्वंद्वी के लिए, बल्कि एक व्यक्ति के लिए भी प्रासंगिक है: अपेक्षाकृत समान रणनीतिक स्थिति बनाने के लिए, एक जीवित खिलाड़ी के जहाजों को छद्म-यादृच्छिक रूप से व्यवस्थित किया जाना चाहिए। इस अनुच्छेद में, हम एक एल्गोरिथ्म पर विचार करते हैं जो एक वैध व्यवस्था खोजने की गारंटी है (इस परिमित समय पर खर्च करके, जिसका एक ऊपरी अनुमान प्राप्त किया जा सकता है) यदि यह मौजूद है (तदनुसार, यह प्रस्तावित स्थितियों में जहाजों की व्यवस्था करने की मौलिक संभावना की विशेषता हो सकती है)।

विकल्पों की संख्या

यदि हम एक गैर-शास्त्रीय स्क्वाड्रन पर विचार करते हैं, तो जहाज प्लेसमेंट विकल्पों की कुल संख्या की गणना सूत्र द्वारा की जाती है:

यह सूत्र सभी संभावित विकल्पों को ध्यान में रखता है: यहां तक कि एक प्राथमिकता मृत-अंत। इस फॉर्मूले की आवश्यकता प्रत्येक विकल्प की संख्या के कारण होती है, केवल बाद में स्वीकार्यता के लिए विशिष्ट संख्या की जांच करने के लिए। यह देखना आसान है कि 10 जहाजों और 10x10 क्षेत्र के लिए हमें 10 ^ 26 के क्रम का एक नंबर मिलता है, जिसका अर्थ है कि अनुक्रमण के लिए हमें 87 बिट्स के एक चर की आवश्यकता है, जो संरेखण को ध्यान में रखते हुए - कुल। इसके अलावा, क्षेत्र में वृद्धि, या, इससे भी बदतर, जहाजों की संख्या, स्थिति को बढ़ा देती है। इसलिए सिर्फ एक जहाज को जोड़ने से विकल्पों की संख्या लगभग 10 ^ 28 हो जाती है। कोई भी अंतर्निहित (हार्डवेयर-समर्थित) डेटा प्रकार ऐसे नंबरों के साथ काम करने के लिए उपयुक्त नहीं है। बेशक, आप बड़ी संख्या के साथ अंकगणित का अनुकरण कर सकते हैं, लेकिन इसके परिणामस्वरूप खेल तर्क इंजन के एक कार्य के लिए प्रदर्शन और अनावश्यक रूप से बड़े सहायक उपकरणों का नुकसान होगा। इसके अलावा, अनुक्रमणिका के उपयोग का अर्थ है कि प्रत्येक अनुक्रमणिका को एक अनूठी व्यवस्था के साथ मिलान करना, अर्थात, सूचकांक अभी भी जहाजों के रोटेशन के निर्देशांक और कोण को दर्शाती संख्याओं के एक निश्चित समूह में "ब्रेक अप" करेगा। यदि आप अभी भी इसके बारे में सोचते हैं, तो आप अनुक्रमणिका के बाद के अनुप्रयोग की प्रकृति का उपयोग करके, बड़ी संख्या की समस्या के आसपास हो सकते हैं।

एक जहाज के लिए विकल्पों की गणना

वास्तव में, हम कहते हैं: संख्या का एक ट्रिपल एक जहाज की विशेषता है, और इस तरह के "ट्राइएन्स" का एक सेट - एक स्क्वाड्रन। विशेषताओं का आदेश देने के बाद, हम स्पष्ट कर सकते हैं: पहली संख्या में समन्वय की विशेषता है और 0 से (यमक्स -1) में भिन्न होता है, दूसरा - अनुपस्थित है और [0 से संबंधित है; Xmax-1], बाद वाला रोटेशन कोण है, जो चार अनुमत राज्यों को लेता है। थोड़े विचार के साथ, आप कल्पना कर सकते हैं कि ऑर्डिनेट-एब्सकिसा-कॉर्नर ट्री के रूप में जहाज की स्थिति और रोटेशन को चिह्नित करने वाली चाबियां (एक डेक आसान धारणा के लिए चिह्नित है; कार्य क्षेत्र एक 2x2 क्षेत्र है):

इस तरह के पेड़ में एक गहरी खोज {000}, {001}, {002}, {003}, {010}, {011}, {012} ... {113} मूल्यों को वापस करेगी। यह देखना आसान है कि कुंजियों की गणना एक स्थितिगत संख्या प्रणाली में संख्याओं की गणना से मिलती है जिसमें प्रत्येक अंक का अपना मान होता है। चूंकि हमारी प्रणाली का प्रत्येक बिट स्वतंत्र है और जहाज की स्वतंत्रता की डिग्री में से एक की विशेषता है, इसलिए प्रमुख पीढ़ी के एल्गोरिथ्म को निम्नलिखित आभासी मशीन के रूप में दर्शाया जा सकता है:

निचली रेल को आगे बढ़ाते हुए, हम क्रमिक रूप से कुंजियाँ प्राप्त करेंगे: {000}, {001}, {002} और {003}, जिसके बाद रेल "समाप्त" होगी। निम्न आदेश समाप्त होने के बाद, हम इसकी रेल को उसकी प्रारंभिक अवस्था में लौटाते हैं और औसत एक स्थिति को स्थानांतरित करते हैं। जनरेटर {010}, {011}, {012} और {013} लौटाता है - निचले और मध्य बिट्स समाप्त हो जाते हैं। हम सभी थकावटों की स्थिति को "रीसेट" करते हैं, और ऊपरी रेल को एक स्थान पर स्थानांतरित करते हैं: {100}, {101}, {102} और {103}।
इस प्रकार, अगला प्रमुख अनुरोध एल्गोरिथ्म इस प्रकार है:

स्क्वाड्रन के विकल्प की गणना

एक जहाज के साथ निपटाकर, हम खुद को थोड़ा सार कर सकते हैं और स्क्वाड्रन के लिए समस्या का समाधान कर सकते हैं। कुंजी उत्पन्न करने का सिद्धांत समान है, केवल पटरियों के बजाय, जनरेटर पहले से ही चर्चा करते हैं। हम क्रमिक रूप से कम से कम महत्वपूर्ण बिट के सभी मूल्यों (जो कि यहां सबसे कम जनरेटर है) के माध्यम से छंटनी करते हैं, जब तक यह ओवरफ्लो नहीं होता है, तब "अगले बिट को एक से बढ़ाएं" (अर्थात, संबंधित जनरेटर से एक नया मूल्य का अनुरोध करें) और निचले एक के माध्यम से स्क्रॉल करें
{{000}, {000}}
{{000}, {001}}
{{000}, {002}}
{{000}, {003}}
{{000}, {010}}
...
{{000}, {113}}
{{001}, {000}}
...
{{113}, {113}}

नक्षत्र सृजन

इसलिए, आखिरकार, हमने पहली समस्या को हल किया: हम सभी संभावित व्यवस्थाओं के माध्यम से लगातार हल कर सकते हैं। अब संस्करण सत्यापन के मुद्दे पर विचार करें।
एल्गोरिथ्म सरल है: हमें पहले जहाज के लिए कुंजी मिलती है, यदि जहाज को रखना संभव है, तो हम इसे मैदान पर सेट करते हैं और अगले जहाज पर जाते हैं, अन्यथा हम इस जहाज के लिए अगली कुंजी उत्पन्न करते हैं। यदि चाबियाँ खत्म हो जाती हैं, तो एक संकेत दें "उच्च": पिछले जहाज के लिए हम एक नई वैध कुंजी का चयन करते हैं, पोत को पुनर्स्थापित करें और "वापसी" करें। स्थिति प्रणाली में संख्याओं के साथ सबकुछ ठीक है, केवल कुछ प्रतिबंधात्मक नियम दिखाई दिए हैं जो कुछ संयोजनों को रोकते हैं।
नियमों को आसानी से तार्किक श्रेणियों में विभाजित किया जा सकता है, इस प्रकार अनिवार्य मानदंडों को पेश करके सत्यापन को तेज किया जा सकता है। उदाहरण के लिए: एक जहाज को खेल के मैदान पर सभी फिट होना चाहिए यह साधारण मानदंड, ऊपर दिए गए मामले के संबंध में, तुरंत 75% नक्षत्रों को काट देगा। आगे की जाँच आपके कार्यान्वयन में डेटा के संगठन पर निर्भर करती है।

दुर्घटनाओं

यह सब अच्छा है, लेकिन क्रियाओं का निर्धारक अनुक्रम हमेशा एक ही संयोजन उत्पन्न करेगा, भले ही उनमें से कई उपलब्ध हों। समाधान अपमान करने के लिए सरल है: आपको जनरेटर में रेल पर संख्याओं को मिश्रण करने की आवश्यकता है। बस, मैं कर्मचारियों से पढ़ रहा हूँ, कुछ random_num [i] सरणी के i-वें तत्व का मान कॉल बिंदु पर लौटाता हूँ।
सरणी तत्वों के मिश्रण में, निम्नलिखित की सिफारिश की जा सकती है।
सबसे पहले, सूत्र को दूसरे तत्व के सूचकांक को उत्पन्न करने के लिए गारंटी दी जाती है, पहले से अलग। बेशक, आप काल्पनिक एक्सचेंज random_num [j] <-> random_num [j] को प्रतिबंधित नहीं कर सकते, लेकिन इस पर चलना क्यों खर्च करते हैं?

//N –     //% -    unsigned a_indx=rand()%N; unsigned b_indx=(a_indx+1+rand()%(N-1))%N; //      //-  '%' –    //

दूसरे, पूर्ण मिश्रण ( अव्यवस्था ) के लिए न्यूनतम पर्याप्त राशि के रूप में व्यक्त किया गया है

 ceil(N*0.5);

"युवा" रेल और "अच्छे" जनरेटर पर संख्याओं के मिश्रण का एक उदाहरण नीचे दिया गया है:

विनिमय के दो पुनरावृत्तियों, इस मामले में, मिश्रण को पूरा करने के लिए। कृपया ध्यान दें: यह जनरेटर, मूल एक की तरह, कुंजी के पूरे सेट को वापस कर देगा, लेकिन एक अलग क्रम में, जो आपको मामले से मामले में अलग-अलग व्यवस्था बनाने की अनुमति देगा। मैं ध्यान देता हूं कि "यादृच्छिकता" एक मुख्य रूप से व्यक्तिपरक अवधारणा है, और प्राचीन स्लैट्स को यादृच्छिक माना जा सकता है।

पिछली श्रृंखला में

(अगर मैं किसी का जिक्र करना भूल गया तो पीएम से माफी चाहता हूं। पीएम को सूचित करें)

निष्कर्ष

इस लेख में महारत हासिल करने वाले सभी को धन्यवाद, इसे पढ़ने के लिए समय निकालें। मैं सवालों के जवाब देने और आलोचना पर टिप्पणी करने की कोशिश करूंगा। निवेदन: पीएम में प्रूफरीडिंग के लिए टिप्पणियां और सुझाव लिखें ताकि लेख के विषय से चर्चा को न मोड़ें।

खेल "समुद्री लड़ाई": जहाजों की व्यवस्था