Zadanie 1.1, matura maj 2019, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. 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.
Polecenie
5 punktówNapisz 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:
Dane:
n – liczba całkowita większa od 1
A[1..n] – 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 tablicy A
Przykład:
```
Dane:
n = 10
A[1..n] = {5, 99, 3, 7, 111, 13, 4, 24, 4, 8}
Wynik:
w = 4
```
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
Algorytm o złożoności logarytmicznej – wyszukiwanie binarne (w języku c++)
```
p ← 1
k ← n
dopóki p < k wykonuj
s ← (p + k) div 2
jeżeli (A[s] mod 2 = 1)
p ← s + 1
w przeciwnym przypadku
k ← s
w ← A[p]
```
Algorytm o złożoności logarytmicznej – wyszukiwanie binarne (w języku Python)
```
def szukaj_bin(A):
lewy, prawy = 1, n
while lewy < prawy:
środkowy = (lewy + prawy) // 2
if A[środkowy] % 2 != 0:
lewy = środkowy + 1
else:
prawy = środkowy
return prawy
```
Algorytm o złożoności liniowej – wyszukiwanie liniowe
```
p ← 1
dopóki A[p] mod 2 = 1 wykonuj
p ← p + 1
w ← A[p]
```
Algorytm o złożoności pierwiastkowej (z poprawionymi warunkami brzegowymi):
```
int pier(int n) {
int i = 1;
while (i < n / i) i++;
if (i > n / i) i--;
return i;
}
int wyszukiwanie() {
int p = pier(n);
int i = p;
while (A[i] % 2 != 0) {
if (p > n - i) i = n;
else i += p;
}
while (i > 1 && A[i - 1] % 2 == 0) i--;
return i;
}
w = A[wyszukiwanie()];
```
Schemat punktowania
5 p. – za poprawny algorytm o złożoności czasowej lepszej niż liniowa, w tym:
1 p. – prawidłowy warunek pętli,
1 p. – prawidłowe wyznaczenie podziału ciągu liczb,
1 p. – prawidłowe wyznaczenie początku podciągu liczb,
1 p. – prawidłowe wyznaczenie końca podciągu liczb,
1 p. – prawidłowe wyznaczenie pierwszego elementu parzystego w A[] (lub jego indeksu).
3 p. – za poprawny algorytm o złożoności czasowej liniowej, w tym:
1 p. – za prawidłowy przebieg pętli,
1 p. – za sprawdzenie warunku (parzystości liczby),
1 p. – prawidłowe wyznaczenie pierwszego elementu parzystego w A[] (lub jego indeksu).
0 p. – za podanie odpowiedzi błędnej albo brak odpowiedzi. Uwaga: Za każde inne poprawne rozwiązanie o złożoności lepszej niż liniowa przyznajemy maksymalnie 5 punktów, a o złożoności liniowej – maksymalnie 3 punkty.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.
Komentarz. Za każde inne poprawne rozwiązanie o złożoności lepszej niż liniowa przyznajemy maksymalnie 5 punktów, a o złożoności liniowej – maksymalnie 3 punkty.