Algorytm wyszukiwania w zbiorze danych
Informatyka, Klasy VII i VIII
Imię ucznia: ............................................ Klasa: ................ Data: ................
Dostajesz listę 16 numerów inwentarza ze szkolnej biblioteki, uporządkowaną od najmniejszego do największego. Twoim zadaniem jest wykonać na niej dwa algorytmy wyszukiwania i policzyć, który potrzebuje mniej kroków.
-
Przepisz z tablicy algorytm B, czyli połowienie zakresu, jako ponumerowane kroki. Podkreśl ten krok, który kończy działanie algorytmu, gdy szukanego numeru nie ma na liście.
Wskazówka: Krok kończący zaczyna się od słowa „jeśli” i porównuje dolną z górną. Bez niego algorytm nigdy się nie zatrzyma.
-
Wykonaj oba algorytmy dla numerów 1199, 1560 i 1305. Do tabeli wpisz w kolejnych kolumnach: szukany numer, liczbę kroków algorytmu A, liczbę kroków algorytmu B, wynik czyli pozycję albo słowo „nie ma”.
Wskazówka: Jeden krok to jedno porównanie szukanego numeru z numerem z listy. Numer 1305 nie występuje na liście i to nie jest pomyłka w druku.
-
Napisz jednym zdaniem, przy którym z trzech numerów przewaga połowienia była najmniejsza i dlaczego akurat przy nim.
Wskazówka: Sprawdź, na której pozycji od początku listy leży ten numer.
-
W edytorze Scratch zbuduj skrypt zgadujący liczbę od 1 do 100 metodą połowienia. Ustaw zmienne dolna na 1, gorna na 100, proby na 0. W pętli powtarzanej aż odpowiedź będzie równa słowu trafione wykonaj: ustaw strzal na podłoga z ((dolna plus gorna) podzielone przez 2), czyli zaokrąglenie w dół, zmień proby o 1, zapytaj „Czy Twoja liczba to strzal? Odpowiedz: za malo, za duzo albo trafione” i czekaj, jeżeli odpowiedź to za malo ustaw dolna na strzal plus 1, jeżeli odpowiedź to za duzo ustaw gorna na strzal minus 1.
Wskazówka: Bloki zmiennych znajdziesz w kategorii Zmienne, blok zapytaj i czekaj w kategorii Czujniki, a blok „podłoga z” w kategorii Wyrażenia: to blok z listą rozwijaną, w której domyślnie stoi „pierwiastek”, wybierz w niej „podłoga”. Nie używaj bloku „zaokrąglij”, bo zaokrągla 5,5 do 6, a algorytm z tablicy zaokrągla w dół. Pamiętaj o plus 1 i minus 1, bez nich zakres przestanie się zmniejszać.
-
Przetestuj skrypt na trzech różnych liczbach i zapisz największą liczbę prób, jaką uzyskałeś. Dopisz, ile prób potrzebowałby ten sam skrypt przy zakresie od 1 do 1000.
Wskazówka: Za każdym razem gdy zakres rośnie dwukrotnie, dochodzi dokładnie jedna próba. Policz, ile razy trzeba podwoić liczbę 1, żeby przekroczyć 1000: 1, 2, 4, 8 i dalej. Liczba podwojeń to liczba prób w najgorszym przypadku.