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

プロジェクトオイラー問６７ - (2014/03/02 (日) 03:29:50) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2067


*Problem 67 「最大経路の和 その2」 †
三角数もどきの頂から右下左下への移動を選びながら経路上の数字を合計する。
計が最大になる経路があるが、その経路の計を答えよ。
詳細はリンク先参照のこと。

解法
一段ごとの動的計画法で十分です。
一段をリストとし、そのリストを集めたリスト。
問題で与えられたテキストデータがそうなるように手作業で変換してから解いてます。



 big(X,Y,X):-X>Y,!.
 big(_,Y,Y):-!.
 
 
 next_row([X],[Z],[Z1]):-!,Z1 is Z+X.
 next_row([X],[_,Z],[Z1]):-
 	!,
 	Z1 is Z+X.
 next_row([X,Y|Xs],[Z|Rest],[Z1|Result]):-
 	!,
 	big(X,Y,Add),
 	Z1 is Z+Add,
 	next_row([Y|Xs],Rest,Result).
 
 
 calc([],Sums):-
 	!,
 	sort(Sums,Sums1),
 	reverse(Sums1,[Top|_]),
 	write(Top).
 
 calc([Row|Data],Sum):-
 	!,
  	[R|Row1]=Row,
 	next_row(Sum,Row1,Sum1),
 	[T|_]=Sum,
 	E is T+R,
 	calc(Data,[E|Sum1]).
 
 main67:-
 	open('pe67.txt',read,IS),
  	read_term(IS,[Top|Datas],[]),
 	close(IS),
 	calc(Datas,Top).