dlamaturzysty.info

zadania z informatyki - Analiza algorytmów

przedmiot: informatyka

Przykłady zadań rozwiązywanych na maturze bez użycia komputera.
Liczba zadań: 10. Liczba pytań: 35.

Zadania dostępne także w aplikacji Matura - testy i zadania, gdzie mogliśmy wprowadzić dodatkowe funkcje, np: dodawanie do powtórek, zapamiętywanie postępu nauki czy notatnik.
google_play_h56.png app_store_h56.png
Dziękujemy także developerom z firmy Geeknauts, którzy stworzyli tę aplikację

Zadanie: 1 2 3 4 5 6 7 8 9 10
Zadanie 1.
Wiązka zadań Ciągi rekurencyjne

Dana jest następująca funkcja rekurencyjna:

funkcja wynik( i )
jeżeli i < 3
zwróć 1 i zakończ;
w przeciwnym razie
jeżeli i mod 2 = 0
zwróć wynik(i – 3) + wynik(i – 1) + 1
w przeciwnym razie
zwróć wynik(i – 1) mod 7

Uwaga: Operator mod oznacza resztę z dzielenia.
Zadanie 1.1.
Uzupełnij poniższą tabelę:
iwynik(i)
21
3
4
5
6
7
8
Zadanie 1.2.

Wykonaniem elementarnym nazywać będziemy wykonanie wynik(0), wynik(1) lub wynik(2). Natomiast złożonością elementarną wynik(i) nazywamy liczbę wykonań elementarnych będących efektem uruchomienia wynik(i). Złożoność elementarną wynik(i) oznaczamy przez E(i).

Na przykład złożoność elementarna wynik(4) wynosi E(4) = 2, ponieważ wykonując wynik(4), wywołamy wynik(3) i wynik(1) (wykonanie elementarne), a z kolei przy wykonaniu wynik(3) wywołamy wynik(2) (drugie wykonanie elementarne).

Uzupełnij poniższą tabelę:

i

E(i)

0

1

3

1

5


7


9


10



Okazuje się, że E(i) można opisać rekurencyjnym wyrażeniem, którego niekompletną postać podajemy poniżej. Uzupełnij brakujące miejsca tak, aby E(i) dawało poprawną złożoność elementarną wynik(i) dla każdego całkowitego nieujemnego i.

E(0) = E(1) = E(2) = 1

E(i) = E(....................) + E(....................) dla parzystego i > 2

E(i) = E(....................) dla nieparzystego i > 2

Zadanie 1.3.
Naszym celem jest wyznaczenie największej liczby spośród wartości funkcji wynik(0), wynik(1),...,wynik(1000) bez konieczności rekurencyjnego wyznaczania kolejnych wartości. Poniżej prezentujemy niekompletny algorytm realizujący to zadanie.

W[0] ← 1
W[1] ← 1
W[2] ← 1
max_wart ← 1
dla i = 3, 4, ..., 1 000 wykonuj
jeżeli i mod 2 = 0
W[i] ← ..................................................................
w przeciwnym razie
W[i] ← ...................................................................
jeżeli W[i] > max_wart
....................................................................
zwróć max_wart

Uzupełnij brakujące miejsca w algorytmie tak, aby zwracał on największą liczbę spośród wynik(0), wynik(1),...,wynik(1000).
Następna strona

źródło: CKE
Polityka Prywatności