题解 | #密码强度等级#
将真分数分解为埃及分数
http://www.nowcoder.com/practice/e0480b2c6aa24bfba0935ffcca3ccb7b
#根据任何真分数都是大于等于（分母除以分子加一）分之一来递归，使用数组接收递归的时候的减去的数据对应的分母
def dfs(m, n, l):
m, n = dfs1(m, n)
if m == 1:
l.append(n)
else:
x = int(n / m) + 1
m = m * x - n
n = n * x
dfs(m, n, l)
l.append(x)
return l
# 对传入的两个数据做处理，不能含有公约数
def dfs1(m, n):
if m == 1:
return m, n
else:
for i in range(2, m + 1):
if m % i == 0 and n % i == 0:
return dfs1(int(m / i), int(n / i))
elif i == m:
return m, n
while True :
try:
l = []
la = list(map(int, input().split("/")))
l = dfs(la[0], la[1], l)
for i in range(0, len(l)):
l[i] = "1/" + str(l[i])
print("+".join(l))
except:
break
