Wskazówka:
Działanie wieże(3, A, B, C) opiszemy przy pomocy tak zwanego drzewa wywołań rekurencyjnych. W drzewie tym zapisywać będziemy wszystkie wywołania funkcji wieże będące
wynikiem uruchomienia wieże(3, A, B, C). Wywołania wieże(i, x, y, z) i wieże(i’, x’, y’, z’)
połączymy skierowaną krawędzią, jeśli w treści wieże(i, x, y, z) następuje wywołanie wieże(i’,
x’, y’, z’). Na przykład prowadzimy krawędź od wieże(3, A, B, C) do wieże(2, C, B, A), gdyż
wykonanie wieże(3, A, B, C) powoduje wywołanie wieże(2, C, B, A) (jest to wywołanie
z ostatniego wiersza: wieże(n – 1, z, y, x)). Poniżej prezentujemy pełne drzewo wywołań rekurencyjnych dla wieże(3, A, B, C).
W efekcie uzyskujemy następujące rozwiązanie zadania:
|
n |
x |
y |
z |
|
3 |
A |
B |
C |
|
2 |
A |
C |
B |
|
1 |
A |
B |
C |
|
1 |
B |
C |
A |
|
2 |
C |
B |
A |
|
1 |
C |
A |
B |
|
1 |
A |
B |
C |