「プロジェクトオイラー問３２」の編集履歴（バックアップ）一覧はこちら

「プロジェクトオイラー問３２」(2014/02/14 (金) 13:03:05) の最新版変更点

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

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

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は２桁まで、ｂは４桁以上にはなりえません。
残りの数が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).

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は２桁まで、ｂは４桁以上にはなりえません。
残りの数が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).