Zasady są proste:
– musisz odgadnąć liczbę w zadanym przedziale. Liczbę tę komputer generuje losowo
– odwracamy sytuację. To komputer ma odgadnąć liczbę wymyśloną przez Ciebie
– wszystkim sterujemy przez podstawowe narzędzie I/O w Javie, czyli Scanner
– program powinien zliczać ilości prób

Od czego zaczynamy?
Od początku ;). Piszemy metodę dla rozgrywki człowieka z komputerem.

1 – Ustawiamy zmienną numberToGuess w postaci randomowo wygenerowanej liczby.

2 – Część właściwa algorytmu. Jeżeli wprowadzona przez zmienna jest mniejsza, niż ta, którą wygenerował komputer (random), mamy dostać komunikat more. Odpowiednio, jeżeli jest większa, mamy dostać komendę less

Pamiętajcie o zamknięciu całości algorytmu w pętli, inaczej program będzie kończyć swe działanie po przejściu przez algorytm. W moim przypadku użyłem pętli while(z użyciem wcześniej zainicjalizowanego booleana o nazwie win. Dopóki win ewaluuje do false, dopóty program będzie śmigał.
Ta część była prosta.

Komputer zgaduje, my odpowiadamy

W tym przypadku sprawa się nieco komplikuje – to komputer ma nas odpytywać. Ciekawe ćwiczenie umysłowe. Zanim jednak przejdziemy do pisania, musimy się zastanowić w jaki sposób komputer ma przeszukiwać zbiór liczb w poszukiwaniu tej, którą my ustawiliśmy. Czy ma iterować po każdej kolejnej liczbie? Czy może strzelać randomowo?
Zanim przejdziemy dalej, spróbujcie napisać dwie wersje – dla iteracji po każdej liczbie od zera, oraz dla strzałów randomowych. Tu nie ma dużej filozofii – robimy to w prostej pęli for. Kilka linijek kodu.

Takie przeszukiwania są oczywiście skrajnie nieefektywne. Dla przedziału od 0 do 100, przy założeniu, że liczbą, którą zgaduje komputer jest 99, będziemy musieli 100 razy iterować zanim ją znajdzie. W przypadku strzałów randomowych też może to zająć aż 100 operacji. Jaki algorytm sprawdzi się tu najlepiej? Pomyślmy wizualizując kolejne kroki:
– wymyślamy liczbę 79
– pierwszy strzał komputera to 50. Zacznijmy od środka przedziału, dzięki temu jesteśmy już teraz o krok bliżej do naszej liczby. przekazujemy informację komputerowi, że nasza liczba jest wyższa
– kolejny strzał komputera: połowa pozostałego przedziału. Na podstawie poprzedniej informacji („more”), komputer wie, że nasza liczba znajduje się w przedziale od 50 do 100. Finalnie strzela 75. Po dwóch krokach nasz algorytm jest już bardzo blisko.

Taki sposób przeszukiwania kolekcji danych nazywa się „wyszukiwaniem binarnym” (binary search algorithm). Wyszukiwania binarne są bardzo często wykorzystywane w podstawowych funkcjonalnościach aplikacji. Jego efektywność to O(log n) – dla przedziału od 0 do 100 algorytm powinien w najgorszym przypadku wykonać 7 iteracji by znaleźć wymyśloną przez nas liczbę.

To teraz zapiszmy go w kodzie:

Jak widać jest tu sporo tymczasowych zmiennych i obiektów – można tu sporo optymalizować i upraszczać, do czego zachęcam. Jest jeszcza jedna kwestia – przeszukiwanie binarne można zaprogramować rekursją. Wszak algorytm ten w pewien sposób przypomina to jak działa QuickSort – dzielimy kolekcję na pół, później jeszcze na pół i tak długo, aż to jest konieczne.

Key takeaways

– do przeszukiwania posortowanej kolekcji danych algorytm wyszukiwania binarnego jest najbardziej efektywny
– odwracanie działania programu tak, by komputer wymagał czegoś od nas, to dobry sposób na efektywne „przemeblowanie” mózgu w temacie komunikacji z programem. To my musimy zaprogramować aplikację tak, by to ona czegoś od nas wymagała
– przeszukiwanie binarne to dobra okazja, by zaimplementować rekursję (a jak rekursja, to … stackoverflow, pamiętacie z ostatniego wpisu o algorytmach?)
– jeżeli nie korzystamy z rekursji musimy umieścić nasz algorytm w pętli if lub while, by wykonywał się aż do momentu w którym zgadniemy liczbę (lub zrobi to komputer)