Prezentacja multimedialna
Zadanie 2. Ulubione liczby
Małgosia i Jaś lubią liczby. Małgosia lubi liczby nieparzyste, a Jaś lubi liczby parzyste. Każde z dzieci zapisało po kilka spośród swoich ulubionych liczb na jednej wspólnej kartce. Najpierw Małgosia zapisała wszystkie swoje liczby, a potem Jaś dopisał swoje.
Napisz algorytm (w postaci listy kroków, w pseudokodzie lub w wybranym języku programowania), który dla danego ciągu liczb zapisanych przez dzieci znajdzie pierwszą liczbę zapisaną przez Jasia. Zakładamy, że każde z dzieci zapisało co najmniej jedną liczbę.
Przy ocenie będzie brana pod uwagę złożoność czasowa Twojego algorytmu. Maksymalną liczbę punktów uzyskasz za algorytm o złożoności lepszej niż liniowa.
Uwaga: W zapisie algorytmu możesz wykorzystać tylko operacje arytmetyczne (dodawanie, odejmowanie, mnożenie, dzielenie, dzielenie całkowite, reszta z dzielenia), instrukcje porównania, instrukcje sterujące i przypisania do zmiennych lub samodzielnie napisane funkcje, wykorzystujące wyżej wymienione operacje.
Specyfikacja problemu:
Dane:
n
– liczba całkowita większa od 1A[0..n - 1]
– tablica zawierająca ciąg n liczb zapisanych przez dzieci (najpierw wszystkie liczby nieparzyste, a potem wszystkie liczby parzyste)
Wynik:
w
– pierwsza od lewej parzysta liczba w tablicyA
Dane:
n = 10
A = {5, 99, 3, 7, 111, 13, 4, 24, 4, 8}
Wynik:
w = 4
Rozwiąż zadanie, wykorzystując jeden z języków programowania: C++, Java lub Python. Działanie programu przetestuj dla danych z Przykładu 1.
Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i pojawiło się na egzaminie maturalnym z informatyki w 2019 roku (zadanie 1, poziom rozszerzony, egzamin w tzw. starej formule). Cały arkusz można znaleźć na stronie internetowej CKE.
Porównaj swoje rozwiązanie z przedstawionym w prezentacji.
Algorytm wyszukiwania binarnego w wersji rekurencyjnej omawiamy w e‑materiale Rozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj”Rozwiązywanie problemów informatycznych – strategia „dziel i zwyciężaj”.
Dodaj do swojego programu komentarze tak, żeby był zrozumiały dla osoby, która nie potrafi programować.