[파이썬] 이집트분수

>>> def egypt(x):
    ''' x = (a, b) which represent a/b
    '''
    r = []
    while x[1]%x[0]:
        m = x[1]//x[0] + 1
        r.append(m)
        x = (x[0]*m - x[1], x[1]*m)
    r.append(x[1]//x[0])
    print('+'.join('1/%d'%d for d in r))
    return r

>>> egypt((4, 5))
1/2+1/4+1/20
[2, 4, 20]
>>> egypt((2, 11))
1/6+1/66
[6, 66]
>>> egypt((761, 1000))
1/2+1/4+1/91+1/91000
[2, 4, 91, 91000]

분수의 이집트분수 분해를 구하는 코드. 버그 없는지 잘 모르겠는데, 일단 깔끔하게 됨.