A kitalálós játék

Egy kis játék segítségével megpróbáljuk illusztrálni, hogy különböző algoritmusok ugyanazt a problémát mennyire eltérő hatékonysággal kezelik. A számítógép véletlenszerűen kiválaszt egy 1 és 15 közé eső egész számot. Addig találgathatsz, amíg rá nem jössz a számítógép által kiválasztott számra. Minden tippedre megmondja a számítógép, hogy az nagyobb, vagy kisebb, mint a gondolt szám. (A program feliratai: „My number is higher than 8. Guess higher" - „A gondolt szám nagyobb, mint 8. Tippelj magasabbat!"; „My number is lower than 8. Guess lower" - „A gondolt szám kisebb, mint 8. Tippelj alacsonyabbat!"; „Yes! That's my number" - „Igen! Ez a gondolt szám"; a gomb felirata: „New game" - „Új játék")

Miután kitaláltad a számot, gondolkodj el azon, milyen módszer szerint tippelted meg a következő számot!

Lehet, hogy sorba vetted a számokat: 1, 2, 3, 4... amíg el nem találtad a megoldást. Ezt a megközelítést lineáris keresésnek hívják, mert úgy vizsgálod meg a számokat, mintha sorban állnának. Ez működik. De maximálisan hány találgatásra van szükség? Ha a számítógép a 15-öt választja, akkor 15 találgatás kell. Ugyanakkor viszont, ha szerencséd van, a számítógép 1-et választ, és akkor az első találgatásod eredményes lesz. Mi a helyzet az átlaggal? Ha a számítógép egyforma eséllyel választja bármelyik számot 1-től 15-ig, akkor átlagosan 8 találgatásra lesz szükséged.

De az 1, 2, 3, 4... találgatásnál hatékonyabb megoldást is ki tudnál találni, nem? Mivel a számítógép megmondja, hogy a tipped túl alacsony, vagy túl magas, az első tipp lehetne a 8. Ha a számítógép által választott szám kisebb, mint 8, akkor, mivel tudod, hogy a 8 túl magas, kiküszöbölheted az összes számot 8-tól 15-ig. Ha a számítógép által választott szám nagyobb, mint 8, akkor 1-től 8-ig zárhatók ki a számok. Mindkét esetben a számok fele kiküszöbölhető. A következő találgatással újból kizárható a maradék szám fele. Így folytatva mindig kiküszöbölheted a maradék felét.

Ezt a felező megközelítést bináris keresésnek nevezzük, és függetlenül attól, hogy a számítógép melyik számot választotta 1-től 15-ig, maximum 4 találgatással meg tudod találni a megoldást.

Próbáld ki 1-től 300-ig! 9-nél több tippre nem lesz szükség. (A program feliratai: „My number is higher than 150. Guess higher" - „A gondolt szám nagyobb, mint 150. Tippelj magasabbat!"; „My number is lower than 150. Guess lower" - „A gondolt szám kisebb, mint 150. Tippelj alacsonyabbat!"; „Yes! That's my number" - „Igen! Ez a gondolt szám"; a gomb felirata: „New game" - „Új játék")

Hány találgatás kellett most a szám eltalálásához? Mért nem kell soha 9-nél több találgatás? (Tudsz rá matematikai magyarázatot találni?)

Vissza fogunk még térni a bináris keresésre, és meg fogjuk vizsgálni, hogyan tudunk hatékonyan megkeresni egy adott elemet egy JavaScript tömbben. De előbb vizsgáljuk meg egy ennél bonyolultabb feladat algoritmusát.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.