एक सी ++ बीजगणित खेल के संस्करण लेखन 24

Question

मैं एक सी ++ प्रोग्राम है जो खेल 24. तरह काम करता है उन लोगों के लिए जो नहीं जानता कि यह कैसे खेला जाता है लिखने के लिए कोशिश कर रहा हूँ, मूल रूप से आप किसी भी तरह से है कि 4 नंबर कर सकते हैं खोजने की कोशिश +, -, /, *, और कोष्ठक के चार बीजगणितीय ऑपरेटरों के माध्यम से कुल 24।

उदाहरण के लिए, किसी आदानों 2,3,1,5 ((2 + 3) * 5) कहते हैं - 1 = 24

यह अपेक्षाकृत सरल समारोह कोड करने के लिए निर्धारित करने के लिए किया गया है, तो तीन नंबर कर सकते हैं 24 कोष्ठक के लिए सीमित पदों की वजह से 24 बनाते हैं, लेकिन मैं यह नहीं समझ सकता कि चार चरों को कब दर्ज किया जाता है जब यह कुशलतापूर्वक कोड करता है।

---

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

इसके अलावा, क्या आरपीएन गणना करने के लिए सबसे आसान तरीका है? मैं इस तरह के कई पृष्ठों पर आया: http://www.dreamincode.net/forums/index.php?showtopic=15406 लेकिन शुरुआत के रूप में, मुझे यकीन नहीं है कि इसे कैसे कार्यान्वित किया जाए।

#include <iostream> 
#include <vector> 
#include <algorithm> 
using namespace std; 





bool MakeSum(int num1, int num2, int num3, int num4) 
{ 

    vector<int> vi; 
    vi.push_back(num1); 
    vi.push_back(num2); 
    vi.push_back(num3); 
    vi.push_back(num4); 

    sort(vi.begin(),vi.end()); 


    char a1 = '+'; 
    char a2 = '-'; 
    char a3 = '*'; 
    char a4 = '/'; 
    vector<char> va; 
    va.push_back(a1); 
    va.push_back(a2); 
    va.push_back(a3); 
    va.push_back(a4); 

    sort(va.begin(),va.end()); 
    while(next_permutation(vi.begin(),vi.end())) 
    { 

     while(next_permutation(va.begin(),va.end())) 
    { 

     cout<<vi[0]<<vi[1]<<vi[2]<<vi[3]<< va[0]<<va[1]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< vi[3]<<va[1]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<vi[2]<<va[0]<< va[1]<<vi[3]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< vi[3]<<va[1]<<va[2]<<endl; 

     cout<<vi[0]<<vi[1]<<va[0]<<vi[2]<< va[1]<<vi[3]<<va[2]<<endl; 


    } 

    } 

    return 0; 

} 

int main() 
{ 

    MakeSum(5,7,2,1); 
    return 0; 
} 

Answer 1

तो, सरल तरीका सभी संभव संयोजनों के माध्यम से दूसरे स्थान पर रखना है:

यहाँ एक किसी न किसी तरह, अपरीक्षित कोड उदाहरण है। यह थोड़ा मुश्किल है, संख्याओं का क्रम महत्वपूर्ण हो सकता है, और निश्चित रूप से संचालन का क्रम है।

एक अवलोकन यह है कि आप कुछ गुणों के साथ सभी संभावित अभिव्यक्ति पेड़ों को उत्पन्न करने की कोशिश कर रहे हैं। एक संपत्ति यह है कि पेड़ हमेशा 4 पत्तियों के पास होगा। इसका मतलब है कि पेड़ में हमेशा 3 आंतरिक नोड्स भी होंगे। ऐसे पेड़ के लिए केवल 3 संभावित आकार हैं:

A 
/\ 
N A 
/\  (and the mirror image) 
    N A 
    /\ 
    N N 

    A 
/\ 
N A 
/\ 
    A N (and the mirror image) 
/\ 
N N 

    A 
    /` `\ 
    A  A 
/\ /\ 
N N N N 

ए के लिए प्रत्येक स्थान में आप 4 संचालन में से कोई भी हो सकते हैं। एन के लिए प्रत्येक स्थान पर आप संख्याओं में से किसी एक को प्राप्त कर सकते हैं। लेकिन प्रत्येक नंबर केवल एक एन

ब्रूट फोर्स सर्च के रूप में कोडिंग करना बहुत कठिन नहीं होना चाहिए, और मुझे लगता है कि आपके द्वारा काम करने के बाद यह अनुकूलन के बारे में सोचना आसान हो जाएगा।

उदाहरण के लिए, + और * कम्यूटिव हैं। इसका मतलब है कि उन परिचालनों के बाएं और दाएं बच्चों को फ़्लिप करने वाले दर्पणों का कोई प्रभाव नहीं पड़ेगा। ऐसे सभी फ्लिपों के माध्यम से खोज करना संभव हो सकता है।

किसी और ने आरपीएन नोटेशन का उल्लेख किया। पेड़ सीधे इस पर नक्शा।

N N N N A A A 
N N N A N A A 
N N N A A N A 
N N A N N A A 
N N A N A N A 

4 * 3 * 2 = संख्या के लिए 24 संभावनाओं, 4 * 4 * 4 = संचालन के लिए 64 संभावनाओं, 24 * 64 * 5 = 7680 कुल संभावनाओं है कि: यहाँ आरपीएन में हर संभव पेड़ की एक सूची है 4 संख्याओं के दिए गए सेट के लिए। आसानी से गणनीय और आधुनिक प्रणाली पर एक सेकंड के एक छोटे से हिस्से में मूल्यांकन किया जा सकता है। बिल्ली, यहां तक ​​कि मेरी पुरानी अटारी 8 बिट पर भी मूलभूत बात यह है कि इस समस्या में केवल 4 संख्याओं के दिए गए समूह के लिए कुछ मिनट लगेंगे।

Answer 2

मैंने पहले ऐसा कुछ लिखा था। आपको एक पुनरावर्ती मूल्यांकनकर्ता की आवश्यकता है। जब आप हिट करते हैं तो कॉल मूल्यांकन करें, "(" कॉल फिर से मूल्यांकन करें जब तक कि आप हिट नहीं करते हैं तब तक अंकों और ऑपरेटरों के साथ चलते हैं "), अब + +/ऑपरेशंस के परिणाम को आपके ऊपर मूल्यांकन उदाहरण

Answer 3

देखें Knapsack समस्या (यहां आपको प्रारंभ करने के लिए एक लिंक दिया गया है: http://en.wikipedia.org/wiki/Knapsack_problem), यह समस्या उस के करीब है, बस थोड़ा कठिन है (और Knapsack समस्या एनपी-पूर्ण है!)

Answer 4

एक चीज जो सामान्य से अधिक तेज़ी से कर सकती है समांतरता है। OpenMP देखें। इसका उपयोग करके, एक से अधिक चेक एक बार में किया जाता है (आपका "एल्ग" फ़ंक्शन) इस प्रकार यदि आपके पास दोहरी/क्वाड कोर सीपीयू है, तो आपका प्रोग्राम तेज़ होना चाहिए।

यही कारण है, ने कहा कि यदि इस समस्या को ऊपर सुझाए गए एनपी पूरा हो गया है, यह तेजी से है, जरूरी तेजी से नहीं हो जाएगा।

Answer 5

तुम बस Reverse Polish Notation का उपयोग संभव भाव है, जो parantheses की आवश्यकता को दूर करना चाहिए उत्पन्न करने के लिए कर सकते हैं।

ऐसा करने का एक बिल्कुल बेवकूफ तरीका 4 अंकों और 3 ऑपरेटरों के सभी संभावित तार उत्पन्न करना होगा (आरपीएन के रूप में वैधता पर ध्यान नहीं देना), मान लीजिए कि यह आरपीएन में है और इसका मूल्यांकन करने का प्रयास करें। आप कुछ त्रुटि मामलों को दबाएंगे (जैसे अवैध आरपीएन तारों में)। संभावनाओं की कुल संख्या (यदि मैंने सही ढंग से गणना की है) ~ 50,000 है।

एक और अधिक चालाक जिस तरह से यह नीचे मिलना चाहिए ~ 7500 को मेरा मानना ​​है कि (64 * 24 * 5 सटीक होना करने के लिए): अंक (24 तरीके) का क्रमपरिवर्तन उत्पन्न करें, 3 ऑपरेटरों (4^3 के एक त्रिक उत्पन्न = 64 तरीके) और अब ऑपरेटरों को अंकों के बीच वैध आरपीएन बनाने के लिए रखें (5 तरीके हैं, सर्वव्यापी 'उत्तर देखें)।

आप वेब पर आसानी से क्रमचय जनरेटर और आरपीएन कैलकुलेटर खोजने के लिए सक्षम होना चाहिए।

आशा है कि मदद करता है!

पुनश्च: बस FYI: आरपीएन लेकिन इसी अभिव्यक्ति पेड़ के क्रंमोत्तर चंक्रमण कुछ भी नहीं है, और घ अंकों के लिए संख्या घ है! * 4^(डी -1) * चुनें (2 (डी -1), (डी -1))/डी। (अंतिम शब्द एक आदर्श संख्या है)।

Answer 6

संपादित: नीचे समाधान गलत है। हमें केवल x_2 और x_4, और केवल x_1 और x_4 के साथ बनाने योग्य संख्याओं पर विचार करने की आवश्यकता है। यह दृष्टिकोण अभी भी काम कर सकता है, लेकिन यह अधिक जटिल (और यहां तक ​​कि कम कुशल) होने जा रहा है। क्षमा करें ...

---

मान लीजिए हम चार नंबर x_1, x_2, x_3, x_4 है। लिखें

S = { all numbers we can make just using x_3, x_4 }, 

फिर हम सेट हम में रुचि रखते हैं, जो मुझे फोन करता हूँ पुनर्लेखन कर सकते हैं

T = { all numbers we can make using x_1, x_2, x_3, x_4 } 

रूप

T = { all numbers we can make using x_1, x_2 and some s from S }. 

तो एक एल्गोरिथ्म में हर संभव संख्या उत्पन्न करने के लिए है एस, फिर टी के हिस्से को उत्पन्न करने के लिए एस में प्रत्येक संख्या का उपयोग करें। (यह केवल 4 की बजाय एन संख्याओं के लिए काफी आसानी से सामान्यीकृत होगा)।

#include <set> // we can use std::set to store integers without duplication 
#include <vector> // we might want duplication in the inputs 

// the 2-number special case 
std::set<int> all_combinations_from_pair(int a, int b) 
{ 
    std::set results; 

    // here we just use brute force 
    results.insert(a+b); // = b+a 
    results.insert(a-b); 
    results.insert(b-a); 
    results.insert(a*b); // = b*a 
    // need to make sure it divides exactly 
    if (a%b==0) results.insert(a/b); 
    if (b%a==0) results.insert(b/a); 

    return results; 
} 

// the general case 
std::set<int> all_combinations_from(std::vector<int> inputs) 
{ 
    if (inputs.size() == 2) 
    { 
    return all_combinations_from_pair(inputs[0], inputs[1]); 
    } 
    else 
    { 
    std::set<int> S = all_combinations_from_pair(inputs[0], inputs[1]); 
    std::set<int> T; 
    std::set<int> rest = S; 
    rest.remove(rest.begin()); 
    rest.remove(rest.begin()); // gets rid of first two 

    for (std::set<int>.iterator i = S.begin(); i < S.end(); i++) 
    { 
     std::set<int> new_inputs = S; 
     new_inputs.insert(*i); 
     std::set<int> new_outputs = all_combinations_from(new_inputs); 

     for (std::set<int>.iterator j = new_outputs.begin(); j < new_outputs.end(); j++) 
     T.insert(*j); // I'm sure you can do this with set_union() 
    } 

    return T; 
    } 
} 

Answer 7

यदि आपको दो बार एक ही ऑपरेटर का उपयोग करने की अनुमति है, तो आप शायद ऑपरेटरों को संख्याओं में मिश्रित नहीं करना चाहते हैं। इसके बजाए, शायद प्लेसहोल्डर के रूप में तीन 0 का उपयोग करें जहां संचालन होगा (4 संख्याओं में से कोई भी 0 नहीं है, है ना?) और यह निर्धारित करने के लिए कि कौन से संचालन का उपयोग किया जाएगा, एक और संरचना का उपयोग करें।

दूसरी संरचना vector<int> हो सकती है जो तीन 1 के बाद शुरू होती है और उसके बाद तीन 0 होती है।में 0 के अनुरूप है। एक 0 शून्य 1 के से पहले किया जाता है, इसी आपरेशन अगर एक 1 से पहले, + है, यह -, आदि है उदाहरण के लिए: एक आंतरिक पाश में next_permutation का उपयोग कर आपरेशन संभावनाओं के माध्यम से

6807900 <= equation of form (6 @ 8) @ (7 @ 9) 
100110 <= replace @'s with (-,-,/) 
possibility is (6-8)-(7/9) 

अग्रिम।

वैसे, यदि आप संख्या-क्रमपरिवर्तन एक अमान्य पोस्टफिक्स अभिव्यक्ति है तो भी आप जल्दी वापस आ सकते हैं। 67080 9 0 से कम उपर्युक्त उदाहरण के सभी क्रमिक अमान्य हैं, और सभी अधिक मान्य हैं, इसलिए आप 9876000 से शुरू कर सकते हैं और prev_permutation के साथ अपना रास्ता कम कर सकते हैं।