Odpowiedź:
def hanoi(n):
hanoi_recurs(n, 1, 2, 3)
def hanoi_recurs(n, src, mdl, dst):
if n > 0:
hanoi_recurs(n - 1, src, dst, mdl)
print(f"Move ({n}) from {src} to {dst}")
hanoi_recurs(n - 1, mdl, src, dst)
hanoi(3)
Wyjaśnienie:
Żeby zachować zgodność z przykładem, funkcja hanoi(n) z jednym parametrem liczby krążków wywołuje rekurencyjną funkcję hanoi_recurs(n, src, dst, mdl) z czterema argumentami.
Problem ma złożoność wykładniczą:
Wywołanie funkcji hanoi dla kolejnych liczb naturalnych wyświetla liczbę kroków, które należy wykonać do rozwiązania łamigłówki.
Liczby kroków koniecznych do rozwiązania zagadki są o 1 mniejsze od kolejnych potęg liczby 2.
hanoi(1) = 1 czyli [tex]2^{1}-1[/tex]
hanoi(2) = 3 czyli [tex]2^{2}-1[/tex]
hanoi(3) = 7 czyli [tex]2^{3}-1[/tex]
hanoi(4) = 15 czyli [tex]2^4-1[/tex]
hanoi(5) = 31 czyli [tex]2^5-1[/tex]
Możemy zatem przypuszczać, że hanoi(n) = [tex]2^{n}-1[/tex] dla dowolnej liczby krążków n. Złożoność rośnie bardzo szybko wraz ze zwiększaniem liczby krążków.
Bardziej "matematyczne" wyjaśnienie na pewno znajdziesz gdzieś w internecie.