मैं नीचे दिए गए प्रश्न की तरह पुनरावृत्ति संबंध नहीं लिख सकता।
आयताकार ग्रिड को देखते हुए, आयाम 4 x n के साथ, 2 x 2 और 2 x 1 डोमिनोज़ के साथ ग्रिड को पूरी तरह से टाइल करने के कितने तरीके हैं?
यहाँ 2 x 1 आयतों के लिए यह बहुत किया जाता है, लेकिन मैं नहीं समझ सकता कि अगर आयतें 2 x 1 और 2 x 2 हैं: http://www.acmgnyr.org/year2007/h.c
कोई विचार?
उदाहरण के लिए
4x1: 1 रास्ता
4x2: 11 तरीके
4x3: 29 तरीके
नीचे दिए गए कोड ब्रूट बल का उपयोग करके सभी संभावनाएं उत्पन्न करते हैं। लेकिन मैं इसे गतिशील प्रोग्रामिंग का उपयोग करके करना चाहता हूं।
https://gist.github.com/4519601
उत्तर:
जवाब के लिए 2 № 1मुझे लगता है कि आप एक गतिशील प्रोग्रामिंग एल्गोरिदम का उपयोग करके इसे हल कर सकते हैं।
4 x n ग्रिड के रूप में ग्रिड का प्रतिनिधित्व करने की कल्पना करेंचौकों के रूप में, लेकिन प्रत्येक व्यक्तिगत कॉलम की चौड़ाई का प्रतिनिधित्व करने वाले 4-ट्यूपल के रूप में। हर बार जब आप एक टाइल लगाते हैं, तो आप इसे कहीं रखकर कोशिश कर सकते हैं कि इसका एक वर्ग ग्रिड के सुदूर-बाएँ कोने के ऊपरी-बाएँ कोने को छूता है। ऐसा करने का प्रभाव स्तंभों में से प्रत्येक की प्रभावी चौड़ाई को बदलना है। उदाहरण के लिए, यह 4 x 3 ग्रिड दिया गया:
. . .
. . .
. . .
. . .
हम इसे (3, 3, 3, 3) के रूप में एन्कोड करेंगे। यदि आपको ऊपरी कोने में 2 x 2 ब्लॉक रखना था, तो आपको यह मिल जाएगा:
X X .
X X .
. . .
. . .
इसे (1, 1, 3, 3) के रूप में एन्कोड किया जाएगा, क्योंकि शीर्ष दो पंक्तियाँ अब प्रभावी रूप से बहुत छोटी हैं।
यह प्रारंभिक (अकुशल) पुनरावर्ती का सुझाव देता हैकलन विधि। आपके आधार मामलों के रूप में, दुनिया (0, 0, 0, 0) का सिर्फ एक समाधान है (अर्थात्, कुछ नहीं करना)। ऐसी कोई भी दुनिया, जहां बाईं ओर सबसे ऊपरी वर्ग को कवर करने वाली टाइल लगाने का कोई कानूनी तरीका नहीं है, जिसका कोई हल नहीं है। अन्यथा, सभी संभव कदमों के लिए, उस चाल को बनाएं, दुनिया के आंतरिक प्रतिनिधित्व को अपडेट करें, और उन सभी समाधानों में पुनरावृत्ति करें जो आप उस छोटी दुनिया में पा सकते हैं।
यह बेहद धीमी गति से (तेजी से ऐसा) है, लेकिन नाटकीय रूप से ऊपर जा सकता है। विशेष रूप से, ध्यान दें कि संभावित 4-ट्यूपल्स की संख्या है (n + 1)4। इसका अर्थ है कि अधिकतम पुनरावर्ती कॉल की अधिकतम संख्या O (n) है4)। इसलिए, यदि आप अपने पुनरावर्ती कॉल को याद करते हैं या कॉल की पीछे की गणना करने के लिए गतिशील प्रोग्रामिंग का उपयोग करते हैं, तो आपको केवल एक बहुपद संख्या कॉल करना होगा। एक मौजूदा पुनरावर्ती समाधान में जोड़ने के लिए मेमोइज़ेशन बहुत आसान होना चाहिए, और स्पीडअप बहुत बड़ा होना चाहिए।
यदि आप "अधिक गणितीय रूप से देख रहे हैंइस समस्या को हल करने का सटीक तरीका, इस समस्या के लिए एक जनरेटिंग फंक्शन लिखने की कोशिश करना और इसे बंद-बंद समाधान को प्राप्त करना। एक बार जब आप ऐसा कर लेते हैं, तो इसे "उपरोक्त सभी समाधानों की तुलना में अधिक कुशलता से मूल्यांकन करने के लिए कठिन नहीं होना चाहिए। चूंकि मैं" कार्यों को उत्पन्न करने में विशेषज्ञ नहीं हूं, हालांकि, मैं वास्तव में यह सुनिश्चित नहीं करता हूं कि आप यह कैसे करते हैं। ।
उम्मीद है की यह मदद करेगा!
जवाब के लिए 0 № 2
में 4xn, n या तो विषम है। अगर n यहां तक कि, बस उपयोग है 2x2 डोमिनो। अन्यथा, उपयोग करें 2x2 तक n-1। फिर दो का उपयोग करें 2x1 खत्म करने के लिए डोमिनोज़ 4x1 शेष ब्लॉक। जवाब देने में मैंने आपके लिंक का पालन नहीं किया क्योंकि मुझे लगता है कि प्रश्न पर्याप्त रूप से कहा गया है और लिंक केवल एक सरल समस्या के लिए आपका जवाब है।
n = सम
use n 2x2 dominoes
n = विषम
use n-1 2x2 dominoes plus 2 2x1 domino
यदि n = 10 तो 4 * 10 = 40 और (2x2) * 10 = 40
अगर n = 11 तो 4 * 11 = 44 और (2x2) * 10 = 40 और (2x1) * 2 = 4 कुल 44 के लिए