Tauri și vaci 1987 boom-ul e

Tauri și vaci

Jucat de doi. Fiecare zămislește număr de patru cifre cu diferite cifre, care trebuie să ghicească partener (în primul rând și poate fi 0). Cursul este că ghicitor numește un anumit număr, și un patru numere diferite. În cazul în care numerele concepute și numite sunt totale cifre care stau în aceleași locuri, o situație cunoscută sub numele de „taur“ (denumit în continuare „b“). În cazul în care cifrele globale, dar ele sunt în locații diferite, este „Vaca“ (notată cu „o“).

Ca răspuns la progresul partenerului zagadchik compară numărul acestora cu numele și raportează numărul total de „tauri“ și „vaci“. De exemplu, dacă conceput 5239 și numit 2735, răspunsul va fi „un bou 2 vaci (2 * 16). Figura 3 există în ambele figuri și este în aceleași locuri (16), figurile 2 și 5, comune, dar sunt în locații diferite (2k), numerele 7 și 9 nu sunt comune.

Fă o mutare și a obține un răspuns, prezicător extrage câteva informații despre cele concepute și în cele din urmă îl definește. Jocul se termină în momentul în care următorul curs de răspunsul său el devine 46, adică, numărul de planuri găsit. Jucătorul care ghicește numărul adversarului mai repede.

Aici este un exemplu. Mișcările și răspunsurile lor vor fi scrise în tabel. 1.

Să presupunem că partenerul a conceput un număr de 3594, pe care trebuie să ghicească. Primul nostru curs de 1568 a dat un răspuns 16. Acest lucru înseamnă că, în cele concepute există doar o cifră din cele de mai sus, și în picioare în locul lui. Vom încerca să-l ghicească fără să atragă încă - pentru a evita confuzia - celelalte figuri. Asigurați-un al doilea ciclu de 1586. A 16 se spune că în locul său există un număr 1 sau 5. Acum vine al treilea curs de 1658, iar răspunsul 1k arată. care cred că dintr-un număr de pe al doilea rând este de 5, iar numerele 1, 6, 8, nu este. Progresul în 2570 va încerca să afle disponibilitatea numerelor 2, 7 și 16 0. Răspunsul este foarte mare succes - aceste cifre în numărul necesar nu este. Deci, este clar că planul său este numărul de numere de 3, 4, 5, 9, iar pe locul doi - 5. Faceți următoarea cursul 4539. A 16 3k înseamnă că conceput unul dintre numerele - 3594 sau 9543. Dacă prima cifră 3, apoi 9 poate fi doar al treilea, iar în cazul în care primele 9, apoi 3 - doar a patra. Curs de 3594 și 46 de răspuns ne-a condus la obiectivul; 16 3k răspuns ar însemna că numărul planificat de 9543, caz în care partidul va dura mai mult pe curs.

În exemplul prezentat în Fig. 1 ksbzh ales cifru. Prima dată a fost în timpul zchszh un meci plin (x) și o culoare (e) nu a fost în locul ei. Astfel, răspunsul CU (vechiul 16 1k). Al doilea răspuns curs chbb. al treilea - bbchch (identificat toate cele patru culori), a patra - chchchch. Jocul este de peste. Petrecerea a durat patru mutări. În general, așa cum am văzut, placa este proiectat pentru zece mișcări - (numai jucători foarte neexperimentați nu se încadrează în acest cadru).

Deși descrierea ocupă mult spațiu, de fapt, răspunsul este formulat în câteva secunde.

Deci, în „tauri și vaci“ are 5040 de numere diferite, care pot fi și să crezi că poți merge pe jos. Și cât de multe răspunsuri diferite? Toate acestea sunt enumerate în a doua coloană a tabelului. 2, 14 lor (evident răspuns imposibil 1K 36). O linie orizontală într-un tabel împărțit cazurile în care se găsesc toate cele patru cifre, trei cifre, doi, unu și nici unul. A treia coloană arată numărul de numere care pot oferi un răspuns adecvat la prima mutare. Răspunsul cel mai plăcut, desigur, 46 se termină imediat jocul. După cum putem vedea, cea mai mare varietate de numere posibile este la 1K de răspuns - 1440.

Desigur, rezultatul jocului, adică, numărul de mișcări pentru care să ghicească numărul de planuri, într-o anumită măsură, depinde de caz. Dar o mulțime este determinată, și arta de joc. Acest fapt ridică întrebarea: ce se înțelege prin abilitatea de joc în „tauri și vaci“? La urma urmei, chiar și un jucător novice are prima mutare poate fi de a ghici în mod aleatoriu se gândească la un număr, dar încă nu vorbește despre capacitatea lui.

Să presupunem că A și B jucători a jucat un meci din cele trei partide. Un jucător în toate cele trei jocuri de ghicit numărul de partener pentru 5 ture. Jucătorul B în două loturi a ghicit numărul 4 accident vascular cerebral, si intr-unul din 9. Cine joacă mai bine? Jucătorul B a câștigat meciul cu scorul de 2: 1, dar că numărul total de accidente vasculare cerebrale el are mai mult. În cazul în care, de exemplu, în victoria șah sine este importantă, viteza indiferent de durata de partid, de „tauri și vaci“ doar ghicitul, numărul de accidente vasculare cerebrale, de fapt petrecut și de a face rezultatul jocului.

Cele două abordare mai interesantă pentru a evalua puterea de joc în „tauri și vaci“. Este notat cu Li. numărul de accidente vasculare cerebrale, pentru care jucătorul ghicește un număr la numărul I (i se execută 1-5040). Introducem două caracteristici ale jocului său de putere „tauri și vaci“:

Jocul Oamenii întotdeauna ușor de a afla cine este mai puternic. Un alt lucru, atunci când vine vorba de calculatoare. Pentru orice joc de strategie formulată sub forma unui algoritm, este posibil să se calculeze numărul de Lave și Lmax, și, prin urmare, în funcție de criteriul pentru a determina care program de calculator mai puternic.

Este demn de remarcat faptul că jocurile în cauză sunt un obiect foarte interesant pentru cercetarea pe calculator. Este suficient să spunem că, în scris, un program pentru „tauri și vaci“ a fost unul dintre cele mai mari din lume, specialist în domeniul programării americane D. Knuth. În țara noastră, un număr de rezultate în acest domeniu a fost primit un grup de studenți ai Departamentului de Cibernetică MISA condusă de profesor asociat M. Gendler.

Pentru „tauri și vaci“ în urmă cu câțiva ani de către elevi a strategiei MISA a fost dezvoltat, care asigură ghicitul orice număr de șapte accidente vasculare cerebrale, și sa constatat că Lmax ≥6. Dar pentru a închide granițele nu au putut gestiona. Doar recent, cu ajutorul unui raționament combinatorică foarte ingenioasă și utilizarea subtilă a capacităților mașinii, ei au stabilit ca Lmax = 7. Cu alte cuvinte, jocul este construit un algoritm în „tauri și vaci“, care permite de a găsi orice număr necunoscut șapte accidente vasculare cerebrale, și a demonstrat că cele șase căi strategie nu există.

De altfel, în exemplul de mai sus, la începutul planului său a fost să ghicească numărul este de șapte accidente vasculare cerebrale (deși exemplul purtat academic în natură și nu sunt destinate să joace optim).

Să luăm acum în considerare mai multe părți (mai corect să spunem, folosind terminologia de șah - finaluri sau schițe), reprezentate sub formă de sarcini. După ce le-a examinat, veți obține o bună ilustrare a subtilitățile jocului în „tauri și vaci“. Toate situațiile vor fi examinate în cazul în care răspunsul la inamic primul nostru curs - pentru a determina numărul 1234 - pentru a coincide cu una dintre primele cinci din tabel. 2. Dacă răspundeți 46 de partid durează doar un singur rândul său, și pentru fiecare dintre celelalte patru cazuri, vom da drumul la joc, care garantează guessing conceput pentru cel puțin suma de mișcări. Cu alte cuvinte, mai multe mișcări noi ghici cu exactitate numărul de inamic, oricare ar fi ea, dar cu un număr mai mic, nu putem fi întotdeauna norocos - codul nu vor fi divulgate.

Parte 1. La prima mutare în 1234 adversarul a răspuns 2b 2k. Care este cel mai mic număr de mutări garantate guessing conceput?

Este ușor de văzut că doar șase numere concepute ca răspuns la un prim curs de 1234 poate răspunde la 2k 2b (Tabelul. 3, prima coloană), precum și la orice al doilea rând de cel puțin trei dintre ele va da același răspuns.

Al doilea curs al jocului 1356 (în loc de figurile 5 și 6 pot fi luate și altele, diferit de 1, 2, 3, 4). Toate răspunsurile posibile sunt în a doua coloană a tabelului. Răspuns 2b determină în mod direct numărul de planuri - în 1324 (ca răspuns la o serie de alte), 1b 1k răspuns lasă două opțiuni, iar răspunsul 2k - trei. Al treilea curs de 3256 (luând în considerare a doua) o face foarte clar - toate cele cinci numere dau diferite candidați câteva răspunsuri. O liniuță în tabel. 3 (și toate tabelele următoare) înseamnă că un curs adecvat de „reacție“ la un anumit număr de noi nu le pasă cu adevărat. Astfel, al patrulea curs este garantat 4b răspuns și partea care nu durează mai mult de patru mutări.

O greșeală tipică și destul de evident că mulți dintre cei care realizează acest lucru este prin utilizarea numerelor pentru jocuri care conțin numai cifrele 1, 2, 3, 4. Logica este simpla - odată ce toate cifrele sunt cunoscute, atunci de ce să se conecteze nou? Cu toate acestea, această abordare concepută pentru a garanta numărul determinat la a cincea de viteză (răspuns 4b).

Partidul 2. Aceeași întrebare ca și în primul joc, dar răspunsul la prima mutare 1b 3k.

La prima mutare în 1234 opt numere poate da un răspuns la 1b 3k (tab. 4). În orice secundă, în timpul cel puțin unul din cele patru

Numerele dau același răspuns, și pentru a clarifica situația, nevoie de mai mult de două progrese. În al doilea rând de 1256 sunt împărțite în două grupe; pentru primul grup de numere (răspuns 1b 1K) a făcut al treilea curs de 1563 și pentru numărul de al doilea grup (răspunsul 2k) - Accident vascular cerebral 2564. După faptul că există două perechi de numere din fiecare grup care necesită un alt accident vascular cerebral, și un sfert curs de 1,564 clarifica pe deplin imaginea. Astfel, a doua parte nu durează mai mult de cinci pasaje.

Partidul 3. Aceeași întrebare ca și în cele două jocuri, dar răspunsul la primul curs de 4K.

Ca răspuns la un prim curs de 1234 nouă numere poate da un răspuns la 4K (tab. 5). Al doilea curs de 3102 decriptează cele două numere, iar cele șapte rămase se divide în două grupe, una dintre care decide accident vascular cerebral 4153, iar celălalt - 2456. Cea de a patra cursa completeaza partea (4b va fi primit răspuns).

Partidul 4. Aceeași întrebare ca și în cele trei jocuri, dar răspunsul la prima mutare 3b.

răspuns 3b la un prim curs de 1234 dă numărul 24. Într-adevăr, cele trei cifre pot fi fixate în loc în patru moduri, ca a patra, există șase posibilități: O, 5, 6, 7, 8, 9, pentru un total de 4 * 6 = 24 opțiune. Este curios să constatați că numărul de planuri între cele 24 de numere din expediere nu pentru același număr de accidente vasculare cerebrale, câte opt numere în al doilea joc.

Luați în considerare masa. 6a. În primele patru linii și reprezintă oricare dintre cifre 8, 9, 0. Astfel, reprezentată aici de toate cele 24 de posibilități. Asigurați-un al doilea ciclu de 1567. A pe Frunze de stejar, alegerea a trei numere nerezolvate pentru care bun treia rândul său, 8934 (tab. 6 b). Ca răspuns 26 poate juca 1506 (Tabelul 6.), Și când răspunsul 1K - 5634 (. Tabelul 6 g).

Timp de nouă numere cu un răspuns în tabelul 16. 6 și formează masa. 6 g (din nou, și poate lua una dintre următoarele trei valori - 8, 9, 0). Al treilea curs de 3564 le împarte în trei grupe egale, al patrulea număr de curs sunt identificate, iar al cincilea progresul joc complet (4b răspuns). Mai avem șase numere aranjate în rândurile de jos din tabelul. 6 a, scrie-le separat (tab. 6 e). Și această șase nu înțelege doi timpi suplimentare. Deci, încă o dată partidul nu durează mai mult de cinci accidente vasculare cerebrale.

Rezultatele tuturor părților de mai sus sunt rezumate în tabelul. 7. O dovadă riguroasă a faptului că, în fiecare caz, mai puține accidente vasculare cerebrale nu, vom omite.

Exemplele arată că un dezmembrate inteligent joc de „tauri și vaci“ necesită un calcul matematic delicat.