[topic] 分数の発見

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

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

Index

Feed

Other

Link

Pathtraq

loading...