SZUKAJ NA TYM BLOGU

Zadanie 1. Ulubione liczby (0–6) ()

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.

Zadanie 1.1. (0–5)

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

Zadanie 1.2. (0–1)

Podaj, jaką złożoność czasową – kwadratową, liniową, logarytmiczną lub inną (napisz jaką) – ma Twój algorytm.


 Przykładowe rozwiązanie

Przykładowe rozwiązania (poprawione) [2]

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]

Uwaga: Można pominąć zmienną k.
 

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 = A[środkowy]
  return prawy
w = szukaj_bin(A)

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 do poprawy

int pier(int n) {
  int i = 1;
  while(i * i < n) i = i + 1;
  if(i * i > n) i = i - 1;
  return i;
}
int wyszukiwanie(){
  int p = pier(n) - 1;
  int i = p;
  while(i < n) {
    if(A[i] % 2 == 0){
      int j = i;
      while(A[j] % 2 == 0) j--;
      return j + 1;
    }
  if(i + p > n) i = n - 1;
  i = i + p;
  }
}
w = A[wyszukiwanie()];

Przykład 3. o złożoności liniowej (w języku c++) [3]

for(int i = 1; i < n; i = i + 1) {
  if(A[i] % 2 == 0) {
    w = A[i];
    break;
  }
}

Uwagi: Zamieniono operatory złożone.

Poziom wykonania zadania: 1.1. - 42%; 1.2. - 59%;

Przypisy

  1. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2019/formula_od_2015/informatyka/MIN-R1_1P-192.pdf
  2. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2019/formula_od_2015/Zasady_oceniania/MIN-R2_1P-192_model.pdf
  3. https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Informacje_o_wynikach/2019/sprawozdanie/Sprawozdanie%202019%20-%20Informatyka.pdf

Przykład

Algorytm o złożoności logarytmicznej – wyszukiwanie binarne (w języku c++)

#include <iostream>
using namespace std;
int main() {
int n = 10;
int A[] = {5, 99, 3, 7, 111, 13, 4, 24, 4, 8};
int p = 1;
while (p < n) {
  int s = (p + n) / 2;
  if (A[s] % 2 == 1) {
    p = s + 1;
  }
  else {
    n = s;
  }
}
int w = A[p];
    cout << w;
    return 0;
}

Ćwiczenia

  1. Sprawdź działanie algorytmów w Code::Blocks
  2. Zmień kody na pseudokody

Wskazówka
Algorytm o złożoności liniowej – wyszukiwanie liniowe w C++

int p = 1;
while (A[p] % 2 == 1) {
  p = p + 1;
}
int w = A[p];