[topic] 分数の発見
Posted feedbacks - Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | def gcd(m, n):
assert m > 0
assert n > 0
while n:
m, n = n, m % n
assert m > 0
return m
class Rational:
def __init__(self, b, c):
g = gcd(b, c)
self.b = b // g
self.c = c // g
def __repr__(self):
return "%d/%d" % (self.b, self.c)
def __cmp__(self, that):
return self.b * that.c - self.c * that.b
def value(self):
return float(self.b) / self.c
def rationalize(a):
rationals = []
for c in xrange(1, 10):
b = int(a * c + 0.5)
r = Rational(b, c)
if r.b == b:
rationals.append(r)
rationals.sort(key=lambda r: abs(a - r.value()))
return rationals
def solve(a):
print "a = %f" % a, " ".join(repr(r) for r in rationalize(a))
def main():
solve(1.732051)
solve(3.141593)
solve(1920.0 / 1080)
if __name__ == '__main__':
main()
|


gandalf #6278() Rating1/1=1.00
schemeにはrationalizeという手続きがありますが、これは結果を一つしか返しません。そして、複数の結果が欲しい場合も稀にあります。
そこで、非負の実数aが一つ与えられたときに、以下の条件を満たす分数b/cをaに近い順に全て表示する手続きを考えてみてください。条件は、 1. 分数b/cよりaに近い分数d/cは存在しない 2. 分数b/cは既約 3. cは1桁の整数 です。
例をいくつかあげます(あってると思うけど...)。
a = 1.732051 12/7 7/4 16/9 5/3 9/5 3/2 2/1
a = 3.141593 22/7 25/8 19/6 28/9 16/5 13/4 3/1
a = 1920 / 1080 16/9 9/5 7/4 11/6 12/7 5/3 2/1
[ reply ]