Project Euler Problem 033
http://projecteuler.net/index.php?section=problems&id=33
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2033
49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである. 我々は 30/50 = 3/5 のようなタイプは自明な例だとする. 1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある. その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.
正直問題の意味が分からなかったんだけど、答えが合ってたので良しとした。
(a * 10 + b) / (b * 10 + c) = a / c
この条件に当てはまる数を探して、足し算して約分した。
import datetime def reduction(fraction): n = fraction[0] m = fraction[1] def gcd(a, b): if b == 0: return a return gcd(b, a % b) x = gcd(n, m) return (n / x, m / x) def curious_fractions(): result = [] for b in xrange(1, 10): for c in xrange(1, 10): m = b * 10 + c for a in xrange(1, b): n = a * 10 + b if float(n) / m == float(a) / c: print '', (n, m) fraction = reduction((n, m)) result.append(fraction) return result def euler033(): l = curious_fractions() a = reduce(lambda a, b: (a[0]*b[0], a[1]*b[1]), l) a = reduction(a) print a begin = datetime.datetime.now() euler033() end = datetime.datetime.now() print end - begin
答え: 100
実行時間: 0.001888秒くらい