Zadanie 3, specimen 2015, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Polecenie
9 punktówProgi 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.
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łu | Długość | Liczba progów |
|---|---|---|
| 2, 2, 2 | 3 | 0 |
| 3, 1, 1 | 3 | 1 |
| 3, 3, 1 | 3 | 1 |
| 11, 7, 7, 6 | 4 | 2 |
| 7, 7 | 2 | 0 |
| 9, 9, 7 | 3 | 1 |
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)
poprawne podanie wszystkich wartości.
inna odpowiedź lub brak odpowiedzi.
b)
poprawne napisanie algorytmu.
napisanie algorytmu nieuwzględniającego przypadków brzegowych.
błędny algorytm lub brak odpowiedzi.
c)
poprawne napisanie algorytmu.
napisanie algorytmu, w którym nie uwzględniono progów w schodach do dołu kończących się ostatnim elementem ciągu.
błędny algorytm lub brak odpowiedzi.
d)
poprawne podanie liczby porównań i poprawne uzasadnienie.
poprawne podanie liczby porównań i błędne uzasadnienie lub brak uzasadnienia.
inna odpowiedź lub brak odpowiedzi.