प्रोजेक्ट यूलर # 163 समझ

Question

मैंने this problem के समाधान के लिए काफी समय बिताया। मैंने क्रॉस-हाइड किए गए त्रिकोणों को आकर्षित किया, सरल मामलों में त्रिकोणों की गणना की, और कुछ प्रकार के पैटर्न की खोज की। दुर्भाग्य से, मैंने दीवार मारा। मुझे पूरा यकीन है कि मेरे प्रोग्रामिंग/गणित कौशल इस समस्या के लिए prereq को पूरा नहीं किया था।

इसलिए मैं आदेश मंचों तक पहुंच हासिल करने में ऑनलाइन एक समाधान मिल गया। मुझे सबसे अधिक तरीकों को समझ में नहीं आया, और कुछ बहुत जटिल लग रहे थे।

क्या कोई मुझे इस समस्या की समझ दे सकता है? यहां पाए गए तरीकों में से एक: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (समस्या सी) एक एकल फ़ंक्शन का उपयोग करने की अनुमति है।

वे उस समाधान के साथ कैसे आए? इस बिंदु पर, मैं वास्तव में इस दिलचस्प समस्या के पीछे कुछ अवधारणाओं को समझना चाहता हूं। मुझे पता है कि समाधान यूलर भावना का हिस्सा नहीं था, लेकिन मुझे पूरा यकीन है कि मैं इस समस्या को किसी भी तरह हल नहीं कर सका।

Answer 1

यह अनिवार्य रूप से गणनासूचक साहचर्य में एक समस्या है, जो चीजों के संयोजन की गिनती की कला है। यह एक सुंदर विषय है, लेकिन आपके द्वारा दिए गए संदर्भ में निंजा चाल की सराहना करने से पहले शायद कुछ गर्म हो जाता है।

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

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

तीन पंक्तियों को देखते हुए, उनके चौराहे बिंदुओं की गणना करें। आपके पास तीन संभावनाएं होंगी 1) रेखाएं संयोगी हैं - वे सभी एक सामान्य बिंदु 2 में छेड़छाड़ करते हैं) दो पंक्तियां त्रिभुज 3 के बाहर एक बिंदु पर छेड़छाड़ करती हैं 3) चौराहे के सभी तीन बिंदु अलग हैं, और वे सभी भीतर स्थित हैं बाहरी त्रिकोण

बस कॉम्बो हालत (3) को संतोषजनक गिनती और आप कर रहे हैं। आपको परीक्षण करने के लिए लाइन combos की संख्या ओ (एन) है, जो निषिद्ध नहीं है।

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

EDIT2: a combinatorics solution by Bill Daly and others भी देखें। यह गणितीय रूप से दूसरे की तुलना में थोड़ा gentler है।

Answer 2

मैं project euler के लिए इस समस्या को हल नहीं किया है और प्रश्न और समाधान आपके द्वारा दी गई के बंद जा रहा हूँ। एकल समारोह के मामले में, प्रस्तुत की गई पद्धति अंततः सरल पैटर्न खोज थी। घुसपैठ से मौजूद त्रिकोणों के प्रकारों के आधार पर सॉल्वर ने प्रस्तुत किए गए प्रश्न को तीन हिस्सों में तोड़ दिया। यह इस तरह की समस्या के लिए काफी मानक दृष्टिकोण है, सुलझाने के लिए छोटे पैटर्न को छोटे आकार में तोड़ना आसान है। त्रिकोणों के विभिन्न रूपों को व्यक्त करने के लिए उपयोग किए जाने वाले फ़ंक्शंस मैं केवल एक बहुत ही तीव्र पैटर्न को दिमाग या कुछ संख्या सिद्धांत/ज्यामिति ढूंढने के साथ उत्पन्न कर सकता हूं। यह इस स्पष्टीकरण और मेरे ज्ञान के दायरे से भी परे है। इस समस्या के पास प्रोग्रामिंग के साथ कुछ लेना देना नहीं है। यह मूल रूप से पूरी तरह से गणित है। यदि आप जिस साइट को पसंद करते हैं, उसके माध्यम से पढ़ते हैं तो आप उन प्रश्नों को देख सकते हैं जो प्रश्नों तक पहुंचने के लिए गुजर चुके हैं।