🔵 💣 🎆 बस का टिकट ⚖️ 🌡️ 🙍

पृष्ठभूमि

हममें से जिन्हें आधे घंटे या एक घंटे के बीच से मास्को तक की यात्रा करनी होती है, उन्हें दिमाग पर कब्जा करने और गर्म होने के लिए कुछ देखना पड़ता है जो अभी तक पूरी तरह से जागृत नहीं हुआ है। कोई पढ़ता है, कोई पक्षी फेंकता है, कोई गणित की पहेलियां हल करता है। उदाहरण के लिए, एक क्लासिक पहेली: एक बस टिकट के छह अंकों के बीच, कोष्ठक और ऑपरेटरों को रखें ताकि 100 नंबर प्राप्त हो। ऐसा होता है कि किसी भी तरह से आप एक समाधान नहीं ढूंढ सकते हैं, और एक विशेष पहेली दिन के बाकी हिस्सों में नहीं जाती है। एल्गोरिदम के बारे में आप सोचेंगे।
ब्रैकेट और ऑपरेटरों को प्रतिस्थापित करके और कुछ गणितीय इंजन पर जांच करके "माथे पर" समाधान सूट नहीं किया था, आनुवंशिक एल्गोरिदम ~~जो मैं पागल हूं~~ , जो स्थानीय चरम सीमा में जमा होने की प्रवृत्ति के कारण फिट नहीं था। नतीजतन, कार्य को दिए गए पत्तियों के साथ सभी संभव द्विआधारी पेड़ों की गणना करने के लिए कम किया गया था (उनमें से छह के लिए बिल्कुल 42 )।

चलिए मुद्दे पर आते हैं

जाहिर है, एल्गोरिथ्म की जटिलता घातीय है: एक शीट को जोड़कर, हम पिछले पेड़ की प्रत्येक शीट को एक नोड के साथ सशर्त रूप से प्रतिस्थापित करते हैं। कुछ पेड़ समान होते हैं, लेकिन विषमता में अंतर छोटा होता है।

हालांकि, छह अंकों के लिए, कार्यक्रम एक सेकंड से भी कम समय में चलता है, इस प्रकार जीवन का अधिकार होता है।
हम C ++ में लागू करेंगे। अस्वीकरण: मैं अभी भी सीख रहा हूँ। यदि आपको स्पष्ट रूप से बुरा या केवल गैर-इष्टतम कोड दिखाई देता है, तो कृपया मुझे बताएं।
काफी तुच्छ कंस्ट्रक्टर को छोड़ना, अगले पेड़ बनाने पर विचार करें। पेड़ों के नोड्स ऑपरेटर हैं, जिससे हमें कोष्ठक और प्राथमिकताओं के साथ उपद्रव से बचाया जाता है। केवल पाँच ऑपरेटर हैं: संघनन, जोड़, घटाव, गुणा और भाग। यूनिक माइनस का उपयोग नहीं किया जाता है। हम निम्नलिखित सिद्धांत के अनुसार पेड़ों के माध्यम से छांटते हैं: प्रत्येक सही उप-प्रकार के लिए हम सभी बाएं उपप्रकारों के साथ एक पास बनाते हैं। प्रत्येक ऑपरेटर के लिए दोहराएं, यानी पांच बार। सबट्रीज़ के अंदर भी ठीक वैसा ही होता है।

पेड़ की पीढ़ी

void BinTree::buildNext() { if (type == NUMBER) //  , throw BinTreeLastTree(); //     . try { left->buildNext(); } catch (BinTreeLastTree) { try { right->buildNext(); } catch (BinTreeLastTree) { bool isLast = false; leftSize++; if (leftSize == size) { leftSize = 1; type = (Operation)(type + 1); if (type == NUMBER) //      , { type = CONCAT; //     isLast = true; //   «». } } delete left; delete right; generateSubTrees(); if (isLast) throw BinTreeLastTree(); //       ,    « ». } } }

गणना भी नहीं होगी, इसलिए हम इस पर विस्तार से ध्यान नहीं देंगे।
मुख्य समस्या एक ही समाधान थी: एक सिलिकॉन दोस्त ने मुझे आश्वासन दिया कि (1+ (2 + 3)) और ((1 + 2) +3) दो अलग-अलग चीजें थीं। इसके विपरीत की व्याख्या करने के लिए, हम कोष्ठक की "स्मार्ट" व्यवस्था लागू करते हैं, और परिणाम को फ़िल्टर करने में समय बर्बाद न करने के लिए, हम इसे std :: set पर असाइन करते हैं।

कोष्ठक संहिता

 std::string BinTree::toString(bool parentheses) { switch (type) { case CONCAT: return left->toString() + right->toString(); case ADD: { std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)), rightStr = right->toString(!(right->getType() == ADD || right->getType() == SUB)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":""); } case SUB: { std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + right->toString() + (parentheses?")":""); } case MUL: { std::string leftStr = left->toString(!(left->getType() == MUL || left->getType() == DIV)), rightStr = right->toString(!(right->getType() == MUL || right->getType() == DIV)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":""); } case DIV: return (parentheses?"(":"") + left->toString() + operationSymbol[type] + right->toString() + (parentheses?")":""); case NUMBER: { char str[2] = {(char)(digit[0]+'0'), '\0'}; return str; } default: ; } throw BinTreeException(); }

देखा!

कॉल कोड

 int main() { std::string input; std::cin >> input; std::cout << busPuzzleSolve(input); return 0; } std::string busPuzzleSolve(std::string input) { return BinTree(input.c_str()).solve(); }

परिणाम

 123654 ((((1*2)+3)*6)-5)*4 ((1*(2+(3*6)))+5)*4 ((1*(2+3)*6)-5)*4 ((1*(2-3))+6)*5*4 ((1*2)+(3*6)+5)*4 ((1*2)-(3-6))*5*4 ((1*2)-3+6)*5*4 ((1/(2-3))+6)*5*4 ((12*3)-(6+5))*4 ((12*3)-6-5)*4 (1+23+6-5)*4 (1-((2*3)-(6*5)))*4 (1-(2*3)+(6*5))*4 (12+(3*6)-5)*4 1*(((2+3)*6)-5)*4 1*(2+(3*6)+5)*4 1*(2-(3-6))*5*4 1*(2-3+6)*5*4 1+((2+3+6)*(5+4))

Rar संग्रह में स्काईड्राइव पर कोड (+ परियोजना फ़ाइल कोड :: ब्लॉक) (~ 2.56 KiB)।
पास्टबिन कोड।

बस का टिकट

पृष्ठभूमि

चलिए मुद्दे पर आते हैं

More articles: