Zadanie 3, specimen 2015, informatyka rozszerzona

9 pktotwartetrudne (szac.)Specimen 2015

Darmowe konto pozwoli wrócić do niego później.

Zadanie

Polecenie

9 punktów

Progi i schody

W ciągu liczb naturalnych, parę sąsiednich liczb nazywamy progiem, jeśli następna liczba jest mniejsza od poprzedniej.

W ciągu liczb naturalnych, schodami do dołu nazywamy każdy jego podciąg kolejnych elementów, złożony z przynajmniej dwóch liczb, w którym każda liczba poza pierwszą nie jest większa od poprzedniej, a samego podciągu nie można rozszerzyć w żadną stronę do innych schodów do dołu. Długością schodów do dołu nazywamy liczbę zawartych w nim elementów.

Przykład:

Ciąg: 3, 7, 7, 6, 5, 4, 4, 4, 5 zawiera schody do dołu 7, 7, 6, 5, 4, 4, 4 o długości 7. Te schody zawierają 3 progi: pierwszy to 7 i 6, drugi to 6 i 5, trzeci to 5 i 4.

a) Dla następującego ciągu liczb: 2, 2, 2, 3, 1, 1, 3, 3, 1, 10, 11, 7, 7, 6, 7, 7, 8, 9, 9, 7 wypisz kolejno wszystkie występujące w nim schody do dołu i obok każdych schodów podaj jego długość i liczbę zawartych w nim progów.1 punkt

b) Rozważmy następującą specyfikację:2 punkty

Dane: dodatnia liczba całkowita n oraz tablica a[1..n] zawierająca n-elementowy ciąg liczb całkowitych a[1], …, a[n]

Wynik: liczba całkowita liczba_progów – liczba wszystkich progów w ciągu zapisanym w tablicy a

W wybranej przez siebie notacji (schemat blokowy, lista kroków, wybrany przez Ciebie język programowania) opracuj algorytm zgodny z powyższą specyfikacją.

c) Rozważmy następującą specyfikację:4 punkty

Dane: dodatnia liczba całkowita n oraz tablica a[1..n] zawierająca n-elementowy ciąg liczb całkowitych a[1], …, a[n]

Wynik: liczba całkowita najw_liczba_progów – największa liczbę progów w schodach do dołu z ciągu zapisanego w tablicy a

W wybranej przez siebie notacji (schemat blokowy, lista kroków, wybrany przez Ciebie język programowania) opracuj algorytm zgodny z powyższą specyfikacją.

d) Podaj, ile dokładnie porównań między elementami ciągu danych wykona w pesymistycznym przypadku Twój algorytm z punktu c). Odpowiedź uzasadnij.2 punkty

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

a)

Schody do dołuDługośćLiczba progów
2, 2, 230
3, 1, 131
3, 3, 131
11, 7, 7, 642
7, 720
9, 9, 731

b)

```pascal

liczba_progów := 0;

for i := 1 to n-1 do

if a[i] > a[i+1] then liczba_progów := liczba_progów + 1;

```

c)

```pascal

najw_liczba_progów := 0;

liczba_progów_w_schodach := 0;

for i := 1 to n-1 do

if a[i] < a[i+1] then

{* a[i+1] może być początkiem nowych schodów *}

begin

if liczba_progów_w_schodach > najw_liczba_progów then

najw_liczba_progów := liczba_progów_w_schodach;

liczba_progów_w_schodach := 0

end

else

if a[i] > a[i+1] then

liczba_progów_w_schodach := liczba_progów_w_schodach + 1;

if liczba_progów_w_schodach > najw_liczba_progów then

najw_liczba_progów := liczba_progów_w_schodach;

```

d) W pesymistycznym przypadku w każdym obrocie pętli wykonywane są dwa porównania: pierwsze służy do wykrycia nowych schodów, a drugie do identyfikacji progu. Zatem w pesymistycznym przypadku algorytm wykona dokładnie 2(n − 1) porównań.

Schemat punktowania

a)

1 pkt

poprawne podanie wszystkich wartości.

0 pkt

inna odpowiedź lub brak odpowiedzi.

b)

2 pkt

poprawne napisanie algorytmu.

1 pkt

napisanie algorytmu nieuwzględniającego przypadków brzegowych.

0 pkt

błędny algorytm lub brak odpowiedzi.

c)

4 pkt

poprawne napisanie algorytmu.

2 pkt

napisanie algorytmu, w którym nie uwzględniono progów w schodach do dołu kończących się ostatnim elementem ciągu.

0 pkt

błędny algorytm lub brak odpowiedzi.

d)

2 pkt

poprawne podanie liczby porównań i poprawne uzasadnienie.

1 pkt

poprawne podanie liczby porównań i błędne uzasadnienie lub brak uzasadnienia.

0 pkt

inna odpowiedź lub brak odpowiedzi.

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.