Zadanie 1.1

Wprowadzenie

Z treści zadania dowiadujemy się, że Małgosia zapisała na kartce kilka liczb nieparzystych, a następnie Jaś zapisał kilka liczb parzystych. Liczby te tworzą zbiór liczb, w którym najpierw jest kilka liczb nieparzystych, a później kilka liczb parzystych.

Naszym zadaniem jest stworzenie algorytmu, który znajdzie pierwszą liczbę zapisaną przez Jasia (pierwszą liczbę parzystą). Jednocześnie, aby otrzymać maksymalną liczbę punktów, nasz algorytm musi mieć złożoność czasową lepszą od złożoności liniowej.

Jak się za to zabrać

Aby znaleźć pierwszą liczbę w zbiorze, spełniającą dany warunek musimy skorzystać z algorytmu wyszukiwania.
Istnieją różne algorytmy wyszukiwania, najprostszym sposobem na wyszukiwanie jest wyszukiwanie liniowe - czyli po prostu sprawdzanie każdej liczby po kolei. Niestety wyszukiwanie liniowe, jak sama nazwa wskazuje, jest algorytmem o złożoności liniowej. Za użycie wyszukiwania liniowego za to zadanie otrzymalibyśmy tylko 3 punkty na 5 możliwych.

Aby dostać maksymalne 5 punktów, najprościej jest skorzystać z wyszukiwania binarnego, gwarantującego logarytmiczną złożoność czasową.

Wyszukiwanie binarne jest jednym z algorytmów, które trzeba znać, podchodząc do matury z informatyki.

Rozwiązania w Pythonie

Najpierw przedstawię rozwiązanie o złożoności logarytmicznej, a dalej znajdziecie rozwiązanie za mniej punktów, o złożoności liniowej.

Rozwiązanie o złożoności logarytmicznej (za maksa, 5/5 punktów)

Wyszukiwanie binarne

# dane (są w zadaniu, nie trzeba ich uwzględniać w rozwiązaniu na maturze)
n = 10
A = [None, 5, 99, 3, 7, 111, 13, 4, 24, 4, 8]

# wyszukiwanie binarne
def szukaj_binarnie(A):
    lewy, prawy = 1, n
    while lewy < prawy:
        srodkowy = (lewy+prawy)//2
        if A[srodkowy]%2 != 0:  # jeśli środkowy jest nieparzysty
            lewy = srodkowy + 1
        else:                   # jeśli środkowy jest parzysty
            prawy = srodkowy
    return A[prawy]

Analiza rozwiązania o złożoności logarytmicznej

Przeanalizuję tutaj algorytm dla podanych w zadaniu danych. Wgłębienie się w przebieg algorytmu pozwala zrozumieć jego działanie. Wypisuję kolejno wszystkie istotne operacje zachodzące w algorytmie, jak i stany zmiennych.

Pierwszy przebieg pętli
lewy = 1
prawy = 10
srodkowy = (1+10)//2 => 5
lewy < prawy => True

tablica (pogrubione są lewy, środkowy, prawy):

1	2	3	4	5	6	7	8	9	10
5	99	3	7	111	13	4	24	4	8

środkowy jest nieparzysty, więc lewy = srodkowy+1 => 6

2. przebieg pętli
   lewy = 6
prawy = 10
srodkowy = (6+10)//2 => 8
lewy < prawy => True

tablica (pogrubione są lewy, środkowy, prawy):

1	2	3	4	5	6	7	8	9	10
5	99	3	7	111	13	4	24	4	8

środkowy jest parzysty, więc prawy = srodkowy => 8

3. przebieg pętli
   lewy = 6
prawy = 8
srodkowy = (6+8)//2 => 7
lewy < prawy => True

tablica (pogrubione są lewy, środkowy, prawy):

1	2	3	4	5	6	7	8	9	10
5	99	3	7	111	13	4	24	4	8

środkowy jest parzysty, więc prawy = srodkowy => 7

4. przebieg pętli
   lewy = 6
prawy = 7
srodkowy = (6+7)//2 => 6
lewy < prawy => True

tablica (pogrubione są lewy, środkowy, prawy):

1	2	3	4	5	6	7	8	9	10
5	99	3	7	111	13	4	24	4	8

środkowy jest nieparzysty, więc lewy = srodkowy+1 => 7

5. przebieg pętli
   lewy = 7
prawy = 7
srodkowy = (7+7)//2 => 7
lewy < prawy => False
   Warunek pętli while zwraca fałsz, więc wykonywanie pętli zostaje przerwane i zwrócona zostaje wartość elementu o indeksie prawy z tablicy A, czyli A[prawy].

Rozwiązanie o złożoności liniowej (za 3/5 punktów)

Publikuję 2 warianty rozwiązań, można wybrać dowolne jedno z nich.

# dane (są w zadaniu, nie trzeba ich uwzględniać w rozwiązaniu na maturze)
n = 10
# w zadaniu elementy listy numerowane są od 1 do n,
# więc aby uzyskać ten efekt w Pythonie za zerowy element podstawiam None
A = [None, 5, 99, 3, 7, 111, 13, 4, 24, 4, 8]

# Wariant 1 > bez użycia funkcji
for i in range(1, n):
    if A[i] % 2 == 0:
        print(A[i]) # zwraca 4
        break

# Wariant 2 > z wykorzystaniem funkcji
def szukaj_liniowo(A):
    for i in range(1, n):
        if A[i] % 2 == 0:
            return A[i]
        
print(szukaj_liniowo(A)) # zwraca 4

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).

Ciekawe jest to, że w tym zadaniu wg schematu punktowania zaliczane są algorytmy, które zwracają sam indeks zamiast liczby kryjącej się za danym indeksem.

Zadanie 1.2

Dla wyszukiwania binarnego należało tutaj wpisać: złożoność logarytmiczna lub log(n), dla wyszukiwania liniowego: złożoność liniowa, a dla algorytmu o złożoności pierwiastkowej: złożoność pierwiastkowa.

Schemat punktowania

1 p. – za poprawną odpowiedź.
0 p. – za podanie odpowiedzi błędnej albo brak odpowiedzi.

Linki do arkusza w formacie .pdf ze strony CKE:
CKE Matura z informatyki 2019 - arkusz część I
CKE Matura z informatyki 2019 - zasady oceniania