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, 04: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 6 znakova, a određeni znak se može pojavljivati i više puta. Imate 6 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 6 pokušaja dovoljno da pogodimo svaku kombinaciju koju nam računar zada sa sigurnošću od 100%, odnosno da li postoji tačno odredjen postupak koji će nam omogućiti da u najviše 6 pokušaja dodjemo do zadate kombinacije, odnosno da li se igra zasniva na sreći ili ne? Ako 6 pokušaja nije dovoljno da li je dovoljno 7 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, 10:19

Donald Knuth je pokazao da je dovoljno 5 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 4,478 poteza, a da su npr. kasnije Koyama i Lai nasli algoritam koji u proseku zahteva 4,340 poteza. Skocko se zove Mastermind game na engleskom, te se na guglu moze naci i dosta vise informacija.
 
Postovi: 598
Zahvalio se: 15 puta
Pohvaljen: 565 puta


Povratak na ZANIMLJIVI ZADACI

Ko je OnLine

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


Index stranicaTimObriši sve kolačiće boarda
Danas je Subota, 07. Decembar 2019, 13:42 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs