Sudionik ste TV kviza i u završnoj igri morate odabrati omotnicu s novčanom vrijednošću. Voditelj će vam nuditi jednu po jednu omotnicu. Ako je novčana vrijednost omotnice dotad najveća, on će vam to dodatno naglasiti. Vi možete prihvatiti trenutnu omotnicu i otići kući s njenim sadržajem ili reći voditelju da ponudi iduću omotnicu. Znate ukupni broj omotnica, no ne znate koliko novaca one sadrže. Koju omotnicu ćete odabrati?
Naveo sam vam primjer problema optimalnog zaustavljanja. On opisuje situaciju kada u određenom broju koraka trebate nešto odabrati i pritom želite izvući maksimum. Kada pređete na idući korak, nema povratka na prethodni. Također, ne znate unaprijed što vas čeka u budućim koracima.
Recimo da tražite zaposlenika. Odrađujete jedan po jedan razgovor i nakon svakoga kandidatu kažete je li primljen ili odbijen. Idealno bi bilo sa svima obaviti razgovor i tek onda odabrati zaposlenika. Nažalost, ovdje to ne možemo napraviti. U jednom trenutku trebamo odabrati i nadati se da smo odabrali najboljeg. Slične situacije traženje su životnog partnera, kupnja stana ili kuće i sl.
Vratimo se na uvodni primjer TV kviza i odabira omotnice. Napravit ćemo simulaciju pomoću micro:bita. Imamo 25 LED-ica i neka svaka od njih bude po jedna omotnica. Svakoj LED-ici/omotnici nasumično ćemo pridružiti jedan od brojeva u intervalu [1, 25]. Klikom na gumb A reći ćemo voditelju da ponudi iduću omotnicu, a klikom na gumb B odabrat ćemo trenutnu omotnicu (prikazat će se njena vrijednost). Ako je vrijednost trenutne LED-ice dotad najveća, ona će blinkati. Naravno, cilj nam je odabrati LED-icu s brojem 25 ili barem što veću vrijednost. Slijedi kod simulacije napisan u TypeScriptu, s detaljnim komentarima:
Ovo je naše rješenje koje nije ujedno i jedino zato izazivamo Vas da pokušate. Šaljite nam svoje radove kako bi ih mogli usporediti i zajedno pronaći bolji optimum 😉 Postoji strategija pomoću koje imate najveću vjerojatnost izvući maksimum. Probajte ju sami otkriti pomoću ovog programa. Ovdje ju neću otkriti da ne pokvarim vaše simuliranje.
// Svakom pikselu pridružit ćemo jedan od brojeva iz polja rang. // Piksela je 25 pa tako imamo brojeve od 1 do 25. let rang = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25 ] // Kroz ovo polje ćemo napraviti pridruživanje. let rang_piksela: number[] = [] // To ćemo napraviti na ovaj način: // Sve dok ne ispraznimo rang, nasumično uzimamo iz njega brojeve // i redom ih slažemo u rang_spoja. Redno mjesto podatka odgovara // pikselu na način da se krećemo kroz retke pa kroz stupce. while (rang.length > 0) { rang_piksela.push(rang.removeAt(Math.random(rang.length))) } // Krećemo s prvim pikselom. let trenutni_piksel = 0 // Upalit ćemo ga pomoću spritea iz skupine naredbi game. let prikaz_trenutnog_piksela: game.LedSprite = game.createSprite(0, 0) // Prvi piksel dosad ima najveću vrijednost. Prvi je, logično. :) let maksimalni_rang_dosad = rang_piksela[trenutni_piksel] // Budući da je najveći dosad, stavit ćemo da blinka. prikaz_trenutnog_piksela.setBlink(250) // Na pritisak tipke A: input.onButtonPressed(Button.A, () => { // Pređi na idući piksel. trenutni_piksel += 1 // Ako je prethodni bio zadnji: if (trenutni_piksel == 25) { // Vrati se na njega. trenutni_piksel = 24 } // Prikaži trenutnog piksela. prikaz_trenutnog_piksela.goTo(trenutni_piksel % 5, trenutni_piksel / 5) // Ako mu je vrijednost najveća dosad: if (rang_piksela[trenutni_piksel] > maksimalni_rang_dosad) { // Ažuriraj najveću vrijednost dosad. maksimalni_rang_dosad = rang_piksela[trenutni_piksel] // Neka piksel blinka. prikaz_trenutnog_piksela.setBlink(250) // A ako mu je vrijednos manja od najveće dosad: } else { // Neka piksel ne blinka. prikaz_trenutnog_piksela.setBlink(0) } }) // Na pritisak tipke B: input.onButtonPressed(Button.B, () => { // Očisti sadržaj ekrana. basic.clearScreen() // Prikaži vrijednost trenutnog piksela. basic.showNumber(rang_piksela[trenutni_piksel]) })