Algorytm wyszukiwania w zbiorze danych
Slajdów: 8. Notatka pod slajdem jest dla nauczyciela, uczniowie jej nie widzą na tablicy.
Slajd 1
Zgadnij liczbę od 1 do 1000
- Pytania tylko o za mało albo za dużo
- Liczymy pytania na tablicy
- Po kolei to do 1000 pytań
Notatka dla nauczyciela: Zagrajcie naprawdę, zanim cokolwiek wyjaśnicie. Liczba kresek na tablicy jest lepszym wstępem niż definicja.
Slajd 2
Czym jest algorytm
- Skończony ciąg jednoznacznych kroków
- Ten sam wynik przy każdym wykonaniu
- Wykonuje go ktoś bez wiedzy o zadaniu
Notatka dla nauczyciela: Podkreślcie słowo jednoznacznych. Cała praca uczniów sprawdza właśnie to.
Slajd 3
Nasz zbiór danych
- 16 numerów inwentarza biblioteki
- Uporządkowane rosnąco
- Pozycje ponumerowane od 1 do 16
Notatka dla nauczyciela: Wyświetlcie listę i zostawcie ją na ekranie przez całą lekcję. Uczniowie będą do niej wracać.
Slajd 4
Algorytm A, szukanie po kolei
- Sprawdzaj pozycje od pierwszej do ostatniej
- Trafienie kończy działanie
- Koniec listy oznacza odpowiedź nie ma
Notatka dla nauczyciela: Zapiszcie te kroki numerami na tablicy, nie zdaniami ciągłymi. Uczniowie mają je przepisać.
Slajd 5
Algorytm B, połowienie zakresu
- Środek to suma granic przez 2, w dół
- Za mało podnosi dolną, za dużo obniża górną
- Dolna większa od górnej kończy szukanie
Notatka dla nauczyciela: Wykonajcie ten algorytm na żywo dla numeru 1401. Wychodzą 2 kroki i klasa od razu widzi różnicę.
Slajd 6
Warunek zakończenia
- Algorytm musi umieć powiedzieć nie ma
- Bez tego warunku wykonanie się nie kończy
- Sprawdzamy na numerze 1300 spoza listy
Notatka dla nauczyciela: To najczęściej pomijany element w uczniowskich zapisach. Wracajcie do niego przy sprawdzaniu prac.
Slajd 7
Ile kroków przy większym zbiorze
- 16 pozycji to do 5 kroków połowienia
- 1000 pozycji to do 10 kroków
- 1 000 000 pozycji to do 20 kroków
Notatka dla nauczyciela: Poproście klasę o dokończenie ciągu samodzielnie. Reguła podwajania jest tu ważniejsza niż same liczby.
Slajd 8
Kiedy połowienie nie pomaga
- Lista musi być uporządkowana
- Dana blisko początku znajduje się szybciej po kolei
- Porządkowanie zbioru też kosztuje czas
Notatka dla nauczyciela: Bez tego slajdu uczniowie wyjdą z przekonaniem, że jedna metoda jest zawsze lepsza. Podajcie kontrprzykład z lekcji, numer 1199.