4962385662

2.5 Wieże Hanoi

ABC

Problem wież Hanoi. Przenieść pojedynczo n krążków z wieży A na wieże B używając wieży C tak by nigdy krążek większy nie leżał na mniejszym.

Opis algorytmu. Aby przenieść n krążków z A na B przez C

1.    przenieś n — 1 krążków z A na C używając B;

2.    przenieś krążek z A na B;

3.    przenieś n — 1 krążków z C na B używając A.

Zapis algorytmu.

procedura przenieś(m,X,Y,Z); {przenosi krążki z X na Y używając Z} jeśli m=l to przestaw(X,Y)

w przeciwnym przypadku przenies(m-l,X,Z,Y); przestaw(X,Y) przenies(m-l,Z,Y,X);

przenieś(n,A,B,C) {wywołanie początkowe}

Przykład, n = 3. ...

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

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

Równanie rekurencyjne:

f ai = l

( fln+l = Q,_n + 1 + O-n = 2a_n + 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 0(2ⁿ).

2.6 Wyszukiwanie słowa w słowniku

Problem wyszukiwania słowa w słowniku.

•    Dane wejściowe: liczba naturalna n i ciąg słów W\,... ,w_n uporządkowany w porządku leksykograficznym (alfabetycznym) oraz słowo w.

7