Próbuję rozwiązać zadanie Dwubarwne wieże Hanoi z Potyczek Algorytmicznych 2001 (http://main.edu.pl/pl/archive/pa/2001/han). Nie mam pojęcia jak to rozwiązać. Podstawowy problem Hanoi jest prosty i doszedłem do tego, że wynik w nim to 2^n - 1, natomiast te zadanie zdaje się być znacznie trudniejsze. Czy mógłby mi ktoś pomóc? Wiem, że wynik na pewno będzie ogromny, więc trzeba napisać własną arytmetykę, ale to już mam zrobione.
Może tu znajdziesz opowiedź:
http://4programmers.net/Forum/C_i_C++/241531-dwukolorowa_wieza_hanoi
@Archimondei
No właśnie problem w tamtym temacie został rozwiązny pierwszą odpowiedzią - musisz się jedynie w nią zagłębić.
Naskrobałem ci coś takiego w pythonie, co może pomoże ci zobrazować tą odpowiedź:
def hanoi(n, source, helper, target):
if n > 0:
hanoi(n - 1, source, target, helper)
if source:
target.append(source.pop())
hanoi(n - 1, helper, source, target)
heightOfTheTower = int(input("Podaj wysokość wieży: "))
source = list(range(heightOfTheTower))
n = len(source)
target = []
helper = []
#załóżmy sobie, że krążki parzyste są białe a nieparzyste czarne albo łatewa
for x in range(0, n+1):
if x%2:
hanoi(n-x, source, helper, target)
else:
hanoi(n-x, target, helper, source)
print(source, target, helper)
Jestem raczej początkujący, zatem kod pewnie ssie, złożoność i szybkość tak samo, ale działa.
Edit: Zapomniałem o najważniejszej rzeczy - liczbie ruchów :p
Tutaj liczbą potrzebnych ruchów będzie:
gdzie n = heightOfTheTower+1 ^ m=1
Czyli zajrzyj tu: https://en.wikipedia.org/wiki/Eulerian_number
Lub jak chcesz policzyć sam wynik dla danego wejścia, bez pisania, to w wolframie masz gotową funkcję Eulerian[n, m] w module Combinatorica
Ew. tu masz taki prymitywny zapis tego w pythonie:
n = int(input("Podaj wysokość wieży: "))
moves = 0
for x in range(0, n+1):
moves += 2**(n-x)-1
print(moves)