「prolog勉強プロジェクトオイラー171~180」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*Problem 171 「各桁の平方の和が平方数となる数を求めよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20171
正の整数nについて, f(n)を各桁の数字(10進数)の平方の和と定義する. 例えば,
f(3) = 3^2 = 9,
f(25) = 2^2 + 5^2 = 4 + 25 = 29,
f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36
0 < n < 10^20について, f(n)が平方数となるようなnの和の末尾9桁を求めよ.
解法
何も考えずまとめて計算すれば即座に答えが出ます。
PrologはC++でないのでstd::mapや配列が使えませんが素朴に遅く実装しても2秒くらいで答えが出ます。
配列が使えたらはるかに高速に解けます。
union_sum([],Y,[Y]):-!.
union_sum([[Sum,N,Perm]|Rest],[Sum,N1,Perm1],Result):-
!,
N2 is N+N1,
Perm2 is Perm+Perm1,
union_sum(Rest,[Sum,N2,Perm2],Result).
union_sum([X|Rest],[Sum,N,Perm],[[Sum,N1,Perm]|Result]):-
N1 is N mod 10^9,
union_sum(Rest,X,Result).
ans_sum([],Ans,Ans):-!.
ans_sum([[Sum,NSum,_]|Rest],Ans,Result):-
is_square(Sum),
!,
Ans1 is Ans+NSum,
ans_sum(Rest,Ans1,Result).
ans_sum([_|Rest],Ans,Result):-
ans_sum(Rest,Ans,Result).
next_calc(Sets,[Sum1,N1,Perm]):-
member([Sum,N,Perm],Sets),
between(0,9,K),
Sum1 is Sum+K*K,
N1 is N*10+K*Perm.
is_square(N):-
T is floor(sqrt(N)),
N=:=T*T.
seed([Sum,N,1]):-
between(1,9,N),
Sum is N*N.
search(_,21,Ans):-!,
Ans1 is Ans mod 10^9,
write(Ans1).
search(Sets,N,Ans):-
ans_sum(Sets,Ans,Ans1),
findall(Set,next_calc(Sets,Set),Sets1),
msort(Sets1,Sets2),
[Top|Sets3]=Sets2,
union_sum(Sets3,Top,Sets4),
N1 is N+1,
write([N,Ans1]),nl,
search(Sets4,N1,Ans1).
main171:-findall(Set,seed(Set),Sets),
search(Sets,1,0).
*Problem 172 「桁の繰り返しが少ない数について調べ上げよ」 †
どの数字も3回を超えて現れないような18桁の数(先頭の0は許されない)はいくつあるか?
解法
先頭桁を1に固定してあとはどの桁の数字を何回使うか全探索で決めたら数学の教科書に書いてある組み合わせの公式通りで答えが出ます。
あとは1から9まで対称なので9倍すれば1秒で答えが出ますがこれは遅い実装です。
全探索が少し遅いので全探索を動的計画法(メモ化計算?)で置き換えれば、全探索の使った桁数と分母に来る数を主キーにしてまとめて計算すれば速度は上がります。
速度が上がりますがめんどいので私はここまで、興味のある方はどうぞ。
fact(0,1):-!.
fact(N,Result):-
N1 is N-1,
fact(N1,Re),
Result is Re*N.
calc(Keta,_,_,_):-Keta>17,!,fail.
calc(17,_,Div,Div):-!.
calc(_,[],_,_):-!,fail.
calc(Keta,[C|Count],Div,Result):-
between(0,C,Add),
nth0(Add,[1,1,2,6,24],D),
Keta1 is Keta+Add,
Div1 is Div*D,
calc(Keta1,Count,Div1,Result).
divsum(_,[],0):-!.
divsum(All,[Div|Divs],Result):-
divsum(All,Divs,Re),
Result is All//Div+Re.
main172:-
findall(Div,calc(0,[3,2,3,3,3,3,3,3,3,3],1,Div),Divs),
fact(17,All),
divsum(All,Divs,Ans),
Ans1 is Ans*9,
write(Ans1).
*Problem 178 「ステップ数」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20178
45656を考えよう. 連続する2桁の数は全て差の絶対値が 1 である.
連続する2桁の数の差の絶対値が全て 1 である数をステップ数と呼ぶ.
パンデジタル数では0から9の各数が少なくとも 1 回出現する.
10^40未満の数でパンデジタル数かつステップ数であるものの数を答えよ.
解法
簡単なメモ化計算で簡単に出ます
std::mapがないので集計でコードが膨らんでいます。
step(N,N1):-0<N,N1 is N-1.
step(N,N1):-N<9,N1 is N+1.
union_sum([],Y,[Y]).
union_sum([[Pans,N,Perm]|Rest],[Pans,N,Perm1],Result):-
!,
Perm2 is Perm+Perm1,
union_sum(Rest,[Pans,N,Perm2],Result).
union_sum([X|Rest],Y,[Y|Result]):-
!,
union_sum(Rest,X,Result).
next_calc([Pans,N,Perm],[Pans1,N1,Perm]):-
step(N,N1),
sort([N1|Pans],Pans1).
seed([[N],N,1]):-
between(1,9,N).
ans_sum([],Ans,Ans):-!.
ans_sum([[[0,1,2,3,4,5,6,7,8,9],_,Perm]|Rest],Ans,Result):-
!,
Ans1 is Ans+Perm,
ans_sum(Rest,Ans1,Result).
ans_sum([_|Rest],Ans,Result):-
ans_sum(Rest,Ans,Result).
calc(Sets,Result):-
member(Set,Sets),
next_calc(Set,Result).
search(_,41,Ans):-!,write([ans,Ans]).
search(Sets,N,Ans):-
!,
ans_sum(Sets,Ans,Ans1),
findall(Set,calc(Sets,Set),Sets1),
msort(Sets1,Sets2),
[Top|Sets3]=Sets2,
write([N,Ans1]),nl,
union_sum(Sets3,Top,Sets4),
N1 is N+1,
search(Sets4,N1,Ans1).
main178:-
X is 512*1024*1024,set_prolog_stack(global,limit(X)),
findall(Set,seed(Set),Sets),
search(Sets,1,0).
プロジェクトオイラーという数学の問題が掲載されているサイトの問題を堀江伸一さんがProlog言語で解くページ。
*Problem 171 「各桁の平方の和が平方数となる数を求めよ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20171
正の整数nについて, f(n)を各桁の数字(10進数)の平方の和と定義する. 例えば,
f(3) = 3^2 = 9,
f(25) = 2^2 + 5^2 = 4 + 25 = 29,
f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36
0 < n < 10^20について, f(n)が平方数となるようなnの和の末尾9桁を求めよ.
解法
何も考えずまとめて計算すれば即座に答えが出ます。
PrologはC++でないのでstd::mapや配列が使えませんが素朴に遅く実装しても2秒くらいで答えが出ます。
配列が使えたらはるかに高速に解けます。
union_sum([],Y,[Y]):-!.
union_sum([[Sum,N,Perm]|Rest],[Sum,N1,Perm1],Result):-
!,
N2 is N+N1,
Perm2 is Perm+Perm1,
union_sum(Rest,[Sum,N2,Perm2],Result).
union_sum([X|Rest],[Sum,N,Perm],[[Sum,N1,Perm]|Result]):-
N1 is N mod 10^9,
union_sum(Rest,X,Result).
ans_sum([],Ans,Ans):-!.
ans_sum([[Sum,NSum,_]|Rest],Ans,Result):-
is_square(Sum),
!,
Ans1 is Ans+NSum,
ans_sum(Rest,Ans1,Result).
ans_sum([_|Rest],Ans,Result):-
ans_sum(Rest,Ans,Result).
next_calc(Sets,[Sum1,N1,Perm]):-
member([Sum,N,Perm],Sets),
between(0,9,K),
Sum1 is Sum+K*K,
N1 is N*10+K*Perm.
is_square(N):-
T is floor(sqrt(N)),
N=:=T*T.
seed([Sum,N,1]):-
between(1,9,N),
Sum is N*N.
search(_,21,Ans):-!,
Ans1 is Ans mod 10^9,
write(Ans1).
search(Sets,N,Ans):-
ans_sum(Sets,Ans,Ans1),
findall(Set,next_calc(Sets,Set),Sets1),
msort(Sets1,Sets2),
[Top|Sets3]=Sets2,
union_sum(Sets3,Top,Sets4),
N1 is N+1,
write([N,Ans1]),nl,
search(Sets4,N1,Ans1).
main171:-findall(Set,seed(Set),Sets),
search(Sets,1,0).
*Problem 172 「桁の繰り返しが少ない数について調べ上げよ」 †
どの数字も3回を超えて現れないような18桁の数(先頭の0は許されない)はいくつあるか?
解法
先頭桁を1に固定してあとはどの桁の数字を何回使うか全探索で決めたら数学の教科書に書いてある組み合わせの公式通りで答えが出ます。
あとは1から9まで対称なので9倍すれば1秒で答えが出ますがこれは遅い実装です。
全探索が少し遅いので全探索を動的計画法(メモ化計算?)で置き換えれば、全探索の使った桁数と分母に来る数を主キーにしてまとめて計算すれば速度は上がります。
速度が上がりますがめんどいので私はここまで、興味のある方はどうぞ。
fact(0,1):-!.
fact(N,Result):-
N1 is N-1,
fact(N1,Re),
Result is Re*N.
calc(Keta,_,_,_):-Keta>17,!,fail.
calc(17,_,Div,Div):-!.
calc(_,[],_,_):-!,fail.
calc(Keta,[C|Count],Div,Result):-
between(0,C,Add),
nth0(Add,[1,1,2,6,24],D),
Keta1 is Keta+Add,
Div1 is Div*D,
calc(Keta1,Count,Div1,Result).
divsum(_,[],0):-!.
divsum(All,[Div|Divs],Result):-
divsum(All,Divs,Re),
Result is All//Div+Re.
main172:-
findall(Div,calc(0,[3,2,3,3,3,3,3,3,3,3],1,Div),Divs),
fact(17,All),
divsum(All,Divs,Ans),
Ans1 is Ans*9,
write(Ans1).
*Problem 178 「ステップ数」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20178
45656を考えよう. 連続する2桁の数は全て差の絶対値が 1 である.
連続する2桁の数の差の絶対値が全て 1 である数をステップ数と呼ぶ.
パンデジタル数では0から9の各数が少なくとも 1 回出現する.
10^40未満の数でパンデジタル数かつステップ数であるものの数を答えよ.
解法
簡単なメモ化計算で簡単に出ます
std::mapがないので集計でコードが膨らんでいます。
step(N,N1):-0<N,N1 is N-1.
step(N,N1):-N<9,N1 is N+1.
union_sum([],Y,[Y]).
union_sum([[Pans,N,Perm]|Rest],[Pans,N,Perm1],Result):-
!,
Perm2 is Perm+Perm1,
union_sum(Rest,[Pans,N,Perm2],Result).
union_sum([X|Rest],Y,[Y|Result]):-
!,
union_sum(Rest,X,Result).
next_calc([Pans,N,Perm],[Pans1,N1,Perm]):-
step(N,N1),
sort([N1|Pans],Pans1).
seed([[N],N,1]):-
between(1,9,N).
ans_sum([],Ans,Ans):-!.
ans_sum([[[0,1,2,3,4,5,6,7,8,9],_,Perm]|Rest],Ans,Result):-
!,
Ans1 is Ans+Perm,
ans_sum(Rest,Ans1,Result).
ans_sum([_|Rest],Ans,Result):-
ans_sum(Rest,Ans,Result).
calc(Sets,Result):-
member(Set,Sets),
next_calc(Set,Result).
search(_,41,Ans):-!,write([ans,Ans]).
search(Sets,N,Ans):-
!,
ans_sum(Sets,Ans,Ans1),
findall(Set,calc(Sets,Set),Sets1),
msort(Sets1,Sets2),
[Top|Sets3]=Sets2,
write([N,Ans1]),nl,
union_sum(Sets3,Top,Sets4),
N1 is N+1,
search(Sets4,N1,Ans1).
main178:-
X is 512*1024*1024,set_prolog_stack(global,limit(X)),
findall(Set,seed(Set),Sets),
search(Sets,1,0).