Zgadnij liczbę: jak zawsze trafić w 10 próbach?
„Pomyślałem liczbę od 1 do 1000. Zgadnij!” Większość uczniów zaczyna od 7, 42 albo swojego numeru w dzienniku. A wystarczy jeden prosty sposób, żeby zawsze zgadnąć w najwyżej 10 próbach. Ten sam sposób wykorzystują programy, bazy danych i każdy z nas, gdy szuka słowa w słowniku.
Przygotowałem aplikację, w której uczniowie mogą to sprawdzić na własnej skórze:
👉 Otwórz Zgadnij liczbę: zgadnij.komputerowka.pl
📘 Instrukcja obsługi: komputerowka.pl/zgadnij-liczbe-doc
Sposób: pytaj o środek
Zamiast strzelać, zapytaj o środek tego, co zostało:
| Próba | Przedział | Pytam o | Odpowiedź |
|---|---|---|---|
| 1 | 1–1000 | 500 | za mało |
| 2 | 501–1000 | 750 | za mało |
| 3 | 751–1000 | 875 | za dużo |
| 4 | 751–874 | 812 | za dużo |
| 5 | 751–811 | 781 | za dużo |
| 6 | 751–780 | 765 | za mało |
| 7 | 766–780 | 773 | za mało |
| 8 | 774–780 | 777 | 🎯 trafione! |
Każda odpowiedź „za mało / za dużo” odrzuca połowę liczb. Z 1000 zostaje 500, potem 250, 125, 62… Po 10 krokach nie zostaje już nic do odrzucenia.
To jest wyszukiwanie binarne, inaczej połówkowe.
Dlaczego akurat 10?
Odwróćmy pytanie: ile liczb da się zgadnąć, mając określoną liczbę pytań? Każde dodatkowe pytanie podwaja tę liczbę:
| Pytań | Liczb | |
|---|---|---|
| 1 | 2 | 2¹ |
| 4 | 16 | 2⁴ |
| 7 | 128 | 2⁷ |
| 10 | 1024 | 2¹⁰, czyli ponad tysiąc |
| 20 | 1 048 576 | ponad milion |
| 30 | ponad miliard | |
| 33 | 8,6 miliarda | każdy człowiek na Ziemi |
To te same potęgi dwójki, co w bitach. #Matematycy nazywają to logarytmem: dla n liczb wystarczy ok. log₂ n pytań.
Po kolei czy na pół?
Najprostszy sposób szukania to #wyszukiwanie liniowe: sprawdzam po kolei od początku. Działa zawsze, ale bywa bardzo wolne:
| Elementów | Liniowe (najgorzej) | Binarne (najgorzej) |
|---|---|---|
| 100 | 100 | 7 |
| 1000 | 1000 | 10 |
| 1 milion | 1 milion | 20 |
| 1 miliard | 1 miliard | 30 |
Gdy danych przybywa dwa razy, binarne potrzebuje tylko jednego kroku więcej. #Informatycy zapisują to jako złożoność O(log n).
Haczyk: dane muszą być posortowane
#Wyszukiwanie binarne działa tylko wtedy, gdy dane są uporządkowane. W słowniku „żyrafa” jest na końcu, więc otwierając go w środku, na „małpie”, wiemy, że trzeba szukać dalej. Ale co, jeśli słownik ktoś pomiesza?
W aplikacji jest słownik 66 zwierząt. W posortowanym #komputer znajduje każde zwierzę w najwyżej 7 krokach. Po pomieszaniu słownika wyszukiwanie binarne nie znajduje słowa, które w nim jest, w ok. 9 na 10 prób. Dlatego sortowanie i wyszukiwanie zawsze idą w parze.
Trochę historii
- 1946: John #Mauchly opisuje wyszukiwanie binarne w wykładach o pierwszych komputerach elektronicznych.
- 1960: pojawia się wersja działająca dla dowolnej liczby elementów.
- 1986: Jon #Bentley pisze, że większość zawodowych programistów, których poprosił o napisanie wyszukiwania binarnego, popełniła błąd.
- 2006: Joshua #Bloch z #Google opisuje błąd w liczeniu środka, który latami siedział m.in. w bibliotece Javy.
Pomysł jest prosty, ale łatwo pomylić się o jeden: przy granicach przedziału albo przy liczeniu środka.
Wypróbuj Zgadnij liczbę
- 🎯 Ty zgadujesz: zakresy 1–100, 1–1000 i 1–1 000 000, oś liczb z kurczącym się przedziałem, podpowiedź „środek” i rekordy.
- 🤖 Teraz komputer zgaduje: pomyśl liczbę, a komputer trafi w najwyżej 10 pytaniach. Spróbuj go oszukać!
- 🏁 Wyścig: wyszukiwanie liniowe kontra binarne na 64 liczbach.
- 📖 Słownik zwierząt: szukanie słowa krok po kroku i pomieszany słownik.
- ✖️ Każde pytanie podwaja moc: potęgi dwójki.
- ❓ Quiz z 10 pytaniami.
👉 Uruchom Zgadnij liczbę: zgadnij.komputerowka.pl
📘 Instrukcja z pomysłami na lekcję: komputerowka.pl/zgadnij-liczbe-doc
Wyzwania
- Zgadnij liczbę od 1 do 1000 w najwyżej 10 próbach. A od 1 do miliona w 20?
- Pomyśl liczbę 1000. Ile pytań potrzebuje komputer? A dla 500?
- Odpowiadaj komputerowi same „większa”. Co się stanie po 10 pytaniach?
- W wyścigu: czy wyszukiwanie liniowe może wygrać z binarnym? Kiedy?
- Dla ambitnych: pomieszaj słownik i znajdź zwierzę, które binarne mimo to odnajdzie. Dlaczego się udało?
Powodzenia!
Zobacz też: wszystkie aplikacje, Wyścig sortowania, Żarówki binarne, GPS po Gdańsku, Wykrywacz błędów i Jak uczy się AI.
© 2026 Komputerowka.pl · Arnold Basiński
