このディレクトリの索引

% 以下のサイトは # # Prologの集約問題 # 述語体重が定義されている時、各節で定義されているメンバーの # 平均体重を求めるという問題だ。 # # 体重(島田,57). # 体重(服部,65). # 体重(内山,70). % % 最初に最も普通の定義を示す。 体重(島田,57). 体重(服部,65). 体重(内山,70). 平均体重(_平均体重) :- findall(_体重,体重(_,_体重),_メンバーの体重リスト), length(_メンバーの体重リスト,_人数), sum_list(_メンバーの体重リスト,_体重合計), _平均体重 is _体重合計 / _人数. % % Prologを単位節データとして使用する場合、以下のfindavg/3を使います。 % findavg/3 をライブラリに加えておきます。 % 体重(島田,57). 体重(服部,65). 体重(内山,70). 平均体重(_平均体重) :- findavg(_体重,体重(_,_体重),_平均体重). findavg(_集約項,_項,_算術平均) :- findall(_集約項,_項,_値リスト), sum_list(_値リスト,_合計値), length(_値リスト,_リストの長さ), _算術平均 is _合計値 / _リストの長さ,!. % % % 次の定義は体重データベースの構造を変更してしまう対処です。 % 定義自体を一引数増やして、有向グラフの述語表現にしてみます。 % 体重(島田,服部,57). 体重(服部,内山,65). 体重(内山,島田,70). 平均体重(_平均体重) :- 体重(_最初の人,_次の人,_最初の人の体重), 合計体重(_次の人,_最初の人,_人数,_合計体重), _平均体重 is _合計体重 / _人数,!. 合計体重(_最初の人,_最初の人,1,_最初の人の体重) :- 体重(_最初の人,_,_最初の人の体重). 合計体重(_前の人,_最初の人,_人数,_合計体重) :- 体重(_前の人,_次の人,_体重), 合計体重(_次の人,_最初の人,_人数_1,_合計体重_1), _合計体重 is _体重 + _合計体重_1, _人数 is _人数_1 + 1. % % 直ぐにわかることは、同姓が出てくると困る。 % それで、普通は名前でノードを構成することはせず、 % 所謂、IDを振ります。この振り方が大問題となりますが。 % ここではIDは a,b,8 を使っています。 % 体重(a,b,島田,57). 体重(b,8,服部,65). 体重(8,a,内山,70). 平均体重(_平均体重) :- 体重(_id,_id_1,_,_体重), 合計体重(_id_1,_id,_人数,_合計体重), _平均体重 is _合計体重 / _人数,!. 合計体重(_id,_id,1,_体重) :- 体重(_id,_,_体重),!. 合計体重(_id_1,_id,_人数,_合計体重) :- 体重(_id_1,_id_2,_,_体重), 合計体重(_id_2,_id,_人数_1,_合計体重_1), _合計体重 is _体重 + _合計体重_1, _人数 is _人数_1 + 1. % % もしIDが1を先頭とする連続した整数であることを維持できるのなら % 体重(1,島田,57). 体重(2,服部,65). 体重(3,内山,70). 平均体重(_平均体重) :- 合計体重(1,_人数,_合計体重), _平均体重 is _合計体重 / _人数. 合計体重(_id,_人数,_合計体重) :- 体重(_id,_,_体重), _id_2 is _id + 1, 合計体重(_id_2,_人数_2,_合計体重_2), _人数 is _人数_2 + 1, _合計体重 is _体重 + _合計体重_2,!. 合計体重(_,0,0). % 以下のサイトは # 出典:: http://hibari.2ch.net/test/read.cgi/tech/1286978599/863 # # [1] 授業単元:自然言語処理 # [2] 問題文(含コード&リンク): # ttp://nlp.dse.ibaraki.ac.jp/~shinnou/lecture/nl/rep1.pdf # 課題2のみです。 # 課題2 次の図はループのない有向グラフである。辺の向きは記載されていないが、左から右である。 # V9 ! V12 とV13 ! V3 に注意すること。 # V0 をStart ノード、V6 をEnd ノードとして、V0 からV6 に至るパスのうちで、重みの和が # 最大となるようなパスをViterbi アルゴリズムにより求めるプログラムをC あるいはJava # で作成せよ。 # ただしグラフは、入力する形でなくても、プログラムの中で予め配列などで作成しておく形 # でもよい。 # > kadai2.exe # 重みが最大のパスは # V0 --> V* --> V* ・・・・--> V6 # 重みの和は*** # 有向グラフ('V0','V1',1). # 有向グラフ('V1','V2',2). # 有向グラフ('V2','V3',5). # 有向グラフ('V3','V4',8). # 有向グラフ('V4','V5',2). # 有向グラフ('V5','V6',1). # 有向グラフ('V7','V6',2). # 有向グラフ('V8','V7',1). # 有向グラフ('V9','V8',5). # 有向グラフ('V10','V9',2). # 有向グラフ('V10','V11',6). # 有向グラフ('V11','V12',5). # 有向グラフ('V12','V13',1). # 有向グラフ('V0','V10',3). # 有向グラフ('V1','V11',1). # 有向グラフ('V2','V12',4). # 有向グラフ('V8','V5',6). # 有向グラフ('V9','V12',7). # 有向グラフ('V9','V13',1). # 有向グラフ('V11','V9',3). # 有向グラフ('V12','V3',8). # 有向グラフ('V12','V5',2). # 有向グラフ('V13','V8',3). # 有向グラフ('V13','V3',1). # # グラフのデータ構造の例、0 が辺なし、‐の値は向きが逆、+の値は向きが正しい重み。 # #include # #define N 14 /* 頂点の数*/ # #define START 0 /* 始点の頂点番号*/ # #define END 6 /* 終点の頂点番号*/ # int g[N][N] = { /* グラフG はN 行N 列の配列*/ # /* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 */ # { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0}, # { -1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, # { 0, -2, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0}, # { 0, 0, -5, 0, 8, 0, 0, 0, 0, 0, 0, 0, -8, -1}, # { 0, 0, 0, -8, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0}, # { 0, 0, 0, 0, -2, 0, 1, 0, -6, 0, 0, 0, -2, 0}, # { 0, 0, 0, 0, 0, -1, 0, -2, 0, 0, 0, 0, 0, 0}, # { 0, 0, 0, 0, 0, 0, 2, 0, -1, 0, 0, 0, 0, 0}, # { 0, 0, 0, 0, 0, 6, 0, 1, 0, -5, 0, 0, 0, -3}, # { 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, -2, -3, 7, 1}, # { -3, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 6, 0, 0}, # { 0, -1, 0, 0, 0, 0, 0, 0, 0, 3, -6, 0, 5, 0}, # { 0, 0, -4, 8, 0, 2, 0, 0, 0, -7, 0, -5, 0, 1}, # { 0, 0, 0, 1, 0, 0, 0, 0, 3, -1, 0, 0, -1, 0} # }; # ・・・・ 有向グラフ('V0','V1',1). 有向グラフ('V1','V2',2). 有向グラフ('V2','V3',5). 有向グラフ('V3','V4',8). 有向グラフ('V4','V5',2). 有向グラフ('V5','V6',1). 有向グラフ('V7','V6',2). 有向グラフ('V8','V7',1). 有向グラフ('V9','V8',5). 有向グラフ('V10','V9',2). 有向グラフ('V10','V11',6). 有向グラフ('V11','V12',5). 有向グラフ('V12','V13',1). 有向グラフ('V0','V10',3). 有向グラフ('V1','V11',1). 有向グラフ('V2','V12',4). 有向グラフ('V8','V5',6). 有向グラフ('V9','V12',7). 有向グラフ('V9','V13',1). 有向グラフ('V11','V9',3). 有向グラフ('V12','V3',8). 有向グラフ('V12','V5',2). 有向グラフ('V13','V8',3). 有向グラフ('V13','V3',1). 'V0 をStart ノード、V6 をEnd ノードとして、V0 からV6 に至るパスのうちで、重みの和が最大となるようなパスを求める'(_最大の重みの和,_バス) :- findmax(_重みの和,到達('V0','V6',_重みの和,_パス),_最大の重みの和), 到達('V0','V6',_最大の重みの和,_パス). 到達(_節,_隣接節,_重み,[_節,_隣接節]) :- 有向グラフ(_節,_隣接節,_重み). 到達(_開始節,_到達節,_重みの和,[_開始節|_隣接節から到達節までのパス]) :- 有向グラフ(_開始節,_隣接節,_重み), 到達(_隣接節,_到達節,_隣接節から到達節までの重みの和,_隣接節から到達節までのパス), _重みの和 is _重み + _隣接節から到達節までの重みの和. % findmax/3 % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1248012902/509 # # 【 課題 】 # http://nojiriko.asia/jpeg/841.jpg # 図の有向グラフの最短経路を求めよ。 # 初期値がMAXでアルゴリズムを作れ。 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :-   findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :-   有向グラフ(_頂点1,_頂点3,_距離1),   有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R),   _距離 is _距離2 + _距離1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :- findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :- 有向グラフ(_頂点1,_頂点3,_距離1), 有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R), _距離 is _距離2 + _距離1. % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1248012902/509 # # 【 課題 】 # http://nojiriko.asia/jpeg/841.jpg # 図の有向グラフの最短経路を求めよ。 # 初期値がMAXでアルゴリズムを作れ。 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :-   findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :-   有向グラフ(_頂点1,_頂点3,_距離1),   有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R),   _距離 is _距離2 + _距離1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :- findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :- 有向グラフ(_頂点1,_頂点3,_距離1), 有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R), _距離 is _距離2 + _距離1. % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1258158172/771 # # [1] 授業単元:C言語演習 # [2] 問題文(含コード&リンク):これに全て記載 http://ime.nu/kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10245.c # # 問題 # graph.cの関数print_graph_memory()を参考に、グラフの連結であるか否かの判定を行うプログラムを作成せよ。 # または連結な場合は、一筆書きできるか否かの判定を行うようにせよ。 # sample5.dimacs、sample6.dimacs、sample7.dimacsを連結判定・一筆書き判定せよ。 有向グラフに於いて一筆書き(A,_経路) :- setof((B,C),有向グラフ(B,C),L), length(L,Len), 有向グラフに於いて一筆書き(A,A,Len,[],_経路). 有向グラフに於いて一筆書き(A,A,Len,L,[]) :- length(L,Len),!. 有向グラフに於いて一筆書き(A,S,Len,L,[A|R]) :- 有向グラフ(A,B), \+(member((A,B),L)), 有向グラフに於いて一筆書き(B,S,Len,[(A,B)|L],R). % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1258158172/771 # # [1] 授業単元:C言語演習 # [2] 問題文(含コード&リンク):これに全て記載 http://ime.nu/kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10245.c # # 問題 # graph.cの関数print_graph_memory()を参考に、グラフの連結であるか否かの判定を行うプログラムを作成せよ。 # または連結な場合は、一筆書きできるか否かの判定を行うようにせよ。 # sample5.dimacs、sample6.dimacs、sample7.dimacsを連結判定・一筆書き判定せよ。 有向グラフに於いて到達可能(A,B) :-   有向グラフ(A,B),!. 有向グラフに於いて到達可能(A,B) :-   有向グラフ(A,C),   有向グラフに於いて到達可能(C,B).