Zadanie: Matura CKE Maj 2011 (Informatyka Rozszerzona)

Question

Zadanie 1. Długość napisów binarnych (7 pkt)
Opisana poniżej funkcja rekurencyjna wyznacza, dla liczby naturalnej $n > 0$, długość napisu uzyskanego przez sklejenie binarnych reprezentacji liczb naturalnych od $1$ do $n - 1$.

Funkcja $sklej(n)$
krok 1. jeśli $n = 1$, to podaj 0 jako wynik i zakończ działanie
krok 2. jeśli $n$ parzysta, to wynikiem jest $n - 1 + 2 \cdot sklej(n / 2)$
krok 3. jeśli $n$ nieparzysta, to wynikiem jest $n - 1 + sklej((n - 1) / 2) + sklej((n + 1) / 2)$ Pytanie 1: a) Wykonanie funkcji sklej można przedstawić w postaci drzewa wywołań rekurencyjnych ilustrującego wszystkie wywołania funkcji po jej uruchomieniu dla zadanego argumentu. Poniższy rysunek przedstawia takie drzewo dla wywołania $sklej(5)$.

[img1]
Narysuj analogiczne drzewo dla wywołania $sklej(7)$.
[odp_graficzna1] Pytanie 2: b) Uzupełnij poniższą tabelę, podając wartości funkcji sklej dla wskazanych argumentów.

$n$$sklej(n)$
10
21
3[odp_tab1]
4[odp_tab2]
5[odp_tab3]
6[odp_tab4] Pytanie 3: c) Chcemy wypełnić tablicę $s[1..n]$ w taki sposób, że $s[i] = sklej(i)$ dla każdego $1 \le i \le n$.
Podaj algorytm wypełniający tablicę $s$ odpowiednimi wartościami bez wywoływania funkcji sklej, tzn. bez użycia rekurencji. Zauważ, że jeśli poprawnie wyliczone są już wartości $s[1], ..., s[i - 1]$, to można z nich skorzystać przy wyznaczaniu $s[i]$.
Zapisz swój algorytm w postaci listy kroków, schematu blokowego lub w wybranym języku programowania, który wybrałeś/aś na egzamin.

Specyfikacja:
Dane: liczba naturalna $n > 0$
Wynik: tablica $s[1..n]$ o wartościach $s[i] = sklej(i)$, dla $1 \le i \le n$
Algorytm:
[odp_otwarta1]

Instytut Maturalny · Accepted Answer

Sprawdź pełne rozwiązanie na stronie Instytutu Maturalnego.

$n$	$sklej(n)$
1	0
2	1
3	........
4	........
5	........
6	........

Zobacz również podobne zadania

Chcesz zobaczyć więcej rozwiązań z przedmiotu Informatyka Rozszerzona?