Ha ezt az üzenetet látod, az annak a jele, hogy külső anyagok nem töltődnek be hibátlanul a honlapunkra.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Fő tartalom

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.

Szeretnél részt venni a beszélgetésben?

Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.