TEMAT: Odgadniesz liczbę?

1. wyszukiwanie elementów w zbiorze uporządkowanym,
2. stosowanie wyszukiwania binarnego według metody „dziel i zwyciężaj”,
3. losowanie liczb całkowitych.

WYSZUKIWANIE BINARNE

Jednym z przykładów wyszukiwania jest gra Zgadnij liczbę, w której odgaduje się liczbę wylosowaną przez przeciwnika. Wyobraź sobie, że komputer wylosował liczbę z zakresu od 1 do 100, a ty masz zgadnąć, jaka to liczba. Podajesz swoją propozycję, a komputer ci odpowiada:

• trafiona (jeśli odgadniesz wylosowaną przez niego liczbę),
• za mała (jeśli podana przez ciebie liczba jest mniejsza niż wylosowana),
• za duża (jeśli podana przez ciebie liczba jest większa niż wylosowana).

Gdy odgadujesz liczbę z zakresu od 1 do 100, możesz trafić za pierwszym razem, albo dopiero za setnym. Metoda przypadkowego wyszukiwania liczb nie jest ani dobra, ani szybka.
Co możesz zrobić, by odgadnąć liczbę w najmniejszej liczbie prób? Zastosuj wyszukiwanie binarne według metody „dziel i zwyciężaj”. Rozpocznij od elementu środkowego badanego zbioru. Elementem środkowym w przypadku liczb od 1 do 100 będzie liczba 50 lub 51. Sprawdź, czy jest to liczba wylosowana przez komputer. Jeśli tak, to problem jest rozwiązany. Jeśli nie, to poszukiwany element jest albo mniejszy od elementu środkowego, albo większy. Ponieważ zbiór liczb jest uporządkowany, elementy mniejsze od środkowego będą leżały w pierwszej połówce zbioru, a elementy większe – w drugiej. Kontynuuj poszukiwania w coraz mniejszych zbiorach, aż znajdziesz wylosowaną liczbę.
W zbiorze stuelementowym trzeba wykonać maksymalnie siedem kroków:

• Trafiasz w połowę zakresu, zmniejszasz zbiór do 50 elementów.
• Trafiasz w połowę zakresu, zmniejszasz zbiór do 25 elementów.
• Trafiasz w połowę zakresu, zmniejszasz zbiór do 13 elementów.
• Trafiasz w połowę zakresu, zmniejszasz zbiór do 7 elementów.
• Trafiasz w połowę zakresu, zmniejszasz zbiór do 4 elementów.
• Trafiasz w połowę zakresu, zmniejszasz zbiór do 2 elementów.
• Pozostał ostatni element.

LOSOWANIE LICZB

A teraz sprawdź, jak działa losowanie liczb w Pythonie.

Zaimportuj funkcję randint z modułu random odpowiadającego za losowanie.

Ćwiczenie – wykonaj losowanie np. 50 liczb

 

PĘTLA WHILE

Jeśli nie wiesz, ile razy powinna być wykonywana pętla, najlepiej zastosuj pętlę while. Wykonuje ona ciąg poleceń, dopóki podany warunek jest prawdziwy.

while warunek:

Obliczanie sumy 10 cyfr:

GRA W PYTHONIE

Zacznij tworzyć grę, w której użytkownik będzie zgadywał wylosowaną przez komputer liczbę.

• Zdefiniuj funkcję zgadnij(), za pomocą której komputer wylosuje liczbę z zakresu od 1 do 100.
• A teraz zdefiniuj funkcję input, która umożliwi wczytanie liczby podanej przez gracza.
  odp = int(input(„Podaj liczbę „))Po wypisaniu komunikatu Podaj liczbę (w komunikatach możesz używać polskich znaków) kursor będzie czekać na wpisanie liczby z klawiatury (int na początku komunikatu oznacza, że wczytywana jest wartość całkowita). Ponieważ program nie jest zabezpieczony przed niepoprawnym wpisywaniem danych, po wpisaniu ułamka dziesiętnego pojawi się komunikat o błędzie.
• Po wylosowaniu liczby przez komputer i podaniu odpowiedzi przez gracza należy zastosować pętlę while do sprawdzania, czy liczby są sobie równe.

Pozostaje już tylko wypisać komunikat trafiona.