Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica RAZNO ZANIMLJIVI ZADACI

Skočko

Skočko

Postod Marko_555 » Petak, 29. Novembar 2019, 05:37

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?
 
Postovi: 1
Zahvalio se: 0 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Skočko

Postod Onomatopeja » Petak, 29. Novembar 2019, 11:19

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.
 
Postovi: 608
Zahvalio se: 15 puta
Pohvaljen: 580 puta


Povratak na ZANIMLJIVI ZADACI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 3 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Ponedeljak, 01. Jun 2020, 15:48 • Sva vremena su u UTC + 1 sat [ DST ]
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs