If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Gra w zgadywanie liczb

Zagrajmy w prostą grę, która pozwoli Ci zrozumieć, dlaczego różne algorytmy, zastosowane do rozwiązania tego samego problemu, mogą mieć tak bardzo różną skuteczność. Komputer wylosuje liczbę całkowitą od 1 do 15. Twoje zadanie polega na tym, żeby zgadnąć tą liczbę. Próbujesz tak długo, aż zgadniesz, a komputer za każdym razem podpowiada Ci, czy Twoja liczba jest większa, czy mniejsza od tej, której szukasz:
Kiedy już zgadniesz, powiedz nam skąd wiedziałeś jaką liczbę wybrać w kolejnym kroku.
Może próbowałeś 1, potem 2, potem 3, potem 4 i tak dalej, aż trafiłeś na właściwą liczbę. Taką metodę nazywamy przeszukaniem liniowym, ponieważ zgadywałeś liczby po kolei. To działa. Ile wynosi największa możliwa liczba prób, których będziesz potrzebować? Jeśli komputer wybierze liczbę 15, będziesz potrzebować 15 prób. Z drugiej strony, jeśli masz szczęście, komputer wybierze liczbę 1 i trafisz w pierwszej próbie. A ile wynosi średnia liczba prób? Jeśli komputer wybiera z jednakowym prawdopodobieństwem każdą liczbę od 1 do 15, to średnio będziesz potrzebować 8 prób.
Czy można postąpić sprytniej niż zgadywać po kolei 1, 2, 3, 4, … ? Skoro komputer daje Ci informację czy zaproponowana przez Ciebie liczba jest większa, mniejsza czy równa tej wybranej przez komputer, możesz zacząć od 8. Jeśli liczba wybrana przez komputer jest mniejsza niż 8, możesz z góry wyeliminować wszystkie liczby od 8 do 15. Jeśli liczba wybrana przez komputer jest większa niż 8, możesz wyeliminować wszystkie liczby od 1 do 8. W obu przypadkach możesz wyeliminować połowę możliwości. W następnym kroku wyeliminujesz połowę pozostałych liczb. I tak dalej, za każdym razem eliminując połowę pozostałych liczb.
Tą strategię dzielenia na pół nazywamy przeszukiwaniem binarnym i niezależnie od tego, jaką liczbę od 1 do 15 wybierze komputer, tą metodą powinieneś zgadnąć prawidłową odpowiedź w nie więcej niż 4 próbach.
Spróbuj zgadnąć liczbę od 1 do 300. Nie powinieneś potrzebować więcej niż 9 prób.
Ile prób potrzebowałeś żeby zgadnąć tym razem? Dlaczego nigdy nie będziesz potrzebować więcej niż 9 prób? Potrafisz podać matematyczne wyjaśnienie?
Wrócimy jeszcze do przeszukiwania binarnego i zobaczymy jak można wykorzystać tą metodę aby skutecznie przeszukać tablicę zakodowaną w JavaScript. Na razie jednak zajmijmy się algorytmem rozwiązania bardziej złożonego problemu.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.

Chcesz dołączyć do dyskusji?

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.