Modyfikacja Hanoi dla k wież

0

Witam,

potrzebuję zaimplementować zmodyfikowaną wersję algorytmu Hanoi. Klasycznie działa on dla n dysków i tylko 3 wież, a ja potrzebuję, żeby wykonywał się dla k wież. Niestety, kompletnie nie wiem jak się za to zabrać. Potrzebuję jakiegoś pomysłu, może pseudokodu. Szukałem w internecie rozwiązań, ale nie natknąłem się na bezpośrednią implementację takiej wersji w znanym mi języku C++.

Muszą być spełnione klasyczne założenia alg. Hanoi:
-Większy dysk (krążek) nie może być położony na mniejszy

  • Wszystkie dyski zaczynają z wieży startowej i mają zostać przeniesione na wieżę docelową.
  • W jednym ruchu można przenieść tylko jeden dysk

Proszę o jakąś pomoc. Jest to złożony problem i trudno mi sobie wyobrazić, jak obsłużyć n dysków i k wież...

0

Google moim przyjacielem, ale nadal nie wiem jak wyznaczyć optymalną liczbę k dysków. Jest napisane, że "count k should be picked for which this quantity is minimum" Czyli jak np. mam 7 dysków (krążków) to 1<= k < 7 najmniejszym k spełniającym warunek jest 1? Ale czy to nie wynika z warunku na k? Wtedy zawsze k byłoby równe 1.

Także nie wiem jak wyznaczyć minimalną liczbę ruchów T potrzebnych na przeniesienie krążków.

Bardzo proszę o jakieś łopatologiczne wyjaśnienie, nie siedzę w algorytmach i takie rzeczy są dla mnie niejasne.

0

Zgodnie z treścią wikipedii, optymalne k zależy od ilości kijków, dla czterech na przykład wynosi ono

n - \lfloor \sqrt{2n+1} \rfloor + 1

Co oznacza, jak rozumiem, że jeśli interesuje cię jakiekolwiek (niekoniecznie optymalne) rozwiązanie, to możesz wybrać jakiekolwiek k. Możesz zatem przenosić i po 1 krążku.

0

Ten algorytm (Stewart/Frame) wiadomo, że jest optymalny tylko dla czterech wież.
https://www.i-programmer.info/news/181-algorithms/3494-generalized-towers-of-hanoi-optimal-algorithm.html

1 użytkowników online, w tym zalogowanych: 0, gości: 1