「プロジェクトオイラー問８１」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問８１」(2014/03/04 (火) 11:52:49) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

http://projecteuler.net/problem=81
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2081



*Problem 81 「経路の和:2方向」 †
コストが最小になる経路移動の問題その１
詳細はリンク先参照のこと。


解法
上の段からの動的計画法で間に合います。

 sumA([],_,[]):-!.
 sumA([X|Xs],Sum,[Sum1|Result]):-
 	!,
 	Sum1 is Sum+X,
 	sumA(Xs,Sum1,Result).
 
 min(A,B,A):-A<B,!.
 min(_,B,B):-!.
 
 dp_one_row([],[],_,[]):-!.
 dp_one_row([E|Row],[S|Sum],L,[Z|Result]):-
 	!,
 	min(L,S,M),
 	Z is E+M,
 	dp_one_row(Row,Sum,Z,Result).
 
 dp([],Sums):-
 	!,
  	reverse(Sums,[Goal|_]),
 	write([ans,Goal]).
 dp([[T|Row]|Rows],[S|Sums]):-
 	!,
  	L is T+S,
  	dp_one_row(Row,Sums,L,Sums1),
 	dp(Rows,[L|Sums1]).
 
 main81:-
 	open('pe81.txt',read,IS),
 	read_term(IS,[Top|Rows],[]),
 	close(IS),
 	sumA(Top,0,Top1),
 	dp(Rows,Top1).

http://projecteuler.net/problem=81
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2081



*Problem 81 「経路の和:2方向」 †
コストが最小になる経路移動の問題その１
詳細はリンク先参照のこと。


解法
上の段からの動的計画法で間に合います。
テキストファイルは一段をリストとしてそのリストのリストに手作業で変換してから読み込んでいる。

 sumA([],_,[]):-!.
 sumA([X|Xs],Sum,[Sum1|Result]):-
 	!,
 	Sum1 is Sum+X,
 	sumA(Xs,Sum1,Result).
 
 min(A,B,A):-A<B,!.
 min(_,B,B):-!.
 
 dp_one_row([],[],_,[]):-!.
 dp_one_row([E|Row],[S|Sum],L,[Z|Result]):-
 	!,
 	min(L,S,M),
 	Z is E+M,
 	dp_one_row(Row,Sum,Z,Result).
 
 dp([],Sums):-
 	!,
  	reverse(Sums,[Goal|_]),
 	write([ans,Goal]).
 dp([[T|Row]|Rows],[S|Sums]):-
 	!,
  	L is T+S,
  	dp_one_row(Row,Sums,L,Sums1),
 	dp(Rows,[L|Sums1]).
 
 main81:-
 	open('pe81.txt',read,IS),
 	read_term(IS,[Top|Rows],[]),
 	close(IS),
 	sumA(Top,0,Top1),
 	dp(Rows,Top1).