2011年8月16日星期二

Continued fraction

故名思義,Continued fraction就是可以不斷fraction的數,以2開方為例:

2 = 1.4142135623730951 = 1 + 1 1 0.4142135623730951 = 1 + 1 2 + 1 0.4142135623730951


可以不斷除下去,但是否一直是2呢,假設是:
n = 1 + 1 2 + 1 2 + 1 2 + n - 1 = 1 2 + 1 2 + 1 2 + n - 1 = 1 2 + n - 1 n 2 - 1 = 1 n = 2
運用了infinity series中的infinity items eliminiation方法,便成。

def continued_fraction(r, n=10):
    '''Return list of continued fraction of float r, maximum n items.

    >>> continued_fraction(math.sqrt(2))
    [1, 2, 2, 2, 2, 2, 2, 2, 2, 2]
    >>> continued_fraction(math.sqrt(5))
    [2, 4, 4, 4, 4, 4, 4, 4, 4, 4]
    >>> continued_fraction(math.sqrt(7))
    [2, 1, 1, 1, 4, 1, 1, 1, 4, 1]
    >>> continued_fraction(math.sqrt(8), 20)
    [2, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1]
    '''
    l = []
    for j in range(n):
        i = int(r)
        l.append(i)
        if r == i:
            break
        r = 1 / (r - i)
    return l

沒有留言:

發佈留言