Krok 1. Warto powtórzyć.
👉 Jakie znasz przykłady szyfrowania informacji?
👉 W jakim celu szyfruje się informacje?
👉 Czym jest tekst jawny?
👉 Czym jest szyfrogram?
👉 Na czym polega szyfr Cezara?
👉 Jaką rolę pełni klucz w szyfrze Cezara?
👉 Na czym polega szyfrowanie tekstu metodą przestawieniową?
Krok 2. Algorytm wyszukiwania przez połowienie
Algorytm wyszukiwania przez połowienie jest przykładem metody „dziel i zwyciężaj”. Polega ona na dzieleniu przeszukiwanego zbioru na dwie części i zawężeniu przeszukiwania do jednej z tych części.
Krok 3. Analiza algorytmu wyszukiwania metodą połowienia
Algorytm poszukiwania przez połowienie jest przykładem metody dziel i zwyciężaj. Polega ona na dzieleniu przeszukanego zbioru na dwie części i zawężeniu przeszukiwania do jednej z tych części. Metoda podziału pomaga szybko znaleźć poszukiwany element, czyli zwyciężyć.
Algorytm
Na przykład: zbiór liczb od najmniejszej do największej:
11 23 35 44 51 59 62 71 88 91
Poszukiwana liczba to 44
Dzielimy zbiór liczb na dwie części, rozdzielone środkowym elementem. Zaczynamy od sprawdzenia tego elementu.
11 23 35 44 51 | 59 62 71 88 91
W przypadku gdy liczba elementów zbioru jest parzysta, to spośród dwóch środkowych elementów (w naszym przypadku liczb 51 i 59) jako "środkowy" wybieramy ten, który jest pierwszy w kolejności (czyli 51).
Jeśli środkowy element jest szukaną liczbą, kończymy wyszukiwanie. Jeśli środkowy element jest większy od poszukiwanej liczby, przeszukujemy podzbiór na lewo od elementu środkowego. Jeśli środkowy element jest mniejszy od poszukiwanej liczby, przeszukujemy podzbiór na prawo od elementu środkowego.
11 23 | 35 44 51 59 62 71 88 91
11 23 35 | 44 51 59 62 71 88 91
11 23 35 44 51 59 62 71 88 91
Krok 4. Przeprowadź analizę rozwiązania do zbioru liczb
1 25 36 45 53 58 60 75 89 91 99 102 125
Poszukiwana liczba to 102
Odpowiedź na pytania:
👉 Jakie powtarzające się operacje zauważasz w rozwiązaniu?
👉 Kiedy kończymy powtarzanie operacji połowienia zbioru?
Komentarze
Prześlij komentarz