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

「プロジェクトオイラー問１８」(2014/02/13 (木) 16:23:59) の最新版変更点

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

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

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


*Problem 18 「最大経路の和 その1」 †
以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる.

    3
   7 4
  2 4 6
 8 5 9 3
この例では 3 + 7 + 4 + 9 = 23.

以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ.
詳細はリンク先参照のこと。


解法
一段ずつの動的計画法で片が付きます。


 max(A,B,A):-A>B,!.
 max(_,B,B):-!.
 
 calcCol([D],[X,Y],AddDX,[AddDY]):-
 	!,
 	write([X,Y,D]),
 	AddDY is D+Y,
         AddDX is D+X.
 calcCol([D|DP],[X,Y|Row],AddDX,[CommitNum|NextDP]):-
 	calcCol(DP,[Y|Row],ReDX,NextDP),
 	AddDY is D+Y,
  	max(AddDY,ReDX,CommitNum),
 	AddDX is D+X.
 
 moveRow(Last,[],Last):-
 	!.
 moveRow(DP,[Row|Rows],Result):-
 	calcCol(DP,Row,ReDX,NextDP),
 	moveRow([ReDX|NextDP],Rows,Result).
 
 search_max([X],X):-!.
 search_max([X|Xs],Result):-search_max(Xs,Re),max(X,Re,Result).
 
 main18:-
 	X=[[75],
 	   [95,64],
 	   [17,47,82],
  	   [18,35,87,10],
 	   [20,04,82,47,65],
 	   [19,01,23,75,03,34],
 	   [88,02,77,73,07,63,67],
 	   [99,65,04,28,06,16,70,92],
 	   [41,41,26,56,83,40,80,70,33],
 	   [41,48,72,33,47,32,37,16,94,29],
 	   [53,71,44,65,25,43,91,52,97,51,14],
 	   [70,11,33,28,77,73,17,78,39,68,17,57],
 	   [91,71,52,38,17,14,91,43,58,50,27,29,48],
 	   [63,66,04,68,89,53,67,30,73,16,69,87,40,31],
  	   [04,62,98,27,23,09,70,98,73,93,38,53,60,04,23]],
 	[Seed|Rest]=X,
 	moveRow(Seed,Rest,LastDP),
 	search_max(LastDP,Ans),
 	write(Ans).