zadania z informatyki - Analiza algorytmów

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

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