🛄 ⚜️ 💅 गतिशील प्रोग्रामिंग। मैच मॉडल 🖊️ 🤲 🚸

नमस्कार, हबहार। इसमें, बाद में मैं समस्याओं के समाधान के उदाहरण का उपयोग करके गतिशील प्रोग्रामिंग के बारे में बात करना चाहता हूं। मैं हाल ही में ओलंपियाड समस्याओं के पोर्टल पर इस कार्य में भाग गया (लिंक अंत में इंगित किया गया है)। तुरंत व्यापार के लिए नीचे उतरो।

कार्य

प्रोफेसर सैमोडेलकिन ने क्यूब किनारों के लिए मैचों का उपयोग करके मैचों से क्यूब्स का एक तीन-आयामी मॉडल बनाने का फैसला किया। प्रत्येक क्यूब की किनारे की लंबाई एक मैच के बराबर होती है।

तीन पासा के मॉडल का निर्माण करने के लिए, उन्होंने 28 मैचों का उपयोग किया।

समोडेलकिन को एन क्यूब्स का एक मॉडल बनाने के लिए सबसे छोटी संख्या में क्या मैच चाहिए?

समस्या की सभी संख्याएँ 2 · 10 ⁹ से अधिक नहीं हैं।

तकनीकी स्थिति

इनपुट डेटा

एक संख्या एन क्यूब्स की संख्या है।

उत्पादन

एक नंबर मैचों की संख्या है।

मैंने गतिशील प्रोग्रामिंग का उपयोग करके इस समस्या को हल किया, लेकिन इसे अन्य तरीकों से हल किया जा सकता है, और यहां तक कि सिर्फ एक सूत्र के साथ - जिसे हम अंत में प्राप्त करेंगे।

_{_{"हालांकि, प्रगणित और कुछ अन्य समस्याओं के बीच, एक समस्या का एक वर्ग अलग-अलग हो सकता है जिनके पास एक अच्छी संपत्ति है: कुछ उपप्रोमीटरों के लिए समाधान (उदाहरण के लिए, एक छोटी संख्या n के लिए), यह संभव है कि मूल समस्या का समाधान लगभग गणना के बिना हो।" - समस्याओं का एक वर्ग जो गतिशील प्रोग्रामिंग द्वारा हल किया जाता है ।}}

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

निर्णय

मैंने इस कार्य को 3 चरणों में विभाजित किया है:

1D मामले के लिए समस्या को हल करें और इसमें मैं 1 मैच में एक पक्ष के साथ एक वर्ग का उपयोग करूंगा, सूत्र प्राप्त करें
2 डी मामले के लिए समस्या को हल करें और इसमें मैं 1 मैच के किनारे के साथ एक वर्ग का उपयोग करूंगा, सूत्र को प्राप्त करूंगा
1 डी और 2 डी मामले में पैटर्न ढूंढें और उनके आधार पर 3 डी केस के लिए समस्या को हल करें, 3 डी केस के लिए सूत्र प्राप्त करें
N- आयामी मामले पर विचार

-1 डी

और इसलिए हम समस्या की स्थितियों को स्थापित करते हैं:

हमें 1 मैच में एक पक्ष के साथ एन वर्गों की एक पंक्ति बनाने के लिए आवश्यक न्यूनतम मैचों का पता लगाना होगा

मैं परिणाम को संग्रहीत करने के लिए DP सरणी का उपयोग करूंगा।

अब हम आकृति को देखते हैं और इस सरणी को उन संख्याओं से भरते हैं जिन्हें i-1 मामले के समाधान में जोड़ने की आवश्यकता होती है:

न:	0	1	2	3	4	5	6	7
डी पी:	0	4	3	3	3	3	3	3

और N का उत्तर 0 से N तक DP सरणी के तत्वों का योग होगा, और तुरंत पैटर्न देखेगा - DP के लिए [1]: = 4 , DP [> 1]: = 3

और सूत्र प्राप्त करें (N हमेशा> 1 है, अर्थात, प्राकृतिक):

परिणाम (N) : = SUM (DP ₁ -> DP _N ) = 4+ (N-1) * 3

2 डी

उद्देश्य:

हमें 1 मैच में एक साइड के साथ चौकों के निर्माण के लिए आवश्यक न्यूनतम मैचों का पता लगाना होगा। आप 2 आयामों में बना सकते हैं।

2 डी में, हमें एक नई समस्या है: मैचों की संख्या को कम करने के लिए A x B को किस आकार के विमान की आवश्यकता है? और जैसा कि कई ने अनुमान लगाया है, यह निश्चित रूप से एक वर्ग है। लेकिन सब कुछ इतना सरल नहीं है, आपको इस विचार को सरल बनाने की आवश्यकता है।

यदि आप ऊपर दिए गए आंकड़े को देखते हैं, तो आप देख सकते हैं कि नए वर्ग के लिए सबसे लाभप्रद स्थिति वह होगी जिसमें अधिक पड़ोसी हैं, और सबसे अच्छी स्थिति में, यह 2 पड़ोसी होंगे।

यही है, इस तरह का निर्माण करने के लिए इष्टतम मामला होगा:

हम आसानी से कह सकते हैं कि अगर हम इसे अपने हाथों से करते हैं तो अगला क्यूब कहां बनाया जाए, लेकिन हम इसके बारे में कंप्यूटर को कैसे बता सकते हैं?

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

प्रारंभ में, यह एक वर्ग 1x1 - 1 वर्ग था, फिर हम इसे 2x1 - 2 वर्ग तक बढ़ाते हैं, फिर:

2x2 - 3 और फिर 4 वर्ग

3x2 - 5 और 6 वर्ग

3x3 - 7.8.9 वर्ग

बारीकी से देखें और पैटर्न देखें: हमारे पास किनारों की संख्या को कम करने के लिए एक ए एक्स बी प्लेन है, एक प्लेन बनाने के लिए अगले वाले ए (1 + 1) एक्स बी और फिर (ए + 1) एक्स (बी + 1) होंगे, बाद वाला एक वर्ग है, जब से हम 1 x 1 से निर्माण शुरू करें

डीपी सरणी के लिए एक तालिका लिखें:

एन	1	2	3	4	5	6	7	8	9
आकार	1 एक्स 1	२ x १	२ x २	२ x २	३ x २	३ x २	३ x ३	३ x ३	३ x ३
डी पी	4	3	3	2	3	2	3	2	2

हम तालिका का विश्लेषण करते हैं:

डीपी [1] = 4 के लिए

इसके अलावा, जब हम एक नई पंक्ति जोड़ते हैं, तो हम 3 मैचों का उपयोग करके एक नया वर्ग बनाते हैं और पंक्ति के अंत तक हम 2 मैचों के साथ वर्ग समाप्त करते हैं। फिर भी जो याद नहीं है 1 डी के साथ मामले को याद करें - पहला वर्ग 4 मैचों का है, बाकी 3 हैं, इस मामले में यह एक ही अतिरिक्त पंक्ति है, लेकिन 3 मैचों के शुरुआती वर्ग और बाकी के 2 मैचों में।

2 डी के लिए एन	1	2	3	4	5	6	7	8	9
1 डी के लिए एन	1	1	1	2	1	2	1	2	3
आकार	1 एक्स 1	२ x १	२ x २	२ x २	३ x २	३ x २	३ x ३	३ x ३	३ x ३
डी पी	4	3	3	2	3	2	3	2	2

अब समाधान एल्गोरिथ्म:

DP[1]=4 
      

        
        
        
      

     A=1 
      

        
        
        
      

     B=1 // A x B  
      

        
        
        
      

         1  N       A  B           DP   1D       A  B      : 
      

        
        
        
      

     j=1 //   DPfor1D,        DPfor1D={3,2,2,2,2,2,2,2,...} 
      

        
        
        
      

     for i = 2 -> N 
      

        
        
        
      

     begin 
      

        
        
        
      

     if A*B<i 
      

        
        
        
      

     then begin 
      

        
        
        
      

     (A<B)?A++:B++ 
      

        
        
        
      

     j=1 
      

        
        
        
      

     end 
      

        
        
        
      

     DP[i]:= DP[i-1]+DPfor1D[j] 
      

        
        
        
      

     j++ 
      

        
        
        
      

     end

या तो:

Result:= 4 
      

        
        
        
      

     newN:= 1 
      

        
        
        
      

     A:= 2 
      

        
        
        
      

     B:= 1 
      

        
        
        
      

     while newN <= N 
      

        
        
        
      

     begin 
      

        
        
        
      

     Result:= Result + 1D(min(A,B)) // 1D(N):=3+(N-1)*2  N >= 1,  0 
      

        
        
        
      

     (A<B)?A++:B++ 
      

        
        
        
      

     newN=A*B 
      

        
        
        
      

     end 
      

        
        
        
      

     (A>B)?A--:B-- 
      

        
        
        
      

     Result:= Result+ 1D(NA*B)

और सूत्र:

परिणाम (N) : = 4 + 3 * (पूर्ण वर्गों की संख्या जो कि संख्या 1 तक N के बिना हैं + अतिरिक्त संख्या जो पूर्ण वर्गों से पहले जाती हैं) + 2 * (बाकी सब कुछ)

N _SQRT : = int (sqrt (N)) - 1

N _ADD : = N _SQRT + 1 (यदि N <= N _SQRT * (N _SQRT +1)

परिणाम (N) : = 4 + 3 * (N _SQRT + N _ADD ) + 2 * (NN _SQRT -N _ADD )

3 डी

तो हम 3 डी मामले के लिए मिला है

त्रि-आयामी मामले में, भवन के लिए मैचों की संख्या को कम करने के लिए, अब, क्यूब्स को एक बड़े क्यूब के निर्माण के उद्देश्य से किया जाना चाहिए, लेकिन मध्यवर्ती मामलों में यह होगा:

A x B x C -> (A + 1) x B x C -> (A + 1) x (B + 1) x C -> (A + 1) x (B + 1) x (C + 1)

2 डी मामले में समाधान एल्गोरिथ्म के समान होगा, लेकिन कुछ नई विशेषताएं दी गई हैं:

1 डी (एन): = 5+ (एन -1) * 3

2D (N): = उपर्युक्त उपधारा में दिया गया एल्गोरिदम, लेकिन समायोजन के साथ - 2D (1): = 8

3 डी (एन): = 2 डी मामले में ऊपर वर्णित एल्गोरिदम, लेकिन तीन-आयामीता को ध्यान में रखते हुए - 3 डी (1): = 12, और जब निर्देशांक बढ़ते हैं, तो हम इस तरह से परिणाम बदलेंगे: परिणाम: = परिणाम + 2 डी (ए * बी * सी / अधिकतम (ए, बी, सी)), i.e. आपको हमारे नए बॉक्स के पैरामीटर को बदलकर जोड़े गए विमान के आकार से 2 डी प्राप्त करना होगा

और 3 डी के लिए सूत्र

सूत्र में 2 डी के सूत्र के समान भाग शामिल होंगे, लेकिन हम केवल पूर्ण वर्ग ही नहीं, बल्कि पूर्ण क्यूब्स को भी ध्यान में रखेंगे।

परिणाम (एन) : = 12 + 8 * (3 * एन _{पूर्ण क्यूब्स} + (0 या 1 या 2 एन के आधार पर)) + 5 * (2 * एन _{पूर्ण वर्ग} + (0 या 1 एन के आधार पर)) + 3 * एन _बाकी

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

N- आयामी मामले पर विचार

पिछले अनुभागों में, हमने जांच की कि घन / वर्ग के लिए मेलों का कम से कम क्या होना चाहिए और इस पर आधारित है कि हम किसी भी माप का एल्गोरिथ्म बना सकते हैं:

आपको यह विचार करने की आवश्यकता है कि मूल एन-आयामी वर्ग में कितने मैच हैं, और गणना करें कि नए तत्वों के निर्माण के लिए आपको कितने मैचों की आवश्यकता है

हमने ऑब्जेक्ट के आयाम को कैप्चर करने के लिए एल्गोरिदम को घटा दिया है - प्रत्येक पुनरावृत्ति पर, 1 सबसे छोटे आयाम से वृद्धि करें।

हमने यह भी महसूस किया कि जब वस्तु के आकार को बदलते हैं, तो (N-1) -थ माप के मान को जोड़ा विमान के आकार से परिणाम में जोड़ा जाना चाहिए

सूत्र बनाते समय, आपको एन डिग्री, एन -1, एन -2, आदि में संख्याओं की संख्या को ध्यान में रखना होगा। + खाते की विशेषताओं को ध्यान में रखें

संदर्भ

E-olimp - यूक्रेन के शैक्षिक संस्थानों के प्रतिभाशाली युवाओं के लिए दूरस्थ प्रोग्रामिंग ओलम्पियाड्स के संगठनात्मक और पद्धति समर्थन के लिए एक इंटरनेट पोर्टल।

पोर्टल पर एक कार्य जिसे आप पास करने की कोशिश कर सकते हैं - पंजीकरण की आवश्यकता है

डायनामिक प्रोग्रामिंग आर्टिकल

गतिशील प्रोग्रामिंग। मैच मॉडल