Wieże Hanoi zgodnie z ruchem wskazówek zegara

[sinus alfa]

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ć :/

[SlotaWoj]

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

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Wie%C5%BCe_Hanoi

oraz .

[gardner]

Odpowiedź jest bardzo prosta. Bierzesz sobie np \(\displaystyle{ 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 \(\displaystyle{ n-1}\) krążkow na 3 palik :potrzeba tyle ruchów - \(\displaystyle{ a_{n-1}}\)
(to że przerzucasz je w odpowiedniej kolejności i najpierw musisz przerzucić je na drugi jest już uwzględnione w naszym \(\displaystyle{ 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: \(\displaystyle{ 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

[SlotaWoj]

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:

• \(\displaystyle{ a_n=4a_{n-1}+1}\)