埃及分数求解

设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：

步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1）

步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r)/b(q1+1）

步骤三：重复步骤2，直到分解完毕

3/7=1/3+2/21=1/3+1/11+1/231

13/23=1/2+3/46=1/2+1/16+1/368

以上其实是斐波那契提出的一种求解埃及分数的贪心算法，准确的算法表述应该是这样的：

设某个真分数的分子为a，分母为b;

把b除以a的商部分加1后的值作为埃及分数的某一个分母c；

将a乘以c再减去b，作为新的a；

将b乘以c，得到新的b；

如果a大于1且能整除b，则最后一个分母为b/a；算法结束；

或者，如果a等于1，则，最后一个分母为b；算法结束；
def Aiji(a, b):
list = []
while a!=1:
if b%(a-1)==0:
list.append(b//(a-1))
a=1
else:
c = (b // a) + 1
a = a-b%a
b = b * c
list.append(c)
if b%a==0:
b=b//a
a=1
list.append(b)
return list
while True:
try:
list1 = input().split("/")
fenzi = int(list1[0])
fenmu = int(list1[1])
lit = Aiji(fenzi, fenmu)
lit1=[]
for i in lit:
i = str(i)
i="1"+"/"+i
lit1.append(i)
print("+".join(lit1))
except:
break