% NIM (odebirani zapalek)- program vypisuje pozice % s maximalne N zapalkami na maximalne K hromadkach a % pro kazdou takovou pozici vypise, zda je vyhrana nebo % prohrana, a pripadne vyherni strategii % (zapoctovy program do Programovani II na MFF UK) % Miroslav Tynovsky % brezen 2003 % ---------------------------------------------------------- % sumlist(+List, -Suma) % pro ciselny seznam List vrati soucet jeho prvku sumlist([N], N). sumlist([H|Tail], N):- sumlist(Tail, N1), N is H+N1. % ---------------------------------------------------------- % gen_nuly(+K, -List) % vygeneruje K prvkovy seznam nul gen_nuly(0, []). gen_nuly(K, [0|List]):- K1 is K-1, gen_nuly(K1, List). % ---------------------------------------------------------- % bubble(List, Sorted) % bubblesort - utridi seznam List do seznamu Sorted bubble(List, Sorted):- swap(List, List1), !, bubble(List1, Sorted). bubble(Sorted, Sorted). % ---------- % swap(List, List1) % prohodi jednu inverzi a uspeje. pokud neni inverze, fails swap([X,Y|Tail], [Y,X|Tail]):- X < Y. swap([Z|Tail],[Z|Tail1]):- swap(Tail, Tail1). % ---------------------------------------------------------- % dalsihrom(+Max, +Poz, -Poz1). % N ... maximalni pocet sirek, % Poz ... sestupne usporadany seznam reprezentujici % hromadky sirek % Poz1 ... dalsi takovy seznam v "reversed-lexikografickem" % usporadani dalsihrom(N, [H|Tail], [H1|Tail]):- H1 is H+1, sumlist([H1|Tail], N1), N1 =< N. dalsihrom(N, [_,Y|Tail], [X1,Y1|Tail1]):- dalsihrom(N, [Y|Tail], [Y1|Tail1]), X1 is Y1, sumlist([X1,Y1|Tail1], N1), N1 =< N. % ---------------------------------------------------------- % tahi(+I, +Poz, -Poz1) % vygeneruje pozice Poz1, ktere vzniknou z Poz odebranim % I sirek tahi(I, [H|Tail], [H1|Tail]):- H >= I, H1 is H-I. tahi(I, [H|Tail], [H|Tail1]):- tahi(I, Tail, Tail1). % ---------------------------------------------------------- % tah(+Icka, +Poz, -Poz1). % Icka je seznam poctu sirek, ktery se odebere z jedne % z hromadek. Vrati Poz1 - pozice vznikla nejakym tahem % z pozice Poz tah([I|_], Poz, Poz1):- tahi(I, Poz, Poz2), bubble(Poz2, Poz1). tah([_|Icka], Poz, Poz1):- tah(Icka, Poz, Poz1). % --------------------------------------------------------- % neni_tah(+Icka, +Poz). % uspeje, pokud z Poz neexistuje zadny tah. neni_tah(Icka, Poz):- tah(Icka, Poz, _), !, fail. neni_tah(_, _). % --------------------------------------------------------- % zkustahy(+Icka, +Poz, +Prohrane) % pokud existuje nejaky tah vedouci do prohranych, uspeje a % vypise " -> " zkustahy(Icka, Poz, Prohrane):- tah(Icka, Poz, Poz1), member(Poz1, Prohrane), write(' -> '), write(Poz1). % ---------------------------------------------------------- % prohrana(+Icka, +Poz, +Prohrane, -Prohrane1) % pokud je pozice prohrana, prida do seznamu prohranych na % zacatek, jinak vrati stejny seznam (kazdopadne vrati % seznam prohranych pozic) % hleda jenom jeden tah do hloubky! prohrana(Icka, Poz, Prohrane, Prohrane):- neni_tah(Icka, Poz), write(' neexistuje tah vyhrana'), !. prohrana(Icka, Poz, Prohrane, Prohrane):- zkustahy(Icka, Poz, Prohrane), write(' vyhrana'), !. prohrana(_, Poz, Prohrane, [Poz|Prohrane]):- write(' prohrana'). % ---------------------------------------------------------- % vypis(+Icka, +N, +K, +Pozice, +Prohrane) % vypise na obrazovku tabelaci vp(Icka, N, K, Pozice, Prohrane):- dalsihrom(N, Pozice, Pozice1), !, write(Pozice1), prohrana(Icka, Pozice1, Prohrane, Prohrane1), nl, vp(Icka, N, K, Pozice1, Prohrane1). % ---------------------------------------------------------- % start. % hlavni klauzule, ktera zajisti vstup a vsechno to spusti. start:- write('Zadej pocet sirek (napr. "7."): '), read(N), write('Zadej pocet hromadek (napr. "4."): '), read(K), gen_nuly(K, Pozice), write('Zadej pocty odebiranych v jednom tahu '), write('(napr. "[1,2]."): '), read(Icka),!, vp(Icka, N, K, Pozice, []).