※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。


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).