Hanoi. Trivial: Zadanie dla ICSP: Ile ruchów potrzeba, aby rozwiązać wieżę Hanoi o n krążkach?

ICSP: co to wieża Honoi

Trivial: Mamy trzy drążki: na jednym jest ułożonych n kółek o różnych średnicach (w kolejności od największej średnicy na dole do najmniejszej na górze). Trzeba przełożyć wszystkie krążki na inny drążek przy zasadach: nie można kłaść większego kółka na mniejsze i wolno przenosić tylko jeden krążek na raz.

ICSP: hmm pomyśle nad tym jak wrócę

Trivial: Tylko nie patrz na Wikipedii, bo jest tam rozwiązane.

Pestek: Ktoś z was wybiera się na informatykę? Zdawaliście na maturze infę? Nie miałeś w liceum ICSP wież Hanoi?

ICSP: Niestety nie miałem. Jak na razie udało mi się zauważyć że dla 1 kółka wystarczy przełożyć raz dwa dwóch kółek 3 razy a dla trzech kółek 13 razy. Mam rację?

ICSP: tak więc 1,3,7,15 − to są 4 pierwsze najszybsze możliwości różnica miedzy nimi to 2,4,8 czyli kolejne potęgi liczby 2 dla n=1 otrzymujemy 1 dla n = 2 otrzymujemy 3 = 1 + 2¹ dla n = 3 otrzymujemy 7 czyli 3 + 2² dla n = 4 otrzymuje 15 czyli 7 + 2³ zakładam że będzie to ciąg rekurencyjny a₁ = 1 a_n = a_n−1 + 2ⁿ⁻¹ Dobrze myślę?

Jack: podaj jeszcze wzór nierekurencyjny

ICSP: 2ⁿ − 1?

Jack: troszkę głupie pytanie... masz rację. Myślałem że będziesz musiał przekształcić wzór rekurencyjny

ICSP: nie umiem przekształcać wzoru rekurencyjnego. Muszę zgadywać

Trivial: Wzór rekurencyjny zły, jawny dobrze. Sposób rozwiązania: Aby przenieść n elementów musimy najpierw przenieść n−1 górnych elementów na drugi drążek, potem ostatni element na trzeci krążek i znów n−1 elementów na trzeci krążek. Mamy więc: H_n = H_n−1 + 1 + H_n−1 H_n = 1 + 2H_n−1, przy warunku początkowym: H₁ = 1. Rozwijamy rekurencję i gotowe: H_n = 1 + 2(1 + 2H_n−2) = 1 + 2 + 2²H_n−2 = 1 + 2 + 2² + 2³H_n−3 = = 1 + 2 + 2² + 2³ + ... + 2^k−1 + 2^kH_n−k. Niech n−k = 1, wtedy:

	2n−1+1−1
Hn = 1 + 2 + 22 + 23 + ... + 2n−2 + 2n−1H1 =		= 2n−1.
	2−1

Trivial: na trzeci drążek*

Trivial: Tzn. Twój wzór rekurencyjny jest OK, tyle tylko, że wziął się trochę z kosmosu.

tn: @Trivial zapodaje zadania informatyczne

Trivial: Czy ja wiem. Problem wież Hanoi to zagadnienie matematyki dyskretnej.

tn: ale popularne w informatyce

ICSP: trochę z kosmosu? Po dogłębnej analizie problemu zadania udało mi się dojść do wniosków z których wyłonił się właśnie ten genialny wzór.