Tauri și vaci Olympiad Plus. Dezvoltarea strategiei optime a jocului "Bulls și vaci" pe baza teoriei informațiilor. Uita-te la ce este "tauri și vaci" în alte dicționare
Tauri și vaci - joc logic Pentru doi jucători. Este suficient să aveți o bucată de hârtie și un mâner, timp liber și puțin noroc. De regulă, un astfel de timp este în școli și studenți. Dar pentru mine, slujitorul tău supus, nu sa întâmplat în anii mei să învețe această distracție. De ce nu-ți sparge substanța gri în timpul tău liber? Aceasta este o bună pregătire pentru mintea care nu necesită tensiune puternică și modul în care divertismentul este destul de justificat.
În versiunea sa clasică, regulile sunt foarte simple și nu sunt atrase. Două persoane se joacă, fiecare vine în secret de la adversar patru cifre fără repetări. De exemplu, acesta poate fi numărul 0834. Zero este, de asemenea, o cifră și poate fi bine în primul rând.
Mai mult, jucătorii se întorc fac mișcări, adică încercând să ghicească adversarul ascuns al adversarului. Dar trebuie, de asemenea, să ceară sub forma unui număr de patru cifre. De exemplu, vom întreba: "Numărul dvs. 3094?". Ca răspuns, trebuie să raportăm numărul de tauri și vaci. Taurul este o cifră care este în numărul nostru specificat și se află în aceeași poziție. Și vaca este o figură care este și în numărul nostru, dar nu este în locul lui. În cazul nostru, obținem două vaci, acestea sunt figurile 3 și 0, și un taur, este 4. Acum ne vom cere, și așa mai departe, până când cineva nu rezolvă pe deplin numărul. Aceasta este, în răspuns, el va primi patru tauri. Imaginea arată un exemplu al jocului. Timpul pentru un lot necesită destul de puțin. În practică, este de obicei necesară de la 5 la 8 mișcări, dar există unicume care gestionează și înfrânge trei lovituri. Desigur, există o parte considerabilă a norocului.
Pe site-ul nostru puteți juca "tauri și vaci" atât împotriva computerului, cât și online cu un adversar live. În partea de jos a camerei de joc pentru confortul dvs. există un chat de joc în care puteți alege un adversar pentru a juca în rețea sau puteți solicita Consiliului. Doar dacă aveți comentarii cu privire la implementarea jocului nostru, sugestii pentru îmbunătățirea sau dezvoltarea acestuia - apoi scrieți-ne. Puteți scrie atât pe forum, cât și pe corespondența noastră [E-mail protejat]site-ul web.
Soiuri de jocuri
Jocuri excelente:
- 1. După tipul de secvență de ghicire - poate fi un număr. În clasic, aceasta este o cifră de patru cifre fără repetări, constând din numere de la 0 la 9. Numărul de cifre poate crește, de asemenea, posibilitatea repetării acestora. Ca o secvență, culoarea, care este criptograma, poate fi folosit cuvântul.
- 2. După tipul de joc în sine. În epoca computerelor, este posibil să jucați una. Când o persoană ghicește numărul plantat de un computer sau împotriva computerului. Dar este dificil să câștigi mașina, există mai mult de problema algoritmului corect în el. Jucătorii joacă o opțiune clasică, dar sunt la o distanță considerabilă una de cealaltă. Jucătorii ghici numărul la rândul său, care a fost conceput de calculator - există opțiuni pentru așa-numitul scaun fierbinte, când adversarii sunt situați și se joacă cu un computer și de la distanță.
În prezent, este implementată numai versiunea clasică a jocului. Dacă aveți idei, ce fel de tauri și vaci ar trebui să apară pe site-ul nostru, apoi să le împărtășiți cu noi.
Adnotare: Jocul "Bulls și vaci" în această lecție, luarea în considerare a jocului anterior "Wake Up Number" continuă. Un algoritm binar de căutare care oferă o strategie optim de căutare a numărului dorit este discutată. Punerea în aplicare a acestei strategii este furnizată. Butonul "Computer, ghiciți numărul" apare în interfața de joc. Proiectul de implementare a proiectului joc nou "Bulls și vaci", unde trebuie, de asemenea, să ghiciți numărul plantat de computer. Găsiți numărul dorit în acest joc este mai dificil, deoarece este permis să pună întrebarea unui singur tip de "număr egal cu n?" Din motive tehnice, a fost înregistrată următoarea prelegere, unde a fost luată în considerare variația proiectului "tauri și vaci", în care combinația intenționată a fost aleasă aleatoriu din set, inclusiv 12 imagini. În textul care însoțește această lecție, este dată o scurtă descriere a acestui proiect.
Lecția începe cu analiza temelor efectuate de un școală. În temele dvs., a fost necesar să adăugați noi butoane la interfața de joc și să scrieți manipulatorilor de evenimente corespunzători în cod. Școala a adăugat două butoane "mai mari sau egale" și "mai puțin sau egale". A scris corect manipulatorilor de evenimente adecvați. Deși răspunsul la întrebare nu a fost format în mod corect, decizia propusă merită o bună evaluare. Inexactitățile de răspuns sunt ușor eliminate.
Când elevii, jucând jocul, au dat drumul unui computer planificat, de regulă, de regulă, a primit titlul de "maestru al jocului". Acest lucru a permis un nivel intuitiv pentru a înțelege esența unuia dintre algoritmii clasici de căutare de date într-un set comandat - un algoritm de dicotomie sau de căutare binară, de dragul studierii pe care acest joc a fost scris.
Care este esența jocului "Spuneți numărul"? Computerul crede numărul de la un interval. Limitele intervalului sunt comunicate jucătorului. Jucătorul are posibilitatea de a alege un număr de n din acest interval și de a seta un computer la o întrebare de trei tipuri: "Numărul n este mai conceput", "Numărul N este mai puțin decât planificat", "numărul n intenționat în mod egal. " Pentru fiecare întrebare, computerul răspunde la "da", dacă declarația este corectă și nu altfel. Pentru a deveni un joc master, trebuie să întrebați mai mult de întrebările K, unde K depinde de interval.
Strategia optimă Jocurile sunt determinate de algoritmul de căutare binar, numit și algoritmul de dihotomie sau metoda de divizare în jumătate. Luați în considerare mai detaliat.
Algoritmul căutării binare
Esența acestui algoritm va privi exemplul căutării numărului dorit într-un interval specificat. Care este incertitudinea inițială? Intervalul specificat este maxim - min + 1 număr. Deci, în interval este o sută un număr și numărul dorit poate fi oricare dintre ele. Deci, incertitudinea este egală cu numărul de numere din acest interval. Cum să puneți o întrebare, astfel încât să fie posibilă reducerea cât mai posibilă a incertitudinii. Mijlocul intervalului este numărul mediu (Max - min) / 2, în exemplul nostru - acesta este numărul 50. Prin specificarea întrebării "Numărul dorit este mai mult (mai puțin) MID", cu orice răspuns, incertitudinea este redus la jumătate. După ce a primit răspunsul "Da" la întrebarea "Conceput mai mult MID?" Valoarea limitei de jos a intervalului MIN se schimbă la mijlocul + 1. În caz contrar, limita superioară a max este schimbată la valoarea medie. Cu fiecare întrebare, intervalul se micșorează de două ori. Când intervalul este redus la un număr, problema egalității este garantată de un număr conceput. Numărul total de aspecte care ar trebui specificate în mod egal rotunjit în cea mai mare valoare a jurnalului de funcții (n) este un algoritm binar al N număr N, unde n este incertitudinea inițială, numărul de numere din interval.
Luați în considerare un exemplu. Numărul 83 din interval este conceput. Numărul optim de probleme care vă permit să ghiciți numărul planificat egal cu jurnalul 101, rotunjit la cel mai apropiat întreg, ceea ce dă numărul 7. Iată o secvență de 7 probleme, permițând ghicitul planificat:
- Numărul mai mult de 50? - Da.
- Numărul mai mult de 75? - Da.
- Numărul mai mult de 88? - Nu.
- Numărul mai mult de 81? - Da.
- Numărul mai mult de 84? - Nu.
- Numărul mai mult de 82? - Da.
- Numărul egal cu 83? - Da.
Algoritmul de căutare binară este utilizat pe scară largă într-o varietate de sarcini aplicate, - oriunde este necesar să găsească un element într-un set sortat, peste elementele care funcționează de comparație este definită pe "mai mare", "mai puțin".
Cum se joacă computerul?
Un computer, desigur, "știe" strategia optimă și, prin urmare, ajunge întotdeauna la titlul de "Master of Game" de orice nivel. Versiunea preferată a strategiei utilizează tipul "număr mai mult". Cu fiecare întrebare, intervalul de incertitudine este redus la jumătate până când conține exact un element, care este numărul dorit. Strategia de calculator este determinată de dezasamblarea prin metoda de căutare binară. Deci, manipulator al handlerului evenimentului Click "computer, ghiciți numărul" este implementarea algoritmului de căutare binar, suplimentat de ieșirea mesajelor corespunzătoare. Acesta este ceea ce arată codul de funcționare a evenimentului de clic:
///
Buna ziua.
În toamnă în al doilea an ca lucrări de laborator la "Teoria automată", profesorul în curs a venit cu sarcini americane, concentrându-se asupra dorințelor noastre în evaluare. Practic a fost jocuri. Cineva a primit hochei, cineva tenis, nu am fost atât de faimos joc logic "Bulls și vaci".
A fost necesar să realizăm cel puțin un comportament rezonabil al computerului în joc cu o persoană. Dar am continuat și după o lună, calculatorul în majoritatea cazurilor a fost ușor de jucat de colegii mei de clasă. Și pe subiect a fost obținut automat. Programul obține după descrierea algoritmilor.
Esența jocului
Jucătorul și computerul fac numere de patru cifre folosind numere de la 0 inainte de 9 . Jucătorii încearcă să rezolve numerele adversarului, trimițându-i posibilele opțiuni de numere, ca răspuns la obținerea a două numere - numărul "Bykov" și numărul "Vaci". Care sunt aceste numere?- Bulls sunt numerele corecte din locurile potrivite. Patru "Bull" - cheia victoriei, visul fiecărui agricultor.
- "Vaci" - numerele corecte din locurile greșite.
Sung unul 1622 . Dacă suntem presupuși 6112 , atunci ca răspuns va veni: 1 taur.(a patra cifră "2" în locul său), 2 vaci(Șase și unități nu sunt în locurile lor).
Operarea datelor "Skot" ale inamicului, trebuie să ghiciți numărul mai rapid.
Primul algoritm trivial, care întâlnește acest lucru, este de a rezolva seturile "1111", "2222", "3333" ... Atâta timp cât setul complet este primit și apoi generați mișcarea acestui set.
De exemplu, același număr este ghici 1622 , presupunem "1111"Avem răspuns "Taur", atunci "2222" - Avem deja răspuns 2 "bykov", "3333" - Goliți, "4444" - Goliți, "5555" - Goliți, "6666" - 1 taur..
Nu va mai continua mai departe, deoarece au marcat deja 4 tauri în sumă. Rămâne să găsești combinația dorită. Vom genera o permutare până când vom obține TA-DAAAM: "1226", "1262", "1226", "1262", "1622" . Tot.
Evident, algoritmul nu este foarte bun, dar ușor de înțeles și nu este confuz. Numărul maxim de mișcări de ghicire - 10 ("7890") + 24 de permutări. 34 - Acesta este cel mai rău caz. Desigur, este posibil ca bustul și permutarea în orice mod de a optimiza, de exemplu, căutat alternativ de la două capete - "1111", "0000", "2222", "9999" ... De asemenea, este de a optimiza generarea de permutări în prezența acelorași cifre (ca în exemplul nostru - punem același lucru de mai multe ori).
Dar să nu o facem. Lăsați această strategie să fie cu noi nivelul luminii Complexitatea computerului.
M-am așezat foarte mult pe pereche și m-am jucat cu mine însumi, încercând să vin cu un fel de algoritm rece. Dar a venit doar o singură idee de la care nu puteam compila o singură strategie. A început să studieze literatura. Am întâlnit articole, genul "ghicit pentru 7 mișcări". Nu m-au atras, pentru că acolo foarte Multe ramificare. Dar citirea cărții profesorului nostru Kirov (dar nu de la universitatea noastră) CM. Okulova "Programare în algoritmi", Am găsit o descriere a unui algoritm destul de simplu și destul de eficient. Folosește așa-numitul "Metoda unică" (Un exemplu este faimosul "Deceni Erasopena" - sarcina clasică de a găsi numere simple). Considerăm că setul final al tuturor numerelor posibile și fiecare mișcare exclude toate elementele stabilite, fără a reprezenta interesul.
De exemplu, pentru numărul mandatat 1234 Am sugerat 5678 și am primit 0 tauri și 0 vaciCe să gândiți - excludem toate numerele care conțin 5, 6, 7, 8 . Puteți estima imediat cât de mult este trecut 10000. Nu vă fie frică de multe dintre ele 10000 Elemente. Pe 5-6 Vor fi doar câteva numere.
Să începem cu structurile de date. Cod pe Pascal:
Const pmax \u003d 10.000; Tip postare \u003d șir; VAR A: Gama de post; // Majoritatea B: Array de Boolean; // Gama de steaguri, 1 - atât de potrivită, 0 - Excluse
Inițializare:
T: \u003d 1; Pentru i: \u003d 0 la 9 face pentru un j: \u003d 0 la 9 face pentru k: \u003d 0 la 9 face pentru l: \u003d 0 la 9 începe A [t]: \u003d INTTOSTR (I) + INTTOSTR (J) + INTTOSTR (k) + INTTOSTR (L); // formulați setul Inc (t); Sfârșit; Pentru i: \u003d 1 la Pmax do b [i]: \u003d adevărat; // Implicit toate numerele sunt potrivite
Funcția de implementare a unei analize a setului de seturi prin valori variabile (BK, KR - tauri și vaci)
Funcția PR (A, B: Post; BK, KR: Integer): Boolean; // B - accidentul nostru, A- elementul "testat" al setului Var I, X: Integer; Începeți x: \u003d 0; Pentru i: \u003d 1 până la 4 do // verificați tauri dacă a [i] \u003d b [i] apoi inc (x); dacă X.<>bK începe apoi PR: \u003d FALSE; Ieșire; Sfârșit; X: \u003d 0; Pentru i: \u003d 1 până la 4 face // verificați pentru vacile dacă (A [i]<>b [i]) și (PO (B [i], a)<>0) apoi Inc (x); Dacă X. Deci, după fiecare accident vascular cerebral, lansați sita Pentru i: \u003d 1 la Pmax face dacă b [i] și nu PR (A [I], HOD, BK, KR), atunci B [I]: \u003d FALSE; În concluzie, putem spune că algoritmul este cheltuit pe memorie și în comparație cu algoritmii standard se va gândi "mai mult", dar cât de ușor este complet optimizat. Buna ziua. Primul algoritm trivial, care întâlnește acest lucru, este de a rezolva seturile "1111", "2222", "3333" ... Atâta timp cât setul complet este primit și apoi generați mișcarea acestui set. M-am așezat foarte mult pe pereche și m-am jucat cu mine însumi, încercând să vin cu un fel de algoritm rece. Dar a venit doar o singură idee de la care nu puteam compila o singură strategie. A început să studieze literatura. Am întâlnit articole, genul "ghicit pentru 7 mișcări". Nu m-au atras, pentru că acolo foarte Multe ramificare. Dar citirea cărții profesorului nostru Kirov (dar nu de la universitatea noastră) CM. Okulova "Programare în algoritmi", Am găsit o descriere a unui algoritm destul de simplu și destul de eficient. Folosește așa-numitul "Metoda unică" (Un exemplu este faimosul "Deceni Erasopena" - sarcina clasică de a găsi numere simple). Considerăm că setul final al tuturor numerelor posibile și fiecare mișcare exclude toate elementele stabilite, fără a reprezenta interesul. Const pmax \u003d 10.000; Tip postare \u003d șir; VAR A: Gama de post; // Majoritatea B: Array de Boolean; // Gama de steaguri, 1 - atât de potrivită, 0 - Excluse Inițializare: T: \u003d 1; Pentru i: \u003d 0 la 9 face pentru un j: \u003d 0 la 9 face pentru k: \u003d 0 la 9 face pentru l: \u003d 0 la 9 începe A [t]: \u003d INTTOSTR (I) + INTTOSTR (J) + INTTOSTR (k) + INTTOSTR (L); // formulați setul Inc (t); Sfârșit; Pentru i: \u003d 1 la Pmax do b [i]: \u003d adevărat; // Implicit toate numerele sunt potrivite Funcția de implementare a unei analize a setului de seturi prin valori variabile (BK, KR - tauri și vaci) Funcția PR (A, B: Post; BK, KR: Integer): Boolean; // B - accidentul nostru, A- elementul "testat" al setului Var I, X: Integer; Începeți x: \u003d 0; Pentru i: \u003d 1 până la 4 do // verificați tauri dacă a [i] \u003d b [i] apoi inc (x); dacă X.<>bK începe apoi PR: \u003d FALSE; Ieșire; Sfârșit; X: \u003d 0; Pentru i: \u003d 1 până la 4 face // verificați pentru vacile dacă (A [i]<>b [i]) și (PO (B [i], a)<>0) apoi Inc (x); Dacă X. Deci, după fiecare accident vascular cerebral, lansați sita Pentru i: \u003d 1 la Pmax face dacă b [i] și nu PR (A [I], HOD, BK, KR), atunci B [I]: \u003d FALSE; În concluzie, putem spune că algoritmul este cheltuit pe memorie și în comparație cu algoritmii standard se va gândi "mai mult", dar cât de ușor este complet optimizat. Când am intrat în institut, jocul "tauri și vaci" a fost foarte popular. Așa că a coincis că, în același timp, am citit jurnalul no romanul matematic al lui Alfred Reni. - notele studenților cu privire la teoria informațiilor. " Datorită acestui articol, m-am întâlnit. Și am avut ideea de a-mi îmbunătăți performanța în "tauri și vaci", bazându-se pe noi cunoștințe. Reamintim pe scurt regulile.Două jocuri. Toată lumea crede și înregistrează un număr secret de 4 cifre, cu numere care nu repetă (primul poate fi zero). Un jucător care începe jocul prin lot, face o încercare de a ghici numărul. O încercare este un număr de 4 cifre, cu numere care nu rafină, raportate de inamic sub forma unei întrebări. Inamicul vorbește ca răspuns, câte cifre sunt ghicit cu coincidența pozițiilor lor în numărul secret și cât de mult este ghici fără coincidență. De exemplu: numărul secret 3219 este conceput; Încercare (întrebare) 2310; Rezultatul (răspunsul): un "taur" (figura 1 din întrebarea intră în numărul secret și este în locul său) și două "vaci" (figurile 2 și 3 din întrebare sunt incluse în numărul secret, dar nu sunt la loc). Răspunsul este raportat sub forma unui număr de 2 cifre. În exemplul nostru, răspunsul este de 12 (un "taur", două "vaci"). Jucătorii fac încercări la rândul lor. Cel care primește mai întâi răspunsul la întrebarea 40. Descărcați o notă în format sau, exemple în format, un exemplu în format ZIP (într-un fișier Excel cu 57mV). Acestea sunt ideile teoriei informațiilor mi-au fost utile pentru a îmbunătăți indicatorii din joc (a se vedea): Pentru o mai bună înțelegere a materialului, este de asemenea util să deschideți un fișier Excel. 1. Numărul secret poate fi rafinat 10 * 9 * 8 * 7 \u003d 5040 (În primul rând poate exista oricare dintre cele 10 cifre, pe al doilea - oricare dintre cele 9 rămase etc.). Pentru a forma o serie de numere admise, am folosit algoritmi simpli în Excelență (vezi "subc1" și "subg."). Deoarece probabilitatea de a fi concepută de oricare dintre numerele 5040 este aceeași, incertitudinea (H) este calculată utilizând Formula Hartley: H \u003d log 2 N. Înainte de începerea jocului, incertitudinea este log 2 5040 \u003d 12.30 biți de informație. 2. Este clar că prima întrebare poate fi, de exemplu, 0123. 14 răspunsuri sunt posibile pe aceasta (a se vedea și lista "Întrebare1" a fișierelor Excel): Aici: P Este probabilitatea unui răspuns, n este incertitudinea care rămâne după răspunsul corespunzător, H este cantitatea de informații obținute dacă a fost implementat unul sau altul. Cel mai probabil răspuns este 01, ceea ce înseamnă că doar o singură cifră este printre întrebarea într-un număr secret și nu este în locul său. Răspunsul 01 implică faptul că unul dintre numerele 1440 ar putea fi conceput, adică incertitudinea rămasă după acest răspuns este log 2 1440 \u003d 10,49 biți, iar informațiile obținute cu un astfel de răspuns sunt 12.30 - 10.49 \u003d 1.81 biți. Răspunsul 40 oferă 12.30 de informații și incertitudinea după aceasta nu rămâne j. Deoarece probabilitățile de răspunsuri sunt diferite, cantitatea de informații conținute în chestiune este determinată de formula Shannon: H (X) \u003d P 1 2 (1 / P 1) + P 2 Log 2 (1 / P 2) + ... + P n Log 2 (1 / p N). Prima întrebare aduce 2,77 biți de informații. 3. Când alegeți o a doua întrebare, trebuie respectate trei idei formulate mai sus. În practică, aceasta înseamnă că Întrebarea trebuie să i se permită să răspundă la 40. Regula de formare a celei de-a doua întrebări.Lăsați prima întrebare (0123) am primit un răspuns 01. Pentru a doua întrebare, luați o cifră din prima întrebare, puneți-o într-un loc nou și adăugați trei numere noi. Obținem, de exemplu, 4561. Dacă a fost obținută o întrebare 1, de exemplu, un răspuns 11, trebuie să luați două numere din prima întrebare, unul să plecați în locul meu, al doilea pentru a pune un loc nou și Adăugați două numere noi; De exemplu, 0435. La întrebarea 2.4561 14 răspunsuri sunt, de asemenea, posibile (a se vedea lista "Întrebare 2"): Am selectat a doua întrebare adus 2,86 biți de informații. Să vedem cât de multe informații vor oferi alte întrebări. În aceste scopuri, am creat un fișier separat "A doua întrebare non-optimă.XLSX" (el "cântărește" 58mV, deci aveți grijă de ea :)). A doua întrebare poate fi una din cele 5040 de numere posibile (inclusiv repetarea primei întrebări). Ca urmare a acestui studiu, am primit suma informațiilor pe care le oferă aceste sau alte probleme (îți amintesc că analiza se face presupune că prima întrebare 0123 a dat răspunsul 01). De exemplu, întrebarea 2 - 0123 oferă biți zero de informații, deoarece este doar un răspuns 01, a (pentru n \u003d 1) log 2 1 \u003d 0. Întrebarea 2 0132 oferă 0,65 biți de informații, întrebarea 2 0148 - 2.53 biți de informații. Cantitatea maximă de informații oferă 1440 de aspecte a doua formate din regula descrisă mai sus. Rezultatele studiului pe care l-am transferat la lista "Diferite întrebări2" fișier "bull-cow.xlsx" și apoi voi vorbi doar despre acest fișier. Așa cum am spus, cantitatea maximă de informații este de 2.859 - va fi obținută pentru o întrebare 2, pregătită după cum urmează: Trebuie să luați o cifră din prima întrebare, puneți-o într-un loc nou și adăugați trei numere noi: Se poate observa că alte 180 de întrebări oferă aproape aceleași informații - 2.774 de biți. O astfel de număr de informații vor fi obținute la răspunsul, de exemplu, la o întrebare 1045 (vezi foaia de "chestiune a punctului"). Dar această întrebare nu poate da un răspuns 40! Adică întrebarea este pregătită cu o încălcare a regulii formulate. Cât de mare este diferența de informație între 2,859 și 2,774 biți!? La prima vedere, nu arată mare. Pe de altă parte, cu cel mai nefavorabil răspuns la întrebarea 2.4561 (01), vor exista 378 de opțiuni pentru numărul secret și cu cel mai nefavorabil răspuns la întrebarea 2.045 (de asemenea, 01) - 408 de opțiuni. Cu 8% mai mult! Acesta este prețul unei întrebări ne-optime. 4. În pregătirea celei de-a treia (și ulterioare), urmăresc următoarea regulă mnemonică. Este necesar să se facă o masă agregată a tuturor numerelor secrete posibile care satisfac răspunsurile la întrebările anterioare. După aceea, pentru a forma o întrebare3, folosind partea din acest tabel, care conține mai multe opțiuni (evaluarea apare "pe ochi"). Un pic confuz? Să luăm în considerare două exemple. Exemplu1. Prima opțiune: o unitate include, apoi nu este inclusă, nici 023, nici 456; Adică sunt incluse, nu sunt folosite în primele două întrebări, numere - 789. Obținem un set de numere de numărul secret 1789 (ordinea locației lor, satisfacerea răspunsurilor la primele două întrebări). Opțiuni care îndeplinesc acest set, 12. A doua opțiune: Unitatea nu este inclusă, apoi o cifră este printre 023, una din 456 și două de la 789. I-am scris astfel: Numărul estimat de opțiuni setate de cifre este de 3 (unul din 023) * 3 (unul din 456) * 3 (două din 789) \u003d 27. Și luând în considerare locațiile numerelor variantelor sunt semnificativ mai mari de 100. Pentru Întrebarea 3 Luăm o singură cifră din 023, una din 456, două din 789. Avem cifre, astfel încât să nu existe coincidențe de locații de locație cu o întrebare1 și o întrebare2. Mai mult, avem cifre care s-au întâlnit anterior (4 și 2) în locuri complet noi, adică la al 2-lea sau al patrulea. De exemplu, întrebarea 3 7482 este mai bună decât 2784. Deoarece în primul caz, al IV-lea și 2-KA se află pe teren, care în cauză1 și întrebarea 2 nu au ocupat. În același timp, în întrebarea 3.2784, numărul 2 se află în locul 4-ki de la întrebarea2 (vezi foaia "Întrebare3"). Răspunsul la întrebarea 3 4782 conține 2,958 biți de informații, iar răspunsul la întrebarea 3 2784 - "numai" 2,955. Exemplu2. Primele două întrebări și răspunsuri au fost după cum urmează: Prima opțiune: inclusă 13, apoi nu este inclusă, nici 02, nici 45 și din numerele rămase sunt două: Numărul de numere secrete din realizarea1 - 48. A doua opțiune: o cifră este una dintre 13, apoi una include una din 02, una din 45 și una din 6789: Numărul aproximativ al numerelor secrete din realizarea 2 este mai mare de 100. A treia opțiune: Nu includeți 13, apoi compus din 02 și 45: 0245. Numărul de numere secrete din exemplul de realizare 3 - 8. 5. Când numerele secrete rămân puțin (de la 4 la 10 ... 20), mă întorc la căutarea completă a tuturor opțiunilor posibile. Jucați cu un algoritm bazat pe teoria informațiilor și câștigați! Zeplem Kenezhebekov a scris un program care vă permite să jucați cu un computer. Programul funcționează în Windows 7, 8, 8.1 cu cadru 4.5 instalat. Mi-a plăcut foarte mult jocul, dar algoritmul este în mod clar îndepărtat de cea optimă. Am jucat de trei ori și am câștigat totul de trei ori. Descărcați programul în format. http://slovesnov.narod.ru/articles/bullcow.pdf. . Pentru a spune adevărul, nu puteam stăpâni 🙂 dar menționează teoria informațiilor când nu am găsit-o în ea ...
Ei bine, asta-i tot, nu este deloc dificil. Primul meu articol, judecă strict.
În toamnă în al doilea an ca lucrări de laborator la "Teoria automată", profesorul în curs a venit cu sarcini americane, concentrându-se asupra dorințelor noastre în evaluare. Practic a fost jocuri. Cineva a primit hochei, cineva tenis, nu am fost atât de faimos joc logic "Bulls și vaci".
A fost necesar să realizăm cel puțin un comportament rezonabil al computerului în joc cu o persoană. Dar am continuat și după o lună, calculatorul în majoritatea cazurilor a fost ușor de jucat de colegii mei de clasă. Și pe subiect a fost obținut automat. Programul obține după descrierea algoritmilor.Esența jocului
Jucătorul și computerul fac numere de patru cifre folosind numere de la 0
inainte de 9
. Jucătorii încearcă să rezolve numerele adversarului, trimițându-i posibilele opțiuni de numere, ca răspuns la obținerea a două numere - numărul "Bykov" și numărul "Vaci". Care sunt aceste numere?
Pentru înțelegere, voi da un exemplu: Sung unul 1622
. Dacă suntem presupuși 6112
, atunci ca răspuns va veni: 1 taur.(a patra cifră "2" în locul său), 2 vaci(Șase și unități nu sunt în locurile lor).
Operarea datelor "Skot" ale inamicului, trebuie să ghiciți numărul mai rapid. De exemplu, același număr este ghici 1622
, presupunem "1111"Avem răspuns "Taur", atunci "2222" - Avem deja răspuns 2 "bykov", "3333" - Goliți, "4444" - Goliți, "5555" - Goliți, "6666" - 1 taur..
Nu va mai continua mai departe, deoarece au marcat deja 4 tauri în sumă. Rămâne să găsești combinația dorită. Vom genera o permutare până când vom obține TA-DAAAM: "1226", "1262", "1226", "1262", "1622"
. Tot.
Evident, algoritmul nu este foarte bun, dar ușor de înțeles și nu este confuz. Numărul maxim de mișcări de ghicire - 10 ("7890") + 24 de permutări. 34
- Acesta este cel mai rău caz. Desigur, este posibil ca bustul și permutarea în orice mod de a optimiza, de exemplu, căutat alternativ de la două capete - "1111", "0000", "2222", "9999" ... De asemenea, este de a optimiza generarea de permutări în prezența acelorași cifre (ca în exemplul nostru - punem același lucru de mai multe ori).
Dar să nu o facem. Lăsați această strategie să fie cu un nivel ușor de complexitate a computerului. De exemplu, pentru numărul mandatat 1234
Am sugerat 5678
și am primit 0 tauri și 0 vaciCe să gândiți - excludem toate numerele care conțin 5, 6, 7, 8
. Puteți estima imediat cât de mult este trecut 10000.
Nu vă fie frică de multe dintre ele 10000
Elemente. Pe 5-6
Vor fi doar câteva numere.
Să începem cu structurile de date. Cod pe Pascal:
Ei bine, asta-i tot, nu este deloc dificil. Primul meu articol, judecă strict.Răspuns
Numărul de răspunsuri
r.
H.
h.
00
360
7,1%
8,49
3,81
01
1440
28,6%
10,49
1,81
02
1260
25,0%
10,30
2,00
03
264
5,2%
8,04
4,25
04
9
0,2%
3,17
9,13
10
480
9,5%
8,91
3,39
11
720
14,3%
9,49
2,81
12
216
4,3%
7,75
4,54
13
8
0,2%
3,00
9,30
20
180
3,6%
7,49
4,81
21
72
1,4%
6,17
6,13
22
6
0,1%
2,58
9,71
30
24
0,5%
4,58
7,71
40
1
0,02%
0,00
12,30
5040
100,0%
12,30
2,77
Răspuns
Numărul de răspunsuri
r.
H.
h.
00
54
3,8%
5,75
4,74
01
378
26,3%
8,56
1,93
02
369
25,6%
8,53
1,96
03
91
6,3%
6,51
3,98
04
6
0,4%
2,58
7,91
10
126
8,8%
6,98
3,51
11
222
15,4%
7,79
2,70
12
83
5,8%
6,38
4,12
13
6
0,4%
2,58
7,91
20
57
4,0%
5,83
4,66
21
31
2,2%
4,95
5,54
22
5
0,3%
2,32
8,17
30
11
0,8%
3,46
7,03
40
1
0,07%
0,00
10,49
1440
100,0%
10,49
2,86
Informații din întrebare2, biți
Numărul de astfel de probleme
0,000
1
0,650
6
0,811
8
0,918
9
1,899
24
2,104
72
2,258
144
2,268
72
2,365
216
2,372
48
2,530
180
2,624
360
2,664
720
2,756
360
2,766
480
2,767
720
2,774
180
2,859
1440
TOTAL
5040
Intrebarea 1
0123
Raspunsul 1
01
Intrebarea 2.
4561
Răspuns2.
01
Intrebarea 1
0123
Raspunsul 1
02
Intrebarea 2.
3541
Răspuns2.
02