http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2032
Problem 32 「パンデジタル積」 †
すべての桁に 1 から n が一度だけ使われている数をn桁の数がパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.

7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.

掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.

HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.



解法
a*b=cとすると
a<=b<cとしても一般性を失いません。
するとaは2桁まで、bは4桁以上にはなりえません。
残りの数がCとマッチするかだけ調べればいいと分かります。


toNum([],0):-!.
toNum([X|Xs],Result):-toNum(Xs,Re),Result is Re*10+X.

to_list(0,[],[]):-!.
to_list(N,[X|Result],[_|Rest]):-
	X is N mod 10,
	N1 is N//10,
	to_list(N1,Result,Rest).

listA([],Nums,2,Nums):-!.
listA([],Nums,KetaA,Nums):-KetaA>0.
listA([X|A],Nums,KetaA,ReNums):-
	select(X,Nums,Nums1),
	KetaA1 is KetaA+1,
	listA(A,Nums1,KetaA1,ReNums).

listB(_,_,KetaA,KetaB,_):-KetaA+KetaB-1>4,!,fail.
listB([],Nums,KetaA,KetaB,Nums):-KetaA=<KetaB.
listB([X|B],Nums,KetaA,KetaB,ReNums):-
	select(X,Nums,Nums1),
	KetaB1 is KetaB+1,
	listB(B,Nums1,KetaA,KetaB1,ReNums).

sum([],0):-!.
sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X.

search(NumC):-
	Nums=[1,2,3,4,5,6,7,8,9],
	listA(A,Nums ,0,Nums1),
	length(A,KetaA),
	listB(B,Nums1,KetaA,0,Nums2),
	toNum(A,NumA),
	toNum(B,NumB),
 	NumC is NumA*NumB,
	to_list(NumC,C,Nums2),
msort(C,C1),
	C1==Nums2.

 

main32:-findall(C,search(C),AnsList),
	write(AnsList),
	sort(AnsList,AnsList1),
	sum(AnsList1,Ans),
	write(Ans).

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2014年02月14日 13:03