Modyfikacja Hanoi dla k wież

Odpowiedz Nowy wątek
2019-11-09 00:03
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ż...

Pozostało 580 znaków

2019-11-09 08:37
1

Google twoim przyjacielem https://en.wikipedia.org/wiki[...]noi#With_four_pegs_and_beyond

Pozostało 580 znaków

2019-11-09 14:22
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.

Pozostało 580 znaków

2019-11-09 16:00
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.

edytowany 1x, ostatnio: Spearhead, 2019-11-09 16:00

Pozostało 580 znaków

2019-11-10 04:36
0

Ten algorytm (Stewart/Frame) wiadomo, że jest optymalny tylko dla czterech wież.
https://www.i-programmer.info[...]-hanoi-optimal-algorithm.html


Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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