लेगो प्लास्टिक ईंटों के साथ संयोजनों की संख्या सी ++

Question

आपके पास कुछ लेगो प्लास्टिक ईंट हैं, सभी ईंटें 1x1x1 हैं। इसके अलावा आपके पास एक टाइल, 1xN (एन < = 80) है, जिस पर आपको लेगो ईंटें रखना चाहिए। आप उन्हें अनुक्रमों में ऑर्डर कर सकते हैं (एक अनुक्रम सही है यदि इसमें 3 या अधिक लगातार ईंटें हैं), आपके पास 2 अनुक्रमों के बीच कम से कम 1 रिक्त स्थान होना चाहिए। आपको टाइल पर ईंटों को रखने वाले विभिन्न संयोजनों की संख्या की गणना करनी चाहिए।

तो टाइल 1X7 है, वहाँ 17 विभिन्न संयोजनों हैं:

यहाँ एक उदाहरण है।

इनपुट: 7 उत्पादन: 17

pic of the example http://mendo.mk/task_files/kocki.gif

इसके अलावा, अगर आप कोई ईंटों यह 1 संयोजन के रूप में गिना रहा है।

मैंने इस समस्या पर काम किया है और मुझे टाइल की अधिकतम लंबाई 14 (3 अनुक्रम) के संभावित संयोजनों की गणना करने का तरीका मिला है। मैंने इसे लूप के लिए उपयोग किया।

मेरी सबसे बड़ी समस्या उन लूपों की बड़ी संख्या है जिन्हें मुझे चलाने की आवश्यकता है। उदाहरण के लिए, 1 अनुक्रम के लिए मैं लूप के लिए 1 का उपयोग करता हूं, 2 अनुक्रमों के लिए 2 लूप + 1 के लिए 1 sequnce ... इसलिए यदि मैं सभी 80 ईंटों का उपयोग करता हूं, तो मैं 20 अनुक्रम बना सकता हूं और मुझे लूप के लिए 210 से अधिक उपयोग करना होगा बड़ी संख्या। तो यह अच्छा होगा अगर मैं उन्हें एक में घोंसला कर सकता हूं। मैंने कोशिश की और यह गन्दा हो गया और यह सही जवाब नहीं देता है।

नए कोड:

#include <iostream> 
using namespace std; 
int main() 
{ 
    long long int places, combinations = 1; 
    cin >> places; 
    long long int f[80], g[80]; 
    f[0] = 0; 
    f[1] = 0; 
    f[2] = 0; 
    g[0] = 1; 
    g[1] = 1; 
    g[2] = 1; 
    for(int i = 3; i<=places; i++) 
    { 
     f[i] = f[i-1] + g[i-3]; 
     g[i] = f[i-1] + g[i-1]; 
    } 
    combinations = f[places] + g[places]; 
    cout << combinations; 
    return 0; 
} 

Answer 1

इस गणना कर रहा है समस्या (outputing नहीं संयोजन सिर्फ उन्हें गिनती) तो यह आसान है। मान लें कि आपने इसे ≥ 3 के लिए हल किया है, अब आप इसे एन + 1 के लिए हल करना चाहते हैं, इसे प्रेरण से हल करें:

मान लें f एक ऐसा कार्य है जो संभावित आइटमों की संख्या दिखाता है जैसे कि अंतिम आइटम ईंट है। और g एक ऐसा फ़ंक्शन है जो संभावित तरीकों की संख्या दिखाता है जैसे कि अंतिम आइटम ईंट नहीं है। और h = f+g सभी संभावित तरीकों से।

तो हमने: प्रारंभिक शर्त के साथ

f(n+1) = f(n) + g(n-2) 
g(n+1) = g(n) + f(n) 

:

for n=0,1,2: g=1, f= 0. 
for n = 3: g=1,f=1 

नमूने:

n=4: g=2,f=2 ==> h=4 
n=5: g=4, f= 3 ==> h=7 
n=6: g=7, f= 4 ==> h=11 
n=7: g=11,f=6 ==> h=17 

आप बस यह एक के साथ पाश के लिए O(n) में हल कर सकते हैं।

---

क्यों:

f(n+1) = f(n) + g(n-2) 
g(n+1) = g(n) + f(n) 

सबसे पहले जाने साबित पहले भाग: याद रखें कि हम च ग्रहण (एन)

काम कर समाधान जो पिछले मद में प्लास्टिक ईंट, और जी (एन) है काम कर रहा समाधान है जिसमें पिछले आइटम में ईंट नहीं है।

एफ (एन + 1) एफ (एन) का मार्ग जारी रख सकता है, जिसका मतलब है कि आखिरी जगह एक ईंट जोड़ना है। जी (एन -2) के बाद तीन ईंट जोड़कर एफ (एन + 1) भी बनाया जा सकता है, इसका अर्थ है एन -1, एन, एन + 1 की कोशिकाएं, ध्यान दें कि हम जी के बाद ईंट नहीं जोड़ सकते हैं (एन -1) या जी (एन) एफ (एन + 1) के लिए वैध समाधान बनाने के लिए क्योंकि वे वैध समाधान नहीं हैं (लगातार ईंटों की संख्या 3 से कम है)। यह भी ध्यान रखें कि जी (एन -3) के बाद ईंटों को जोड़कर उत्पन्न होने वाले तरीकों की संख्या को गिनने की आवश्यकता नहीं है, क्योंकि उन्हें पहले एफ (एन) द्वारा समझाया जाता है। तो हमारे पास f(n+1) = f(n) + g(n-2) है।

इसी तरह आप g(n+1) = f(n)+g(n) साबित कर सकते हैं, इस मामले में आसान है, क्योंकि जी (एन + 1) n तक किसी भी वैध समाधान से बनाया जा सकता है, क्योंकि फ्री स्पेस के लिए लगातार 3 ईंट सीमा मौजूद नहीं है, वे आ सकते हैं किसी भी वैध समाधान के बाद।

Answer 2

सीएस के बजाए गणित प्रशिक्षण वाले व्यक्ति के रूप में, मुझे लगता है कि सईद अमिरी का एल्गोरिदम बहुत अच्छा है और शायद कुछ लाखों तक एन के लिए पर्याप्त तेज़ी से काम करेगा (निश्चित रूप से निरंतर स्मृति के साथ) , समय परिप्रेक्ष्य से एक बेहतर एल्गोरिदम है।

मैं लेने जाएगा वह जहां छोड़ी है:

f(n+1) = f(n) + g(n-2) 
g(n+1) = f(n) + g(n) 

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

  | f(n) | 
    |f(n-1)| 
u(n)=|f(n-2)| 
    | g(n) | 
    |g(n-1)| 
    |g(n-2)| 

है, यू (एन) एक वेक्टर पंक्ति है। तब, निम्न सत्य है:

 
|f(n+1)| |1 0 0 0 0 1| | f(n) | 
| f(n) | |1 0 0 0 0 0| |f(n-1)| 
|f(n-1)| = |0 1 0 0 0 0| . |f(n-2)| 
|g(n+1)| |1 0 0 1 0 0| | g(n) | 
| g(n) | |0 0 0 1 0 0| |g(n-1)| 
|g(n-1)| |0 0 0 0 1 0| |g(n-2)| 

क्या इस से इस प्रकार है, कि u(n) = A * u(n-1), जहां एक मैट्रिक्स से ऊपर है।
फिर, u(n) = (A^(n-2)) * u(2), जहां u(2) वेक्टर है, जिसमें समस्या के प्रारंभिक मान हैं। यह बदले में O(log(n)) जटिलता के साथ एक एल्गोरिदम देता है, क्योंकि आप (A^(n-2)) की गणना करने के लिए तेज़ एक्सपोनिएशन का उपयोग कर सकते हैं और फिर इसे u(2) पर गुणा कर सकते हैं।

बेशक, ऐसी किसी भी तकनीक को शायद किसी प्रकार की बिगइंट की आवश्यकता होगी, अन्यथा ओवरफ्लो बहुत अधिक गारंटीकृत है।

भी ध्यान रखें कि इस तकनीक का एक कदम आगे लागू किया जा सकता:
आप eigenvectors और एक की eigenvalues ​​पा सकते हैं और उसके बाद eigenvectors में u(2) विघटित। फिर, आपके पास एफ (एन) और जी (एन) दोनों के लिए एक बंद फॉर्म होगा।

मैं दृढ़ता से एक एल्गोरिथ्म बंद फार्म के आधार पर के खिलाफ आपको सलाह
यह लगभग निश्चित रूप उच्च परिशुद्धता शामिल होगी फ्लोटिंग प्वाइंट गणना (जब तक सब eigenvalues ​​पूर्णांक हैं, जो बहुत संभावना नहीं है), के हैं जो कम से कम प्रोग्रामिंग परिप्रेक्ष्य से यह जटिलता, और आम तौर पर निरंतर समय के संचालन नहीं होते हैं। बेशक, न तो BigInt संचालन हैं। तो एक निरंतर समय एल्गोरिदम आम तौर पर व्यवहार्य नहीं है, इसके अलावा आपको शायद O(log(n)) की भी आवश्यकता नहीं है, क्योंकि अधिकांश उपयोग रैखिक पर्याप्त है।

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