Arkusz i dane
Rozwiązania i zasady oceniania
Python
Dev-C++
Rozwiązanie zadania 2.1.
funkcja strzalka(x, y)
wypisz "(" + x + "→" + y + ")"
funkcja rysuj(x)
jeżeli 2 * x ≤ N
strzalka(x, 2 * x)
rysuj(2 * x)
jeżeli 2*x + 1 ≤ N
strzalka(x, 2 * x + 1)
rysuj(2*x + 1)
N ← 10
rysuj(1)
Wynik (z interpretera pseudokodu):
(1→2) (2→4) (4→8) (4→9) (2→5) (5→10) (1→3) (3→6) (3→7)
Wynik (CKE)
1
↙ ↘
2 3
↙ ↘ ↙ ↘
4 5 6 7
↙ ↘ ↙
8 9 10
Rozwiązanie zadania 2.2.
a) Dla N = 20 funkcja rysuj(1) narysuje 19 strzałek. Można to zobaczyć, analizując jakie strzałki zostaną narysowane dla każdego wywołania funkcji rysuj(x):
- rysuj(1) narysuje strzałkę od punktu 1 do punktu 2 oraz wywoła rysuj(2)
- rysuj(2) narysuje strzałkę od punktu 2 do punktu 4 oraz wywoła rysuj(4)
- rysuj(4) narysuje strzałkę od punktu 4 do punktu 8 oraz wywoła rysuj(8)
- rysuj(8) nie wykona się, ponieważ 28=16 < 20, ale 28+1=17 > 20, więc funkcja nie wykona się dla x=8
- Po powrocie do rysuj(4) funkcja narysuje strzałkę od punktu 4 do punktu 9 oraz wywoła rysuj(9)
- rysuj(9) nie wykona się, ponieważ 29=18 < 20, ale 29+1=19 < 20, więc funkcja narysuje strzałkę od punktu 9 do punktu 19 oraz wywoła rysuj(19)
- rysuj(19) nie wykona się, ponieważ 2*19=38 > 20, więc funkcja nie wykona się dla x=19
Zatem w sumie zostanie narysowanych 19 strzałek.
b) Dla dowolnego N funkcja rysuj(1) narysuje N-1 strzałek. Można to zobaczyć, analizując podobnie jak dla N=20, jakie strzałki zostaną narysowane dla każdego wywołania funkcji rysuj(x). W każdym kroku funkcja narysuje dokładnie jedną strzałkę, więc w sumie zostanie narysowanych N-1 strzałek.
Możemy prześledzić, jakie punkty są połączone ze sobą strzałkami w kolejnych krokach, zaczynając od punktu 1 i poruszając się zgodnie ze zwrotem strzałek. W każdym kroku będziemy przeskakiwać z punktu o numerze x do punktu o numerze 2x, jeśli 2x ≤ N, lub do punktu o numerze 2x+1, jeśli 2x+1 ≤ N.
Rozwiązanie zadania 2.3.
Zaczynamy od punktu 1.
Następnie idziemy strzałką do punktu 2.
Z punktu 2 idziemy strzałką do punktu 4.
Z punktu 4 idziemy strzałką do punktu 8.
Z punktu 8 idziemy strzałką do punktu 16.
Z punktu 16 idziemy strzałką do punktu 32.
Z punktu 32 idziemy strzałką do punktu 64.
Z punktu 64 idziemy strzałką do punktu 128.
Z punktu 128 idziemy strzałką do punktu 256.
Z punktu 256 idziemy strzałką do punktu 512.
Z punktu 512 idziemy strzałką do punktu 1024.
Z punktu 1024 idziemy strzałką do punktu 2048, ale punkt ten nie należy już do zbioru punktów o numerach 1, 2, ..., N. Zatem kończymy naszą drogę na punkcie 1024.
Widzimy więc, że musimy przejść przez 10 strzałek, żeby dotrzeć z punktu o numerze 1 do punktu o numerze N, jeśli będziemy się przemieszczać zgodnie z ich zwrotami.