Zadanie 2. Długość napisów binarnych (7 pkt.)

Treść zadania

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\left(n\right)$

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·sklej(n:2)$.

Krok 3. Jeśli $n$ jest nieparzysta, to wynikiem jest $n-1+sklej\left(\right(n-1):2)+sklej\left(\right(n+1):2)$.

b) Uzupełnij tabelę, podając wartości funkcji sklej dla wskazanych argumentów.

Przykładowe rozwiązanie:

Obliczmy kolejne wartości podane w tabeli.

$sklej\left(3\right)=3-1+sklej\left(\frac{(3-1)}{2}\right)+sklej\left(\frac{(3+1)}{2}\right)=$

$=2+sklej\left(1\right)+sklej\left(2\right)=2+0+1=3$

$sklej\left(4\right)=4-1+2·sklej\left(\frac{4}{2}\right)=3+2·sklej\left(2\right)=$

$=3+2·1=3+2=5$

$sklej\left(5\right)=5-1+sklej\left(\frac{(5-1)}{2}\right)+sklej\left(\frac{(5+1)}{2}\right)=$

$4+sklej\left(2\right)+sklej\left(3\right)=4+1+3=8$

$sklej\left(6\right)=6-1+2·sklej\left(\frac{6}{2}\right)=5+2·sklej\left(3\right)=$

$=5+2·3=5+6=11$

Schemat oceniania

Poprawna odpowiedź

2 pkt – za poprawne uzupełnienie wartości funkcji w tabeli

1 pkt – za uzupełnienie wartości funkcji w tabeli z jednym błędem

0 pkt – za wypełnioną tabelę z więcej niż jednym błędem albo brak odpowiedzi

Zwróćmy uwagę na schemat oceniania w tym zadaniu. Za prawidłowo wypełnioną tabelę uzyskamy 2 punkty. Gdy jedna z wartości będzie błędna, otrzymamy 1 punkt. Z tego powodu zawsze warto sprawdzić poprawność otrzymywanych wyników.

Problem 1

Przeanalizuj działanie funkcji sklej(n), a następnie rozwiąż zadanie.

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·sklej(n:2)$.

Krok 3. Jeśli $n$ jest nieparzysta, to wynikiem jest $n-1+sklej\left(\right(n-1):2)+sklej\left(\right(n+1):2)$.

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. Rysunek przedstawia takie drzewo dla wywołania sklej(5).

R18Z466M24X17

Ilustracja przedstawia schemat blokowy.
1: sklej(5), 2: strzałka w lewo: sklep (2), 3: Strzałka w dół: sklej (1), 2: strzałka w prawo: sklej (3), 3: strzałka w lewo: sklej (1), 3: strzałka w prawo: sklej (2), 4: strzałka w dół: sklej (1).