Wieża Hanoi

[Ikslawok]

Witam, mam problem z pewnym zadaniem( należy wyznaczyć pdpowiedni wzór rekurencyjny).
Drążki wieży Hanoi będą ustawione na okręgu. Ile minimalnie ruchów należy wykonać ,aby przenieść wieżę z pierwszego na trzeci drążek pod warunkiem ,że nie wykonujemy bezpośrednich ruchów z pierwszego na drugi drążek.
Pozdrawiam.

[Qń]

A rozumiesz dobrze jak wyprowadza się rekurencję bez warunku o zakazie przenoszenia krążków z pierwszego drążka na drugi (i chyba na odwrót, jeśli to zadanie z Konkretnej)?

Q.

[Ikslawok]

Przy zwykłej wieży Hanoi wyprowadzenie wzoru na rekurencję nie jest zbyt trudne, bynajmniej rozumiem. Wystarczy zauważyć ,że dla n krążków należy wykonać trzy operacje, wpierw przenieść \(\displaystyle{ n-1}\) krążków na drugi pachołek, następnie \(\displaystyle{ n}\)-ty krążek na trzeci i \(\displaystyle{ n-1}\) na trzeci, Oznaczając liczbę przeniesień \(\displaystyle{ n}\) krążków pomiędzy dwoma pachołkami przez \(\displaystyle{ H(n)}\) ,mamy: \(\displaystyle{ H(n)=2H(n-1)+1}\). Rozumiem tez jak z tej postaci przejść do ogólnego wzoru, ale w przykładzie który podałem chodziło mi o to ,żeby dojść właśnie do wzoru takiej postaci.

[Qń]

Przy zwykłej wieży Hanoi wyprowadzenie wzoru na rekurencję nie jest zbyt trudne, bynajmniej rozumiem.

Proponuję sprawdzenie w słowniku co znaczy słowo "bynajmniej" i czym różni się od "przynajmniej".

Co do zadania - w wersji bez ograniczeń nasza filozofia działania jest taka, żeby największy krążek jakoś przenieść na docelowy drążek. W tym celu zdejmujemy wszystkie krążki z największego i kładziemy "gdzieś", a następnie przekładamy ten największy na docelowe miejsce.

Dokładnie to samo chcemy zrobić w wersji z ograniczeniem. Zastanów się: jaką sekwencję operacji należy wykonać, żeby największy krążek znalazł się na drugim drążku? Jeśli masz problem z odpowiedzią, zastanów się najpierw jak rozwiązać problem gdy krążki są tylko dwa.

Q.