「プロジェクトオイラー問３４」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問３４ - (2014/02/14 (金) 14:19:53) のソース

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


*Problem 34 「桁の階乗」 †
145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.

各桁の数の階乗の和が自分自身と一致するような数の和を求めよ.

注: 1! = 1 と 2! = 2 は総和に含めてはならない.




解法
7桁までの長さで一桁ずつ昇順で保持した重複のない数字のリストを作ります。
リストの要素をPermとします。
Permを各桁とみて階乗の和Numを計算します。
Numを各桁のリストに戻してソートしList1とします。
List1とPermが同じならその数Numは条件を満たす数です。
条件を満たす数は重複する数があるのでsort関数でそれを取り除き、最後に集計すれば答えです。
ね、簡単でしょ。
BigOはBigO(30887)の定数倍。

 fact(0,1):-!.
 fact(N,Result):-N1 is N-1,fact(N1,Re),Result is Re*N.
 
 
 perm(X,_,7,X):-!.
 perm(X,_,_,X).
 perm(X,P,Keta,Result):-
 	Keta1 is Keta+1,
 	perm([P|X],P,Keta1,Result).
 perm(X,P,Keta,Result):-
 	P>0,
 	P1 is P-1,
 	perm(X,P1,Keta,Result).
 
 to_fact([],0):-!.
 to_fact([X|Xs],Result):-
 	to_fact(Xs,Re),
 	fact(X,Add),
 	Result is Re+Add.
 
 numToList(0,_,[]):-!.
 numToList(_,7,[]):-!.
 numToList(N,Keta,[X|Xs]):-
 	!,
 	N1 is N//10,
 	X  is N mod 10,
 	Keta1 is Keta+1,
 	numToList(N1,Keta1,Xs).
 
 all_check(Perms,Num):-
 	member(Perm,Perms),
 	to_fact(Perm,Num),
 	Num>2,
  	numToList(Num,0,List),
 	msort(List,List1),
 	List1==Perm.
 
 sum([],0):-!.
 sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X.
 
 main34:-
 	findall(Perm,perm([],9,0,Perm),Perms),
  	findall(Num,all_check(Perms,Num),Nums),
 	sort(Nums,Nums1),
 	write(Nums1),
 	sum(Nums1,Ans),
 	write(Ans).