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

「プロジェクトオイラー問６７」(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).

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).