「プロジェクトオイラー問８１」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問８１ - (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).