16380 zdj0 (3)

Problem wież Hanoi

Ile przestawień wykona algorytm by przestawić n krążków?

• a_n - liczba przestawień n krążków.

Równanie rekurencyjne:

^ai = ¹

^an*1 = ^an ^{+ 1 + 3}n = ^2an ^{+ 1}

Rozwiązanie: a_n = 2ⁿ - 1.

Dowód indukcyjny. Dla n = 1.2¹ 1=1= a₁. Załóżmy, że a_n = 2ⁿ 1. Wtedy

a_n+1 = 2a_n + 1 = 2(2ⁿ - 1) + 1 = 2ⁿ⁺¹ - 2 + 1 = 2ⁿ⁺¹ - 1

Liczba przestawień jest proporcjonalna do ilości wszystkich operacji

wykonywanych przez algorytm. Zatem cały algorytm działa w czasie

Proaainow.uiie komputeiou I

32