#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
from linked_lists import LinkedList, Cons, Nil
hanoi_mem = dict()
def hanoi(n, a, b, c):
if n == 1:
return LinkedList(["%s to %s" % (a, b)])
if n < 1:
raise ValueError("n musi byt kladne")
if (n+1, a, c, b) not in hanoi_mem:
hanoi_mem[(n-1, a, c, b)] = hanoi(n-1, a, c, b)
if (n+1, a, c, b) not in hanoi_mem:
hanoi_mem[(n-1, c, b, a)] = hanoi(n-1, c, b, a)
ms1 = hanoi_mem[(n-1, a, c, b)]
ms2 = hanoi_mem[(n-1, c, b, a)]
return append(ms1, Cons("%s to %s" % (a, b), ms2))
def append(xs, ys):
if xs == Nil:
return ys
else:
return Cons(xs.head, append(xs.tail, ys))
# demonstracni vypis
if __name__ == "__main__":
print("Demonstrace programu Hanoi")
print("hanoi(pocet_taliru, z_tyce, na_tyc, pomoci_tyce)")
print("\nVysledek dotazu hanoi(2, 'a', 'b', 'c'): ")
print(hanoi(2, 'a', 'b', 'c'))
print("\nVysledek dotazu hanoi(3, 'a', 'b', 'c'): ")
print(hanoi(3, 'a', 'b', 'c'))
print("\nVysledek dotazu hanoi(4, 'a', 'b', 'c'): ")
print(hanoi(4, 'a', 'b', 'c'))
Demonstrace programu Hanoi
hanoi(pocet_taliru, z_tyce, na_tyc, pomoci_tyce)
Vysledek dotazu hanoi(2, 'a', 'b', 'c'):
['a to c', 'a to b', 'c to b']
Vysledek dotazu hanoi(3, 'a', 'b', 'c'):
['a to b', 'a to c', 'b to c', 'a to b', 'c to a', 'c to b', 'a to b']
Vysledek dotazu hanoi(4, 'a', 'b', 'c'):
['a to c', 'a to b', 'c to b', 'a to c', 'b to a', 'b to c', 'a to c', 'a to b', 'c to b', 'c to a', 'b to a', 'c to b', 'a to c', 'a to b', 'c to b']
| % nacteni:
/* ['5.1_5.pl']. */
:- retractall(start/0).
:- retractall(write_all_X/3).
?-op(100,xfx,to), dynamic(hanoi/5).
hanoi(1,A,B,_,[A to B]).
hanoi(N,A,B,C,Moves) :- N>1, N1 is N-1, lemma(hanoi(N1,A,C,B,Ms1)),
hanoi(N1,C,B,A,Ms2), append(Ms1,[A to B|Ms2],Moves).
lemma(P) :- P,asserta((P :- !)).
% demonstracni vypis
% abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
write_all_X/3,
start/0.
write_all_X(Goal,X,Name):-
call(Goal),write(' '),write(Name),write(' = '),write(X),nl,fail.
write_all_X(_,_,_).
start:-
write('Demostrace programu Hanoi'),nl,
write('hanoi(+PocetTaliru,+z_tyce,+na_tyc,+pomoci_tyce,-Tahy)'),nl,
write('Vysledek dotazu "hanoi(2,a,b,c,M)".'),nl,
write_all_X(hanoi(2,a,b,c,M),M,'M'),
write('Vysledek dotazu "hanoi(3,a,b,c,M)".'),nl,
write_all_X(hanoi(3,a,b,c,M),M,'M'),
write('Vysledek dotazu "hanoi(4,a,b,c,M)".'),nl,
write_all_X(hanoi(4,a,b,c,M),M,'M').
?-start.
:- retractall(start/0).
:- retractall(write_all_X/3).
Demostrace programu Hanoi
hanoi(+PocetTaliru,+z_tyce,+na_tyc,+pomoci_tyce,-Tahy)
Vysledek dotazu "hanoi(2,a,b,c,M)".
M = [a to c,a to b,c to b]
Vysledek dotazu "hanoi(3,a,b,c,M)".
M = [a to b,a to c,b to c,a to b,c to a,c to b,a to b]
Vysledek dotazu "hanoi(4,a,b,c,M)".
M = [a to c,a to b,c to b,a to c,b to a,b to c,a to c,a to b,c to b,c to a,b to a,c to b,a to c,a to b,c to b]
|