※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。



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