szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 cze 2015, o 18:44 
Użytkownik

Posty: 94
Lokalizacja: Krk
Jak napisać równanie rekurencyjne dla wież Hanoi (przełożenie n krążków z palika trzeciego na pierwszy, krążek o większej średnicy nie może zostać położony na krążku o mniejszej średnicy) przy założeniu, że możemy przekładać krążki na palikach zgodnie z ruchem wskazówek zegara, tzn. z pierwszego na drugi, z drugiego na trzeci i z trzeciego na pierwszy?

Nie za bardzo wiem jak to rozpisać :/
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 29 cze 2015, o 03:41 
Moderator

Posty: 4256
Lokalizacja: Kraków PL
O ile wiem, to równanie rekurencyjne dla wież Hanoi dotyczy tylko liczby niezbędnych ruchów i nie ma bezpośredniego odzwierciedlenia w realizacji algorytmu, a chyba o algorytm chodzi w związku z tym ruchem wg wskazówek zegara.
Czy tak?
Przeczytaj w Wikipedii oraz Równania rekurencyjne.
Góra
Mężczyzna Offline
PostNapisane: 29 cze 2015, o 16:05 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Odpowiedź jest bardzo prosta. Bierzesz sobie np a_{n} i niech to będzie najmniejsza liczba ruchów pozwalająca przenieść n krążków na 3 palik zgodnie z zasadami. Twoje równanie będzie wyglądać tak:

1. przyrzucasz n-1 krążkow na 3 palik :potrzeba tyle ruchów - a_{n-1}
(to że przerzucasz je w odpowiedniej kolejności i najpierw musisz przerzucić je na drugi jest już uwzględnione w naszym a_{n-1})
2.przerzucasz krążek o największej średnicy na 2 palik (1 ruch)
3.przerzucasz n-1 krążków znowu na pierwszy palik (to samo jak w 1.)
4.przerzucasz krążek o największej średnicy na 3 palik (1 ruch)
5.przerzucasz n-1 krążków na 3 palik (to samo co w 1. i 3)
6. nasze równanie rekurencyjne: a_{n}=2a_{n-1} + 2


hmm teraz doczytałem że przerzucenie z 3 palika na pierwszy nie odbywa się "z powrotem" tylko bezpośrednio : trzeba trochę zaktualizować algorytm i napisać że przerzucamy wieże o iluś tam klockach na NASTĘPNY palik. Reszta analogicznie. Edytuj mój wpis i spróbuj samodzielnie
Góra
Mężczyzna Offline
PostNapisane: 29 cze 2015, o 16:34 
Moderator

Posty: 4256
Lokalizacja: Kraków PL
W temacie zadania było, że należy przełożyć krążki z palika 3 na palik 1 i przekładać krążki pomiędzy sąsiednimi palikami, bo tylko wtedy jest gwarantowana zgodność kierunku przekładania 1-2-3-1. Tzn. Jeżeli trzeba przełożyć krążki z palika 1 na 3, to należy przełożyć je na palik 2, który musi być wolny lub spełniać wymogi średnicy, a dopiero później na palik 3, który również musi być wolny lub spełniać wymogi średnicy.

Mnie wychodzi:

    a_n=4a_{n-1}+1
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ilość sposobów ułożenia wież Hanoi (nie oryginał)  zaklopotany93  6
 Szachownica i wieże  pumeks  1
 Informatyk kupujący dyskietki i dziecko budujące wieże.  Tucker  7
 wieże na szachownicy - zadanie 3  Zordon  2
 Na ile sposobów można zbudować wieże  Plebsinio  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl