Matura informatyka 2020: Zadanie 2. Symetryczny ciąg - rozwiązanie
Zadanie 2.1
Przykład
Przykładowo rozpiszę działanie funkcji sym na danych z pierwszego wiersza tabeli - dla a = 3
i b = 1
:
sym(3, 1)
3 ≠ 0
sym(2, 2)
2 ≠ 0
sym(1, 3)
1 ≠ 0
sym(0, 4)
0 = 0
wypisz 3 (bo 1*3)
sym(0, 4)
0 = 0
wypisz 4 (bo 2*2)
sym(1, 3)
jw.
wypisz 3 (bo 3*1)
sym(2, 2)
jw.
Pozwoliłem tu sobie wpisać jw. w miejsce funkcji, których rezultat już znamy bo wcześniej wyznaczyliśmy ich rezultat - funkcje te są deterministyczne, co oznacza, że dla takich samych argumentów zwracają takie same wyniki ;)
Niedeterministyczne byłyby wtedy, gdyby coś na nie wpływało z zewnątrz, gdyby korzystały one z danych spoza funkcji, które mogłyby ulec zmianie.
Wystarczy teraz od góry do dołu odczytać wynik czyli kolejne liczby wypisywane za pomocą procedury wypisz: 3 4 3 3 3 4 3
Wszystko się zgadza.
a = 3, b = 3
sym(3, 3)
3 ≠ 0
sym(2, 4)
2 ≠ 0
sym(1, 5)
1 ≠ 0
sym(0, 6)
0 = 0
wypisz 5 (bo 1*5)
sym(0, 6)
0 = 0
wypisz 8 (bo 2*4)
sym(1, 5)
jw.
wypisz 9 (bo 3*3)
sym(2, 4)
jw.
Odpowiedź: 5 8 5 9 5 8 5
a = 4, b = 1
sym(4, 1)
4 ≠ 0
sym(3, 2)
3 ≠ 0
sym(2, 3)
2 ≠ 0
sym(1, 4)
1 ≠ 0
sym(0, 5)
0 = 0
wypisz 4 (bo 1*4)
sym(0, 5)
0 = 0
wypisz 6 (bo 2*3)
sym(1, 4)
jw.
wypisz 6 (bo 3*2)
sym(2, 3)
jw.
wypisz 4 (bo 4*1)
sym(3, 2)
jw.
Odpowiedź: 4 6 4 6 4 6 4 4 4 6 4 6 4 6 4
Zadanie 2.2
Aby wykonać to zadanie, należy przeanalizować długości ciągów otrzymanych w zadaniu 2.1, celowo je tam dopisałem na szaro.
Można zauważyć, że długość ciągu jest zależna bezpośrednio od argumentu a.
Dlaczego tak się dzieje? I jak poznać długość ciągu?
Wywołania rekurencyjne można zobrazować w postaci drzew. Procedura sym wywołuje samą siebie za każdym razem dwukrotnie, zatem z każdego węzła będą wychodziły 2 gałęzie. Spróbujmy to rozrysować, np. dla a = 3
:
sym(3, b)
/ \
sym(2, b+1) sym(2, b+1)
/ \ / \
sym(1, b+2) sym(1, b+2) sym(1, b+2) sym(1, b+2)
Każde wywołanie funkcji sym, gdzie a > 0, skutkuje wypisaniem jednej liczby.
Zatem łatwo zauważyć - skoro drzewo ma 7 węzłów, to wypisanych zostanie 7 liczb.
a = 3 - wysokość drzewa wynosi 3, wierzchołków jest 7
a = 4 - wysokość drzewa wynosi 4, wierzchołków jest 15
Na każdym poziomie drzewa rozgałęzienia są dwa, zatem wzór na ilość węzłów w drzewie będzie równy 2^a-1, gdzie a to wysokość drzewa.
Dla bardziej zainteresowanych: jest to drzewo binarne pełne, zachęcam do wygooglowania ;)
Odkrywając ten wzór, możemy łatwo wyliczyć odpowiedzi.