„Gondoltam egy számra...”

A program generál véletlenszerűen egy számot 1 és 100 között, amit a lehető legkevesebb lépésben kell kitalálni.

Tippeléseink során akkor járunk el a leghatékonyabban, ha az első tippünk a kitalálandó tartományt lehetőleg két egyenlő részre osztó szám lesz. Amennyiben nem talált, meghatározzuk, hogy a kitalálandó szám melyik tartományban van. Ezt a tartományt aztán egy tippel ismét két részre osztjuk. Az eljárást addig ismételjük, amíg rá nem találunk a számunkra. Bizonyítható hogy a számunk a fentiekben leírt módszerrel

n <= log2Nmax

lépésben meghatározható.

Programozási tételek: Logaritmikus keresés tétele

A játék algoritmusának mondatszerű leírása:

Program gondoltamegyszamra:

szam = veletlenszam(1,100)

i = 0

Ciklus

i = i + 1

Ki: i. tipp

Be: tipp

Ha tipp < szam akkor

Ki: ”Nem talált, a szám nagyobb!”

Elágazás vége

Ha tipp > szam akkor

Ki: ”Nem talált, a szám kisebb!”

Elágazás vége

Mígnem szam = tipp

Ciklus vége

Ha i <= 7 akkor

Ki: ”Talált! Tökéletes játék!.”

egyébként

Ki: ”Sikerült, de kevesebb lépésből is ment volna!”

Elágazás vége

Program vége.