Darmowe konto pozwoli wrócić do niego później.
Polecenie
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.
Darmowe konto pozwoli wrócić do niego później.
a) Dla następującego ciągu liczb: 2, 2, 2, 3, 1, 1, 3, 3, 1, 10, 11, 7, 7, 6, 5, 4, 4, 4, 5, 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.
b) Rozważmy następującą specyfikację:
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ę:
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.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.
a) Schody do dołu w ciągu 2, 2, 2, 3, 1, 1, 3, 3, 1, 10, 11, 7, 7, 6, 5, 4, 4, 4, 5, 9, 9, 7:
2, 2, 2 – długość 3, 0 progów
3, 1, 1 – długość 3, 1 próg
3, 3, 1 – długość 3, 1 próg
11, 7, 7, 6, 5, 4, 4, 4 – długość 8, 2 progi
9, 9, 7 – długość 3, 1 próg
b) 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) 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
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
a) 1 pkt – poprawne podanie wszystkich wartości
b) 2 pkt – poprawne napisanie algorytmu; 1 pkt – napisanie algorytmu nieuwzględniającego przypadków brzegowych
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
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
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ń.