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

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

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

*Problem 33 「桁消去分数」 †
49/98は面白い分数である.「分子と分母からそれぞれ9を取り除くと, 49/98 = 4/8 となり, 簡単な形にすることができる」と経験の浅い数学者が誤って思い込んでしまうかもしれないからである. (方法は正しくないが，49/98の場合にはたまたま正しい約分になってしまう．)

我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

このような分数のうち, 1より小さく分子・分母がともに2桁の数になるような自明でないものは, 4個ある.

その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.


解法
ルールが恣意的だということはその恣意性をコードに記述しなくていけないということです。
もしかしたらこの問題には深い意味があるのかもしれませんが私にはルールを見つけられませんでした。
というわけで愚直にそのまま実装します。
幸いPrologは恣意的で不合理なルールを記述するのに向いた言語です。
素直にかけます。
最後に出てきた答えを手計算で既約分数に直せば答えです。


 gcd(0, B, B).
 gcd(A, B, G) :- A > 0, R is B mod A, gcd(R, A, G).
 
 permAB([A1,A2]):-
 	X =[1,2,3,4,5,6,7,8,9],
 	member(A1,X), 
 	member(A2,X).
 
 toNum([A1,A2],X):-
 	X is A1*10+A2.
 
 dellNum([X,A],[X,B],A,B).
 dellNum([X,A],[B,X],A,B).
 dellNum([A,X],[X,B],A,B).
 dellNum([A,X],[B,X],A,B).
 
 search([NumA3,NumB3]):-
 	permAB(A),
 	permAB(B),
 	toNum(A,NumA),
 	toNum(B,NumB),
 	NumA<NumB,
 	dellNum(A,B,NumA2,NumB2),
 	gcd(NumA,NumB,G),
 	NumA1 is NumA//G,
 	NumB1 is NumB//G,
 	gcd(NumA2,NumB2,G1),
 	NumA3 is NumA2//G1,
  	NumB3 is NumB2//G1,
 	NumA1=:=NumA3,
 	NumB1=:=NumB3.
 
 mults([],[1,1]):-!.
 mults([[A,B]|Xs],[ReA1,ReB1]):-
 	mults(Xs,[ReA,ReB]),
  	ReA1 is ReA*A,
 	ReB1 is ReB*B.
 
 
 main33:-
 	findall(N,search(N),AnsList),
 	write(AnsList),
 	mults(AnsList,Ans),
 	write(Ans).