Zadanie 2.1

Zadanie 2. Symetryczny ciąg. Argumentami procedury sym(a, b) są dwie nieujemne liczby całkowite a i b. Wywołanie tej procedury spowoduje wypisanie pewnego ciągu liczb całkowitych. Zadanie 2.1. (0-2) Uzupełnij tabelę - podaj wynik działania procedury sym(a, b) dla wskazanych argumentów a i b.

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.1. Tabelka z rozwiązaniem

Zadanie 2.2

Zadanie 2.2. (0-3) Uzupełnij tabelę - podaj długość ciągu liczbowego otrzymanego w wyniku wywołania procedury sym(a, b) dla wskazanych argumentów a i b.
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.
Zadanie 2.2. Tabelka z rozwiązaniem