Zadanie 1.1, matura maj 2019, informatyka rozszerzona

5 pktotwarteśrednie 42%Maj 2019

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ów

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:

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.

Wypróbuj za darmo

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.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.