プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 *Problem 164 「どの連続した3桁の和も与えられた数を超えない数」 † http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20164 教科書的な動的計画法で何も工夫するところがありません。 破壊的代入がないので段階を置いて集計する必要があるくらいです。 配列や破壊的代入がない言語なのでこの一手間の面倒くさいこと。 seed([N1,N2,N3,1]):- between(1,9,N1), between(0,9,N2), between(0,9,N3), N1+N2+N3=<9. sum([],0):-!. sum([[_,_,_,P]|Ps],Result):-sum(Ps,Re),Result is Re+P. union_sum([],Set,[Set]):-!. union_sum([[N1,N2,N3,P]|Memo],[N1,N2,N3,P1],Result):- !, P2 is P1+P, union_sum(Memo,[N1,N2,N3,P2],Result). union_sum([Set|Memo],Set1,[Set1|Result]):- union_sum(Memo,Set,Result). calc_next_B(Memo,[N2,N3,N,P]):- member([_,N2,N3,P],Memo), between(0,9,N), N2+N3+N=<9. calc_next_A(Memo,Memo4):- findall(Set,calc_next_B(Memo,Set),Memo1), msort(Memo1,Memo2), [Top|Memo3]=Memo2, union_sum(Memo3,Top,Memo4). calc(20,Memo):-!,sum(Memo,Ans),write(Ans). calc(N,Memo):- calc_next_A(Memo,Memo4), N1 is N+1, calc(N1,Memo4). main164:- findall(Set,seed(Set),Memo), calc(3,Memo). *Problem 169 「ある数を2のべき乗の和で表せる方法の数を探し当てよ」 † http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20169 何も考えない動的計画法で解けます。 % 答えは１２桁 to_bit2(0,[]):-!. to_bit2(N,[B|Result]):- N1 is N//2, B is N mod 2, to_bit2(N1,Result). check(0,0,0). check(0,0,1). check(0,1,1). check(1,0,0). check(1,1,0). check(1,1,1). union_sum([],Set,[Set]):-!. union_sum([[Add,P]|Memo],[Add,P1],Result):- !, P2 is P1+P, union_sum(Memo,[Add,P2],Result). union_sum([Set|Memo],Set1,[Set1|Result]):- union_sum(Memo,Set,Result). calc_nextB(Memo,Bit,[NextAdd,P]):- member([Add,P],Memo), check(Bit,Add,NextAdd). calc_nextA(Memo,Bit,Memo4):- findall(Set,calc_nextB(Memo,Bit,Set),Memo1), msort(Memo1,Memo2), [Top|Memo3]=Memo2, union_sum(Memo3,Top,Memo4). calc(Memo,[1]):-!,member([0,P0],Memo),member([1,P1],Memo), Ans is P0+P1, write(Ans). calc(Memo,[Bit|Bits]):- !, calc_nextA(Memo,Bit,Memo4), write([Bit,Memo4]),nl, calc(Memo4,Bits). main169:- N is 10^25, to_bit2(N,Bits), calc([[0,1]],Bits).
