Specyfikacja:
Dane: Zbiór elementów w postaci ciągu n uporządkowanych liczb x1<= x2<= …<=xn. Wyróżniony element y. Wynik: Jeśli y należy do tego zbioru, podaj miejsce (index) w ciągu, w przeciwnym razie sygnalizuj brak takiego elementu w zbiorze.Algorytm:
Powtarzaj kroki 1-3, dopóki nie natrafisz na poszukiwany element.Krok 1: Sprawdź element środkowy ciągu (gdy ciąg ma nieparzystą liczbę elementów) lub jeden z dwóch elementów środkowych (gdy ciąg ma parzystą liczbę elementów).
Krok 2: Jeśli jest on elementem poszukiwanym y, to zakończ algorytm.
Krok 3: Jeśli środkowy element jest większy od y, to pozostaw podciąg na lewo od elementu środkowego, a w przeciwnym wypadku (gdy element środkowy jest mniejszy od y), pozostaw podciąg na prawo od elementu środkowego.
Zadanie: Zapisz program „Zgadnij jaka to liczba?” odpowiadający na podane pytanie.
Wybierz partnera z grupy. Następnie partner wymyśli dowolną liczbę n z przedziały [1, 50], a Ty masz ją znaleźć, zadając mu pytania typu: „Czy to jest liczba …?” Na co Twój partner może jedynie odpowiedzieć : „Tak”- gdy trafiłeś, lub „Za mała”, „Za duża”- w zależności od położenia wybranej przez Ciebie liczby względem ukrytej liczby.
Wytłumaczenie do tego algorytmu z forum elektroda:
Jak się szuka? Mamy przykładowo 32 liczby, od zera do 31
1.
zakresDolny = 0
zakresGorny = 31
2.
pozycja = w połowie = (zakresDolny+zakresGorny)/2
3.
Jeżeli tablica[pozycja] == szukana to znaleziono, exit.
Jeżeli liczba w tablicy na pozycji `pozycja` jest mniejsza od szukanej, to przesuwamy dolny zakres nad aktualną pozycję, bo szukanej liczby na pewno nie będzie niżej (zakresDolny=pozycja+1).
Jeżeli liczba w tablicy na pozycji `pozycja` jest większa od szukanej, to znaczy że jesteśmy za wysoko, więc górna granica spada poniżej aktualnej pozycji: zakresGorny=pozycja-1.
Jeżeli górny zakres nie jest większy od dolnego, powtórz od kroku 2.
Jeżeli nie znaleziono liczby, to automatycznie mamy pozycję na którą można wstawić nową liczbę (przesuwając wszystkie elementy po `prawej` w `prawo` o jedną pozycję). Jest nią pozycja+x, gdzie x jest jedynką tylko wtedy, gdy ostatnie porównanie podniosło dolną granicę.
Kod:
On: Pomyślałem sobie liczbą od zera do 31, zgadnij jaką? (pomyślał sobie 9)
Ja: (liczę...)
zakresDolny = 0
zakresGorny = 31
połowa = (zakresDolny+zakresGorny)/2 = 15
Ja: pytam czy to 15
On: mniej
Ja: (liczę... zostały liczby 0-14)
zakresDolny = 0
zakresGorny = 15-1 = 14
połowa = (0+14)/2 = 7
Ja: pytam czy to 7
On: więcej
Ja: (liczę... zostały liczby 8-14)
zakresDolny = 7+1 = 8
zakresGorny = 14
połowa = (8+14)/2 = 11
Ja: pytam czy to 11
On: mniej
Ja: (liczę... zostały liczby 8,9,10)
zakresDolny = 8
zakresGorny = 11-1 = 10
połowa = (8+10)/2 = 9
Ja: pytam czy to 9
On: Tak
Implementacja w C++
#include <iostream> using namespace std; const int n = 50; const int y = 10; int wyszukaj (int p, int k, int tab[]) { int l_zbioru = k - p; int polowa_liczb = l_zbioru/2; int srodek_zbioru = p + polowa_liczb; if ( y == tab[srodek_zbioru]) return tab[y]; if (l_zbioru < 0) return 0; if ( y < tab[srodek_zbioru] ) { return wyszukaj(p,srodek_zbioru-1,tab); } if ( y > tab[srodek_zbioru] ) return wyszukaj (srodek_zbioru+1,k,tab); } int main() { int tab[n]; for (int i = 1; i<=n; i++) { tab[i] = i; } cout << wyszukaj(1,n,tab); return 0; }
I. WIADOMOŚCI I ROZUMIENIE
Zdający zna i rozumie podstawowe pojęcia, metody, narzędzia i procesy
związane z informatyką i technologią informacyjną:
POZIOM PODSTAWOWY:
1) opisuje środki, narzędzia i metody informatyki posługując się poprawną
terminologią informatyczną
2) zna rolę, funkcje i zasady pracy sprzętu komputerowego
3) charakteryzuje typowe narzędzia informatyczne i ich zastosowania
4) zna podstawową terminologię związaną z sieciami komputerowymi:
rodzaje sieci, protokoły, opisuje podstawowe usługi sieciowe
i sposoby ochrony zasobów
5) omawia przydatność i wiarygodność różnych źródeł i zbiorów informacji oraz
użyteczność sposobów i form ich reprezentowania
6) zna sposoby reprezentowania informacji w komputerze
7) zna podstawowe algorytmy i techniki algorytmiczne:
a) algorytmy badające własności liczb całkowitych i naturalnych
b) algorytmy wyszukiwania i porządkowania (sortowania)
c) algorytmy na tekstach
d) proste algorytmy szyfrowania
e) metoda dziel i zwyciężaj
f) iteracja i rekurencja
8) zna zasady programowania strukturalnego
9) zna podstawowe własności algorytmów
10) zna podstawowe pojęcia związane z relacyjnymi bazami danych
11) zna i opisuje zasady etyczne i prawne związane z wykorzystywaniem
informacji i oprogramowania
POZIOM ROZSZERZONY:
Jak na poziomie podstawowym oraz
1) zna i opisuje zasady administrowania siecią komputerową
2) charakteryzuje sposoby reprezentowania informacji w komputerze
3) zna systemy liczbowe mające zastosowanie w informatyce
4) zna techniki algorytmiczne i algorytmy:
a) dziel i zwyciężaj
b) metoda zachłanna
c) iteracja i rekurencja
d) badające własności liczb całkowitych
e) wyszukiwania i porządkowania (sortowania)
f) schemat Hornera
g) algorytmy na tekstach
h) algorytmy numeryczne
i) algorytmy kompresji
5) zna wybrane struktury danych i ich realizację
6) zna zasady programowania obiektowego
II. KORZYSTANIE Z INFORMACJI
Zdający stosuje posiadaną wiedzę do rozwiązywania zadań teoretycznych i praktycznych:
POZIOM PODSTAWOWY:
1) posługuje się typowymi programami użytkowymi
2) wykorzystuje wybrane środowisko programistyczne do zapisywania,
uruchamiania i testowania programu
3) korzysta z zasobów i usług sieci komputerowych
4) stosuje metody wyszukiwania i przetwarzania informacji w relacyjnych
bazach danych
5) stosuje podstawowe algorytmy i struktury danych w rozwiązywaniu
problemów informatycznych
6) dobiera właściwy program (użytkowy lub własnoręcznie napisany)
do rozwiązywanego zadania
7) wykorzystuje zdobytą wiedzę i umiejętności do rozwiązywania zadań
z różnych dziedzin nauczania i problemów z życia codziennego
POZIOM ROZSZERZONY:
Jak na poziomie podstawowym oraz
1) stosuje metody wyszukiwania i przetwarzania informacji w relacyjnych
bazach danych z wykorzystaniem różnych technik i narzędzi
2) stosuje kolejne etapy prowadzące do otrzymania poprawnego rozwiązania
problemu: od sformułowania specyfikacji problemu po testowanie rozwiązania
3) stosuje narzędzia i techniki informatyczne do modelowania i symulacji
procesów oraz zjawisk
III. TWORZENIE INFORMACJI
Zdający stosuje metody informatyczne do rozwiązywania problemów:
POZIOM PODSTAWOWY:
1) tworzy specyfikację problemu, proponuje i analizuje jego rozwiązanie
2) formułuje informatyczne rozwiązanie problemu przez dobór
algorytmu oraz odpowiednich struktur danych i realizuje je w wybranym
języku programowania
3) projektuje relacyjne bazy danych i wykorzystuje do ich realizacji
system bazy danych
4) wykorzystuje różnorodne źródła i zasoby informacji do tworzenia
dokumentów tekstowych i multimedialnych
POZIOM ROZSZERZONY:
Jak na poziomie podstawowym oraz
1) projektuje i przeprowadza wszystkie etapy na drodze do otrzymania
informatycznego rozwiązania problemu
2) wykorzystuje metody informatyki w rozwiązywaniu problemów
3) uzasadnia poprawność, złożoność i efektywność rozwiązania problemu
4) projektuje relacyjne bazy danych i proste aplikacje bazodanowe
5) tworzy dokumenty sieciowe i multimedialne z użyciem zaawansowanych
technik, w tym programowania
6) opisuje nowe zastosowania narzędzi informatyki i antycypuje
ich konsekwencje dla życia społecznego,
gospodarczego (korzyści i zagrożenia)