Na poprzedniej lekcji poznaliśmy wyszukiwanie elementu w zbiorze nieuporządkowanym. Dziś przechodzimy dalej i zajmiemy się wyszukiwaniem w zbiorze uporządkowanym, czyli takim, w którym elementy są zapisane od najmniejszego do największego.
Poznasz metodę połowienia, zwaną też metodą „dziel i zwyciężaj”.
Na tej lekcji:
przećwiczysz grę w zgadywanie liczby,
zrozumiesz, jak działa wyszukiwanie przez połowienie,
przeanalizujesz przykłady z książki,
wykonasz ćwiczenia praktyczne w Baltie,
porównasz metodę liniową z metodą połowienia.
- Wyszukiwanie elementu w zbiorze uporządkowanym metodą połowienia
Jeżeli elementy w zbiorze są uporządkowane, nie trzeba sprawdzać ich po kolei. Można zacząć od środka zbioru i odrzucać tę część, w której na pewno nie ma szukanego elementu.
To właśnie jest metoda połowienia.
Jeżeli szukasz liczby 40 w uporządkowanym zbiorze, najpierw sprawdzasz element środkowy:
jeśli jest równy 40 — koniec,
jeśli jest większy — odrzucasz prawą połowę,
jeśli jest mniejszy — odrzucasz lewą połowę.
W ten sposób liczba sprawdzanych elementów szybko maleje.
Odwołania do ilustracji:
str. 112 — wprowadzenie do metody połowienia i „Gra w zgadywanie liczby”
str. 113, rys. 5 — program realizujący grę w zgadywanie liczby
str. 114, rys. 6 — przykład wyszukiwania liczby w zbiorze uporządkowanym metodą połowienia
str. 115, rys. 7 — przykład z książkami na półce
str. 116, rys. 8 — program w Pythonie realizujący wyszukiwanie metodą połowienia - Gra w zgadywanie liczby
Zanim przejdziesz do właściwego algorytmu, przećwiczysz myślenie metodą połowienia w prostszej wersji — jako grę w zgadywanie liczby.
Jedna osoba wybiera liczbę z zakresu od 1 do 100, a druga próbuje ją odgadnąć. Najlepiej zaczynać od liczby środkowej, czyli 50, a potem zawężać zakres możliwych odpowiedzi.
To dokładnie ten sam pomysł, który wykorzystuje algorytm wyszukiwania przez połowienie.
Ćwiczenie 6. Gramy w zgadywanie liczby
Zagraj z koleżanką lub kolegą w zgadywanie liczby. Przyjmijcie zbiór liczb naturalnych z zakresu od 1 do 100.
Wskazówka: Jeśli jesteś osobą zgadującą liczbę, najlepiej na początku podać liczbę 50. Jak sądzisz, dlaczego?
Odwołanie:
str. 112 — ćwiczenie 6 - Algorytm gry w zgadywanie liczby
W książce pokazano algorytm gry w zgadywanie liczby oraz jego zapis w Pythonie. U Was punktem wyjścia do zrozumienia działania będzie:
lista kroków,
schemat myślenia,
wykonanie ćwiczenia praktycznego w Baltie.
Lista kroków
Zacznij algorytm.
Zmiennej szukana przypisz liczbę, którą ma odgadnąć gracz.
Wprowadź liczbę podawaną przez gracza do zmiennej liczba.
Jeżeli liczba = szukana, idź do kroku 7.
Jeżeli liczba > szukana, wyświetl napis „Za duża”; w przeciwnym przypadku wyświetl napis „Za mała”.
Idź do kroku 3.
Wyprowadź komunikat „Gratulacje! Odgadnięta liczba to: ” i wartość zmiennej szukana.
Zakończ algorytm.
Odwołania:
str. 113 — lista kroków
str. 113, rys. 5 — program w Pythonie realizujący algorytm gry
Ćwiczenie 7. Tworzymy w języku Python grę w zgadywanie liczby
W książce ćwiczenie polega na przepisaniu programu z rysunku 5 i uruchomieniu go.
U Ciebie:
Przeanalizuj program pokazany na rys. 5 (str. 113).
Zwróć uwagę, jak działa pętla while i instrukcja if.
Następnie wykonaj wersję logiczną tej gry w Baltie — nie jako klasyczne wpisywanie liczb, ale jako symulację zawężania zakresu lub wybierania odpowiednich pól / komunikatów.
Możesz przygotować prostą planszę z liczbami albo etykietami „za mała”, „za duża”, „dobrze”.
Odwołanie:
str. 113, rys. 5
str. 114 — omówienie działania programu
Ćwiczenie 8. Modyfikujemy program
W książce ćwiczenie 8 polega na zmianie sposobu wprowadzania zmiennej szukana.
U Ciebie:
Wróć do pomysłu z ćwiczenia 7.
Zmień program tak, aby rolę „wprowadzania liczby” pełnił inny sposób sterowania w Baltie, np. wybór pola, kliknięcie lub przygotowane komunikaty.
Sprawdź, czy da się uprościć liczbę kroków potrzebnych do odnalezienia właściwego wyniku.
Odwołanie:
str. 114 — ćwiczenie 8 - Algorytm wyszukiwania elementu w zbiorze uporządkowanym metodą połowienia
Teraz przechodzisz do właściwego algorytmu wyszukiwania.
W zbiorze uporządkowanym:
sprawdzasz środek,
odrzucasz połowę niepotrzebnych danych,
powtarzasz działanie aż znajdziesz element albo dojdziesz do wniosku, że go nie ma.
Opis działania
Jeśli szukasz liczby 40 w zbiorze uporządkowanym:
najpierw sprawdzasz środek,
potem tylko lewą albo prawą część zbioru,
znowu wybierasz środek pozostałej części,
i tak dalej.
Odwołania do ilustracji:
str. 114, rys. 6 — przykład krok po kroku
str. 115, rys. 7 — analogia z półką książek
str. 116, rys. 8 — program w Pythonie
Ćwiczenie 9. Sprawdzamy działanie algorytmu wyszukiwania liczby w zbiorze uporządkowanym metodą połowienia
Przygotuj odpowiednie pomoce dydaktyczne i przedstaw wspólnie z klasą algorytm wyszukiwania liczby w zbiorze uporządkowanym metodą połowienia.
Wskazówka: Możesz zapisać liczby na kartkach i układać je na stole lub podłodze.
U Was można to zrobić również w Baltie:
ułóż liczby na scenie od najmniejszej do największej,
zaznacz element środkowy,
pokazuj kolejne etapy odrzucania lewej lub prawej części zbioru.
Odwołanie:
str. 115 — ćwiczenie 9
str. 114, rys. 6
str. 115, rys. 7
Ćwiczenie 10. Zapisujemy w języku Python algorytm wyszukiwania elementu w zbiorze uporządkowanym
W książce ćwiczenie 10 polega na przepisaniu programu z rys. 8 (str. 116).
U Ciebie:
Przeanalizuj program z rys. 8.
Zwróć uwagę na zmienne:
poczatek
koniec
srodek
Przećwicz działanie tego algorytmu na przykładzie przygotowanym w Baltie.
Jeśli starczy czasu, przepisz program także w Pythonie i uruchom go dla uporządkowanych danych.
Odwołanie:
str. 116, rys. 8
str. 117 — ćwiczenie 10 - Zapamiętaj
Najważniejsze informacje z tej części tematu:
element w zbiorze nieuporządkowanym szukamy zwykle metodą liniową,
element w zbiorze uporządkowanym można znaleźć szybciej metodą połowienia,
wyszukiwanie przez połowienie jest przykładem metody „dziel i zwyciężaj”.
Odwołanie:
str. 118 — ramka „Zapamiętaj” - Oko w oko z monitorem – pytania i polecenia
Wyjaśnij, w jaki sposób znajduje się największą spośród siedmiu liczb w zbiorze nieuporządkowanym.
Dlaczego w programie z rysunku 2 wprowadzaną wartość przypisujemy najpierw zmiennej maks?
Jakie może być zastosowanie algorytmu wyszukiwania przez połowienie? Pokaż na przykładzie.
Dlaczego w programie realizującym algorytm wyszukiwania elementu w zbiorze uporządkowanym najpierw sprawdzamy, czy środkowy element jest szukaną liczbą?
Odwołanie:
str. 119 — sekcja „Oko w oko z monitorem” - Zadania końcowe
Zadanie 1
Na podstawie listy kroków pokazanej wcześniej opracuj własną listę kroków algorytmu znajdowania najmniejszej liczby spośród dziesięciu liczb. Sprawdź działanie algorytmu dla danych: 5, 78, 15, 0, 1, 100, 155, 50, 22, 30
Zadanie 2
Zdefiniuj funkcję minimum_n() wyszukującą najmniejszy element w zbiorze n-elementowym. Wywołaj funkcję w programie głównym. Zapisz program w pliku pod nazwą: Minimum_n
Zadanie 3
Dany jest uporządkowany zbiór liczb: 5, 8, 15, 20, 25, 30, 35, 70, 88, 90, 100, 120
Poszukiwana liczba to 70.
Przedstaw na rysunku (podobnym do rys. 6) sposób znalezienia liczby 70.
Zadanie 4
Opracuj listę kroków algorytmu wyszukiwania przez połowienie. Skorzystaj z opisu metody podanego wcześniej.
Zadanie 5
Zdefiniuj funkcję maksimum_lista() tak, aby znajdowała maksymalną wartość na liście liczb. Zapisz program w pliku pod nazwą: Liczba_maksymalna
Odwołanie:
str. 119 — zadania i zadania dodatkowe - Organizacja pracy
Ćwiczenia wykonujesz przede wszystkim:
praktycznie w Baltie,
a przykłady zapisane w Pythonie traktujesz jako wzór do analizy i porównania.
Jeśli wykonujesz wersję w Pythonie, zapisuj pliki zgodnie z nazwami podanymi w zadaniach.