「prolog勉強プロジェクトオイラー1～10」の編集履歴（バックアップ）一覧に戻る

prolog勉強プロジェクトオイラー1～10 - (2013/07/08 (月) 13:37:11) の編集履歴(バックアップ)

---

プロジェクトオイラーの問題をＰｒｏｌｏｇで解く。
問い1
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%201
数式で解くのが正しいけれどまあいいか。

mod_n(N,15,N):-0=:=N mod 15,!.
mod_n(N,5,N):-0=:=N mod 5,!.
mod_n(N,3,N):-0=:=N mod 3,!.
mod_n(_,_,0).

calc(1000,Sum):-write(Sum).
calc(N,Sum):-mod_n(N,_,Add),Sum1 is Sum+Add,N1 is N+1,calc(N1,Sum1).

問い2
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%202
まあ少しくらいの工夫はする。
マクローリン展開を使う方法は私には理解できなかった。

fina(_,_,F,Sum):-F>=4000000,write(Sum),!.
fina(A,B,F,Sum):-B1 is 2*A+3*B,
A1 is F,F1 is A1+2*B1,Sum1 is Sum+F,fina(A1,B1,F1,Sum1).

問い3
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
√まで求めればいいんだけどまあ小さい値で割り切れることはわかってるので特に気にしない。

soinn(1,N):-write(N),!.
soinn(N,A):-0=:= N mod A,!,N1 is N/A,soinn(N1,A).
soinn(N,A):-A1 is A+1,soinn(N,A1).

問い4

findallを使ってる時点で超手抜き。
末尾再帰で書くのが本当の正解。

kaibunn(C):-
between(100,999,N),
between(100,N,M),
C is N*M,
numrev(C,0,C1),C=:=C1.

main4:-findall(C,kaibunn(C),List),mymax(List,0,Max),write(Max).

問い5
普遍的に解けるように書いてもよかったのだけど。
手抜きで解いた。
正しくは1～20までの素数のリストを求め、その素数aがa^n<=20となるｎを求めてから計算する。

calc([],[],Ans):-!,write(Ans).
calc([X|Rest],[Y|Rest1],Ans):-Ans1 is Ans*(X^Y),calc(Rest,Rest1,Ans1).
main5:-Powers=[4,2,1,1, 1, 1,1 ,1],
Base =[2,3,5,7,11,13,17,19],
calc(Base,Powers,1).

問い6
うーんそのまま素直に実装するのが一番いいコードに思えるんだけど？
なにか賢い解き方があるのかな？
数式一行になるとか？

calc6(SumA,SumB,101):-!,
Ans is SumB*SumB-SumA,write(Ans).
calc6(SumA,SumB,N):-
SumA1 is SumA+N*N,
SumB1 is SumB+N,
N1 is N+1,
calc6(SumA1,SumB1,N1).

問い7
素数のリストを伸ばすだけの手抜き実装。
特徴遅い、、、

prime_check([X|Rest],N,[X|Re1],1):-N<X*X,!,append(Rest,[N],Re1).
prime_check([X|Rest],N,[X|Rest],0):-0=:=N mod X,!.
prime_check([X|Rest],N,[X|Result],Add):-prime_check(Rest,N,Result,Add).
search7(_,N,10001):-!,N1 is N-1,write(N1).
search7(PList,N,Count):-
N1 is N+1,
prime_check(PList,N,PList1,Add),
Count1 is Count+Add,
search7(PList1,N1,Count1).

問い8
Ｎに1000桁の数字を代入してＲｅｓultで答えが返ってくる。
賢い方法ってあるのかしら？

calc8(N,Ans,Ans):-N<10000,!.
calc8(N,Max,Result):-N1 is N mod 10,N2 is (N//10) mod 10,N3 is (N//100) mod 10,
                     N4 is (N//1000) mod 10,N5 is (N//10000) mod 10,
                     Temp is N1*N2*N3*N4*N5,(Max<Temp->Max1 is  Temp;Max1 is Max),NN is N//10,calc8(NN,Max1,Result).

問い9
1000=k(*1)
を満たすｋ,m,nの組み合わせを見つける問題。
きちんと実装すると計算量は1000回以下になるが、まあ現状の500*24回でもそんなに悪くないと思う・

gcd(M,0,M):-!.
gcd(M,N,Result):-
	N1 is M mod N,
       gcd(N,N1,Result).
main9:-
between(2,24,M),
0=:=500 mod M,
between(1,500,R),
0=:=500 mod R,
Sum is 500 //R,
S is Sum // M,
N is S-M,
N<M,
0<N,
gcd(M,N,Re),
Re=:=1,
1=:=(M-N) mod 2,
A is R*(M*M-N*N),
B is R*2*M*N,
C is R*(M*M+N*N),
write([ans,A,B,C]).