प्रोग्रामर्स के लिए चुनौतीपूर्ण प्रतियोगिता

हेलो हैब्रेटाटेल।



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







इस तरह की प्रतियोगिता का एक उदाहरण एक n × n शतरंज की बिसात पर 6 रानियों को रखने की समस्या पर एक प्रतियोगिता है। यह पहली बार मेरी प्रतियोगिता के ढांचे में हल किया गया था (सभी कॉन्फ़िगरेशन की संख्या के लिए एक स्पष्ट सूत्र प्राप्त किया गया था) और उन शोधकर्ताओं के बीच एक प्रतिध्वनि का कारण बनता है जो एन्यूमरेटर कॉम्बिनेटरिक्स में शामिल हैं। सूत्र ने स्वयं इस समस्या के शोधकर्ताओं को नए और मजबूत परिकल्पना के निर्माण की अनुमति दी। मैंने इस लेख में Habré में ऐसे कार्यों के संबंध में अपनी स्थिति व्यक्त की।



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



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

कार्य

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



प्रतियोगिता के पृष्ठों पर कार्यों का विस्तृत विवरण दिया गया है, यहां मैं संक्षेप में शर्तों को रेखांकित करूंगा।

समस्या 1. एन की डिग्री के लिए तीन

प्राकृतिक संख्या n दी गई है। एक न्यूनतम पूर्णांक k इस तरह खोजें कि संख्या 3 ^k में दशमलव संकेतन में कम से कम लगातार शून्य शून्य हो। उदाहरण के लिए, n = 1 के लिए, उत्तर k = 10 होगा, 3 ¹⁰ = 59 0 49 के बाद से और यह ट्रिपल की शक्तियों में से पहला है जिसमें एक शून्य होता है। N = 2 के लिए, उत्तर k = 35 है, 3 ³⁵ = 5 00 31545098999707 के बाद से और यह दो शून्य वाले तीनों शक्तियों में से पहला है।

समस्या 2. सिलेण्डर पर डिमर्स

डोमिनोज (अंग्रेजी में लिंक), या डिमर्स की समस्या को कवर करने की एक प्रसिद्ध समस्या है । समस्या का अर्थ 1 × 2 डोमिनोज़ के साथ m × n शतरंजबोर्ड को टाइल करने के तरीकों की संख्या की गणना करना है, ताकि डोमिनोज़ नॉक ओवरलैप न हो, बोर्ड के किनारों से बाहर न निकले और पूरी तरह से बोर्ड को कवर करे। उदाहरण के लिए, यदि n = m = 2 है, तो केवल दो तरीके हैं (दोनों डोमिनोज़ लंबवत या दोनों क्षैतिज रूप से)।



अब हमारे बोर्ड को एक सिलेंडर में "रोल" करें, जो बाईं और दाईं सीमाओं को जोड़ता है। इस मामले में, किसी भी कोटिंग को निम्नानुसार दर्शाया जा सकता है: यदि डोमिनोज़ बाएं किनारे पर बाहर निकलता है, तो इसकी दूसरी छमाही दाईं ओर दिखाई देती है, और इसके विपरीत। 2n × 2n मापने वाले ऐसे चौकोर शतरंज सिलेंडर के झुकाव की संख्या की गणना करना आवश्यक है। N = 1 के लिए, उत्तर 5 होगा, और n = 2 के लिए, उत्तर 121 है ... यदि यह बहुत स्पष्ट नहीं है, तो चित्र प्रतियोगिता के पृष्ठ पर हैं।

समस्या 3. एक वर्ग जाली पर चक्र के आंकड़े

आकार n × n के एक वर्ग जाली को देखते हुए। इसमें, आप 4 चक्र, 6, 8 आदि की लंबाई के साथ सरल चक्र पा सकते हैं, सबसे बड़ी संभव लंबाई तक। [एक सरल चक्र एक चक्र है जिसमें आत्म-चौराहे नहीं होते हैं]। उदाहरण के लिए, 2 × 2 जाली पर लंबाई का एक चक्र होता है 4. 3 × 3 जाली पर 4 लंबाई के 4 चक्र होते हैं, 6 लंबाई के 4 चक्र और 8 लंबाई के 5 चक्र होते हैं, अर्थात यह क्रम उत्तर होगा [4,4,5]। 4 × 4 जाली पर, उत्तर क्रम है [9,12,26,52,76,32,6] (लंबाई 4 से 16 तक)। यह n = 5,6, के उत्तर का नाम देना आवश्यक है ...



इसलिए, सभी प्रतिभागियों का स्वागत है। जो लोग मेरे कंटेस्टेंट और बीमार-शुभचिंतकों का मतलब नहीं समझते हैं, कृपया किसी भी तरह से खुद को न दिखाएं। सौभाग्य है



पुनश्च। हां, ब्लॉग पर "मैं पीआर हूं" पोस्ट करना उचित होगा, लेकिन इसके लिए मेरे पास पर्याप्त कर्म नहीं हैं। यह पोस्ट स्पोर्ट्स प्रोग्रामिंग से भी संबंधित है।