खेल में चलनी विधि "बैल और गाय"

नमस्ते
गिरावट में वापस, 2 साल में, "ऑटोमेटा के सिद्धांत" पर एक प्रयोगशाला के काम के रूप में, जाने पर शिक्षक ने मूल्यांकन में हमारी इच्छाओं पर ध्यान केंद्रित करते हुए, हमारे लिए कार्यों का आविष्कार किया। ये ज्यादातर खेल थे। किसी को हॉकी मिली, किसी को टेनिस मिली, लेकिन मुझे इतना प्रसिद्ध लॉजिक गेम "बुल्स एंड कॉज़" नहीं मिला।



एक व्यक्ति के साथ खेल में कंप्यूटर के कम से कम कुछ उचित व्यवहार का एहसास करना आवश्यक था। लेकिन मैं आगे बढ़ गया और एक महीने के भीतर ज्यादातर मामलों में कंप्यूटर ने मेरे सहपाठियों को आसानी से हरा दिया। और विषय पर स्वचालित प्राप्त किया गया था। एल्गोरिदम के वर्णन के बाद कार्यक्रम प्राप्त करें।

खेल का सार

खिलाड़ी और कंप्यूटर 0 से 9 तक की संख्या का उपयोग करके चार अंकों की संख्या बनाते हैं। खिलाड़ी प्रतिद्वंद्वी संख्याओं को संभव संख्या में भेजने की कोशिश करते हैं, बदले में दो नंबर - "बैल" और "गाय" की संख्या प्राप्त करते हैं। ये किस तरह की संख्या है?

• "बैल" सही स्थानों में सही संख्या हैं। चार "बैल" जीत की गारंटी हैं, हर किसान का सपना।
• "गायें" गलत स्थानों पर सही संख्या हैं।

समझने के लिए, मैं एक उदाहरण दूंगा:

1622 नंबर बना है । यदि हम 6112 मान लेते हैं, तो उत्तर होगा: 1 बैल (उसके स्थान पर चौथा अंक "2"), 2 गाय (छः और एक जगह से)।

दुश्मन के "मवेशी" पर डेटा का उपयोग करते हुए, आपको उसकी तुलना में तेजी से संख्या का अनुमान लगाने की आवश्यकता है।

पहला तुच्छ एल्गोरिथ्म, जो इसे भीख देता है, "1111", "2222", "3333" सेट पर पुनरावृति करना है ... जब तक कि एक पूर्ण सेट प्राप्त नहीं होता है, और फिर इस सेट के आंदोलनों को उत्पन्न करता है।

उदाहरण के लिए, समान संख्या 1622 का अनुमान लगाया गया है, हम मानते हैं कि "1111" , हमें जवाब में "बैल" मिलता है, फिर "2222" - हमें जवाब में 2 "बैल" मिलते हैं, "3333" खाली है, "4444" खाली है, "5555" - खाली, "6666" - 1 बैल ।
हम आगे जारी नहीं रखेंगे, क्योंकि 4 बैल पहले ही कुल जमा कर चुके हैं । यह वांछित संयोजन खोजने के लिए बनी हुई है। जब तक हम ता-दआम: "1226", "1262", "1226", "1262", "1622" प्राप्त नहीं करेंगे, तब तक हम क्रमचय उत्पन्न करेंगे। वह सब है।

जाहिर है, एल्गोरिथ्म बहुत अच्छा नहीं है, लेकिन यह स्पष्ट है और भ्रमित नहीं होना है। अनुमान लगाने के लिए अधिकतम चालों की संख्या 10 ("7890") + 24 क्रमपरिवर्तन है। 34 सबसे खराब स्थिति है। बेशक, हर संभव तरीके से खोज और क्रमपरिवर्तन को अनुकूलित करना संभव है, उदाहरण के लिए, दो छोरों से वैकल्पिक रूप से पुनरावृति - "1111", "0000", "2222", "9999" ... समान अंकों की उपस्थिति में क्रमपरिवर्तन की पीढ़ी को अनुकूलित करें (जैसा कि हमारे उदाहरण में, कई बार) वही बात पूछो)।
लेकिन हम ऐसा नहीं करेंगे। इस रणनीति को कंप्यूटर जटिलता का एक आसान स्तर होने दें।

मैं जोड़ों में बहुत बैठ गया और खुद के साथ खेला, किसी तरह के शांत एल्गोरिदम के साथ आने की कोशिश कर रहा था। लेकिन केवल एक विचार आया जिससे मैं एक भी रणनीति नहीं बना सका। उन्होंने साहित्य का अध्ययन करना शुरू किया। मुझे लेख मिला, "7 चालों में अनुमान लगाने" का। उन्होंने मुझे आकर्षित नहीं किया, क्योंकि बहुत सारे ब्रांचिंग हैं। लेकिन हमारे किरोव प्रोफेसर (लेकिन हमारे विश्वविद्यालय से नहीं) की किताब पढ़ने के बाद एस.एम. ओकुलोवा "एल्गोरिदम में प्रोग्रामिंग" , मुझे काफी सरल और काफी प्रभावी एल्गोरिदम का विवरण मिला। यह तथाकथित "छलनी विधि" का उपयोग करता है (एक उदाहरण प्रसिद्ध इस्ट्रॉफिन चलनी है - प्राइम नंबर खोजने की क्लासिक समस्या)। हम सभी संभावित नंबरों के एक निश्चित सेट पर विचार करते हैं और हर कदम उस सेट के सभी तत्वों को बाहर करते हैं जो ब्याज के नहीं हैं।

उदाहरण के लिए, अनुमानित संख्या 1234 के लिए, हमने 5678 मान लिया, और 0 बैल और 0 गायें मिलीं, क्या सोचा जाए - हम 5, 6, 7, 8 वाले सभी नंबरों को बाहर कर देते हैं। आप तुरंत पता लगा सकते हैं कि 10000 में से कितना लिया जाएगा। 10000 तत्वों के एक सेट से डरो मत। 5-6 चालों के लिए, केवल कुछ संख्याएँ बनी हुई हैं।

चलो डेटा संरचनाओं के साथ शुरू करते हैं। पास्कल कोड:

Const Pmax=10000; Type Post=string[4]; Var A:array[1..Pmax] of Post; // B:array[1..Pmax] of boolean; //  , 1 -  , 0 -  

प्रारंभ:

 t:=1; for i:=0 to 9 do for j:=0 to 9 do for k:=0 to 9 do for l:=0 to 9 do begin a[t]:=inttostr(i)+inttostr(j)+inttostr(k)+inttostr(l); //   inc(t); end; for i:=1 to pmax do b[i]:=true; //      

एक फ़ंक्शन जो चर के मान द्वारा एक सेट के एक तत्व के विश्लेषण को लागू करता है (bk, kr - बैल और केक)

 function pr(a,b:post;bk,kr:integer):boolean; //b -  , a-  ""  var i,x:integer; begin x:=0; for i:=1 to 4 do //    if a[i]=b[i] then inc(x); if x<>bk then begin pr:=false; exit; end; x:=0; for i:=1 to 4 do //    if (a[i]<>b[i]) and (pos(b[i],a)<>0) then inc(x); if x<kr then begin pr:=false; exit; end; pr:=true; end; 

इसलिए हमारी प्रत्येक चाल के बाद हम चलनी शुरू करते हैं

 for i:=1 to Pmax do if b[i] and not pr(a[i],hod,bk,kr) then b[i]:=false; 

अंत में, हम कह सकते हैं कि एल्गोरिथ्म मेमोरी-इंटेंसिव है और, मानक एल्गोरिदम की तुलना में, यह "लंबा" सोचेंगे, लेकिन यह कितना आसान और अधिक अनुकूलित है।
ठीक है, यह सब, यह बिल्कुल जटिल नहीं है। मेरा पहला लेख सख्ती से न्याय करना है।

जैसा कि वादा किया गया था, दूसरे साल से मेरे छोटे खेल का एक लिंक, ताकि खुद पर "छलनी" विधि महसूस हो सके:
बैल और गाय