Pruchod grafu do hloubky

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Pruchod grafu do hloubky

Příspěvek od lickra »

Zadani od Hrica z poslednich zk z 2005.

Kód: Vybrat vše


/*
Projdete graf pomoci DFS a ke kazdemu vrcholu pridejte cas posledni pruchodu.

*/
g([[1,5],[2,5,4,3],[3,2,4],[4,5,2,3],[5,1,2,4]]). 
% seznam vrcholu - vrchol:jmeno,naslednici
% testovaci
 

dfs([],[]).
dfs([Vrchol|T],Zpracovany):-dfs1(Vrchol,[Vrchol|T],Zpracovany,[],_).


dfs1([],_,_,X,X).
dfs1([X|T],Graf,Zpracovany,W,WQ):-not(member(X,W)),
	volny(T,W,P),                                  % v seznamu nasledniku najde prvni vrchol ktery neni ve zasobniku(W) ->P 
	najdi(P,Graf,Vrchol),			       % v grafu najde vrchol P ->Vrchol 
	dfs1(Vrchol,Graf,Zpracovany,[X|W],WQ),	       % zpracuje volny vrchol Vrchol
	zpracuj(WQ,Graf,Zpracovany,1),!.		       % priradime casy opusteni


zpracuj([],_,[],_):-!.
zpracuj([X|T],Graf,Z,Pocitadlo):- najdi(X,Graf,Vrchol), pridej(Vrchol,Pocitadlo,Z1), Poci is Pocitadlo +1,zpracuj(T,Graf,Z2,Poci),conc([Z1],Z2,Z).

pridej([X|T],P,[(X,P)|T]).

conc([],L,L).
conc([X|T],L,[X|S]):-conc(T,L,S).

volny([],_,[]).
volny([Y|_],W, Y):-not(member(Y,W)),!.
volny([_|T],W, Z):-volny(T,W,Z).

najdi([],_,[]).
najdi(P,[[P|T]|_],[P|T]):-!.
najdi(P,[[_|_]|Y],Z):-najdi(P,Y,Z).

member(X,[X|_]):-!.
member(X,[_|T]):-member(X,T).


%testovaci volani g(G),dfs(G,X).

/*
G = [[1, 5], [2, 5, 4, 3], [3, 2, 4], [4, 5, 2, 3], [5, 1, 2, 4]],
X = [[ (3, 1), 2, 4], [ (4, 2), 5, 2, 3], [ (2, 3), 5, 4, 3], [ (5, 4), 1, 2, 4], [ (1, 5), 5]]

*/

Ma nekdo lepsi reseni?

Nevi nekdo jak napsat prevod CNF na DNF nebo obracene?


Pripiste nejake dalsi pokud mate vyresene.
SmutnyStudent

Re: Pruchod grafu do hloubky

Příspěvek od SmutnyStudent »

ja len tolko....cas sa naplnil...blizi sa den D :roll:
heh

Re: Pruchod grafu do hloubky

Příspěvek od heh »

veru..ale hlavne je zdravie 8)
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: Pruchod grafu do hloubky

Příspěvek od hippies »

lickra píše:Pripiste nejake dalsi pokud mate vyresene.
http://s0cketka.blogspot.com/2006/03/pr ... lozky.html .. myslim, ze neni duvod
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Odpovědět

Zpět na „PRG005 Neprocedurální programování“