「プロジェクトオイラー問30」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問30 - (2014/02/14 (金) 10:11:06) の1つ前との変更点

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

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

+http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2030
 
+*Problem 30 「各桁の5乗」 †
+驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.
+
+1634 = 1^4 + 6^4 + 3^4 + 4^4
+8208 = 8^4 + 2^4 + 0^4 + 8^4
+9474 = 9^4 + 4^4 + 7^4 + 4^4
+ただし, 1=14は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である.
+
+
+各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.
+
+
+
+解法
+9^5*7<1000000以下なので7桁以上は検討する必要がありません。
+0~9までを含んだ数を重複なく反辞書順に6個並べたリストを1セットとしてこれを5005個生成します。
+このリストの5乗和を計算し、その数を各桁のリストに戻し辞書順に並べリストをリバースします。
+リバースしたものとリストが同じになればそれの5乗和は答えの一つです。
+そうするとBigO(5005)の定数倍で処理が完了します。
+
+
+ perm(X,_,6,X):-!.
+ perm(X,P,Keta,Result):-
+ 	Keta1 is Keta+1,
+ 	perm([P|X],P,Keta1,Result).
+ perm(X,P,Keta,Result):-
+ 	P<9,
+ 	P1 is P+1,
+ 	perm(X,P1,Keta,Result).
+ to5([],0):-!.
+ to5([X|Xs],Result):-
+ 	to5(Xs,Re),
+ 	Result is Re+X^5.
+ 
+ numToList(_,6,[]):-!.
+ 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),
+ 	to5(Perm,Num),
+  	numToList(Num,0,List),
+ 	Num>1,
+ 	msort(List,List1),
+ 	reverse(List1,List2),
+ 	List2==Perm.
+ sum([],0):-!.
+ sum([X|Xs],Result):-
+  	sum(Xs,Re),
+ 	Result is Re+X.
+ 
+ main30:-
+ 	findall(P,perm([],0,0,P),Perms),
+ 	length(Perms,Len),
+ 	write([datesize,Len]),
+ 	findall(Num,all_check(Perms,Num),Nums),
+  	write(Nums),
+ 	sum(Nums,Ans),
+ 	write([ans,Ans]).