Wieże Hanoi ♊: Takie zadanie na rozruszenie licealistów i nie tylko W świątyni w Brahmie są trzy słupy. Na pierwszym z nich znajdują się 64 złote krążki. Krążki ułozone są kolejno według wielkości, najmniejszy znajduje się na samym dole. Zadaniem mnichów ze świątyni jest przestawienie wszystkich krażków na trzeci słup. Mnich może jednorazowo przestawić jeden krażek. Zajmuje mu to jedną sekundę. Tylko jeden mnich może przestawiać krążki w jednym czasie. Nie może zdarzyć się taka sytuacja, że krążek większy znajdzie się nad krążkiem mniejszym. Według legendy kiedy wszystkie krążki znajdą się na ostatnim słupku nastąpi koniec świata. Po jakim czasie od rozpoczecia przestawiania krążków nastąpi koniec świata?

tim:

♊: Rysunek − może komuś się przydać :)

Mickej: wieża Hanoi słyszałeś kiedyś takie cudo

b.: *najmniejszy znajduje się na samym dole* − ale chyba powinno być tak jak na rysunku?

Mickej: tak w tym algorytmie chodzi o to że nie wolno położyć większego na mniejszy jeśli mnie pamięć nie myli to ilość ruchów do przeniesienia to n²−1 tylko nie jestem pewien ale to łatwo sprawdzić

tim: Mickej: 2ⁿ − 1 (według mnie)

♊: b.: faktycznie. Żle napisałem. Powinno być "największy znajduje się na samym dole".

tim: Dobra, ja już znam odpowiedź

♊: tim − dobrze, ale musisz to jeszcze udowodnić ;]

Mickej: no wiedziałem że jakoś tak 2ⁿ−1 jest dobrze

Mickej: Jak to mówiła moja babka z programowania "Hanoi to piękny algorytm rekurencyjny"

♊: A to chyba miała na myśli wzór a_n=2a_n−1+1

♊: ups − miałem nie podpowiadać :P

Mickej: możliwe tylko że ja zawsze miałem swoje sposoby i ona swoje a ja swoje

Mickej: a ty niestety podałeś rozwiązanie a nie podpowiedziałeś

♊: Serio chcesz liczyć z wzoru, który ja podałem ? Jest prostsza metoda, mniej skomplikowana.

Mickej: najprostsza to zrobić dla 3 elementów potem 4 i 5 i widać zależność

♊: Ale Ty masz obliczyć keidy świat się skończy, a nie sprawdzić jaka jest zależność.

Mickej: aha to pięć sekund

♊: nie − świat się nei skonczy az pięć sekund − próbuj dalej

Mickej: 2⁶4−1 = 18 446 744 073 709 551 615s lat jakieś 584 542 000 000 000lat cwaniak nie

Mickej: 5 sekund miałeś czekać

♊: To mi jeszcze powiedz skąd to się wzieło, że czas będzie równy 2⁶⁴ −1

Mickej: z mojego cudaśnego wzoru który kiedyś na lekcji wyprowadziłem liczba ruchów to 2ⁿ−1

Mickej: halo halo numerze 2 a jak ty takie zadanko robisz>?

♊: Chodziło o to, że masz pokazać wyprowadzenie tutaj. Niemówiłbym nic, gdyby tim nie sprawdził rozwiązania i podał je tutaj, ale znalazło się ono kilka postów wyżej więc pytam.

♊: Ja też doprowadziłem do 2ⁿ−1.