Stranica 1 od 1

Skočko

PostPoslato: Petak, 29. Novembar 2019, 04:37
od Marko_555
Skočko je igra sa znakovima. Računar nasumično izabere kombinaciju od četiri znaka koju treba pogoditi. Znakovi se biraju iz skupa od [inlmath]6[/inlmath] znakova, a određeni znak se može pojavljivati i više puta. Imate [inlmath]6[/inlmath] pokušaja da pogodite kombinaciju, a nakon svakog pokušaja računar prikazuje koliko znakova ste pogodili i koliko od tih znakova je na pravoj poziciji.
Pitanje: Da li nam je [inlmath]6[/inlmath] pokušaja dovoljno da pogodimo svaku kombinaciju koju nam računar zada sa sigurnošću od [inlmath]100\%[/inlmath], odnosno da li postoji tačno odredjen postupak koji će nam omogućiti da u najviše [inlmath]6[/inlmath] pokušaja dodjemo do zadate kombinacije, odnosno da li se igra zasniva na sreći ili ne? Ako [inlmath]6[/inlmath] pokušaja nije dovoljno da li je dovoljno [inlmath]7[/inlmath] ili pak više?

Re: Skočko

PostPoslato: Petak, 29. Novembar 2019, 10:19
od Onomatopeja
Donald Knuth je pokazao da je dovoljno [inlmath]5[/inlmath] pokusaja (u najgorem slucaju) kako bi se nasla tacna kombinacija. Taj rad se moze pogledati ovde: http://www.cs.uni.edu/~wallingf/teachin ... ermind.pdf

Gledajuci gde je sve citiran ovaj rad, mogu se naci i brzi (prosecni) algoritmi. Moze se naci i podatak da Knuthov algoritam daje da je potrebno prosecno [inlmath]4,478[/inlmath] poteza, a da su npr. kasnije Koyama i Lai nasli algoritam koji u proseku zahteva [inlmath]4,340[/inlmath] poteza. Skocko se zove Mastermind game na engleskom, te se na guglu moze naci i dosta vise informacija.