埃及分数是指分子是1的分数，也叫单位分数。古代埃及人在进行分数运算时。只使用分子是1的分数。

问题描述
把一个真分数分解为埃及分数和的形式
Input：3 5
Output：1/2 1/10（$\frac{3}{5}=\frac{1}{2}+\frac{1}{10}$）

优秀博客参考：https://www.jianshu.com/p/da04c77e11d0
算法分析
设真分数 $\frac{a}{b}$ ，b除以a得c，余数为d
则有 $b=a\cdot c+d$ ，两边同时除以a
$\frac{b}{a}=c+\frac{d}{a}$ ，已知$d<a$
则有 $\frac{b}{a}<c+1$
$\frac{a}{b}>\frac{1}{c+1}$
令e = c+1，则$\frac{1}{e}$是$\frac{a}{b}$最大埃及分数，因此可以使用贪心思想，不断分解 $\frac{a}{b}$ ，直至a=1，分解结束
伪代码为 $f(\frac{a}{b})=\frac{1}{e}+f(\frac{a}{b}-\frac{1}{e})$
通分一下 $\frac{a}{b}-\frac{1}{e}=\frac{a\cdot e-b}{b\cdot e}$ ，注意这个分式上下还要约分一下，所以要算一下Gcd.
——————————————————————代码如下————————————————————

int Gcd(int a, int b)
{
	if(b == 0)
		return a;
	return Gcd(b, a%b);
}
int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	do{
		int e = b / a + 1;
		printf("1/%d ", e);
		a = a * e - b;
		b = b * e;
		int d = Gcd(a, b);
		a /= d;
		b /= d;
	}while(a > 1); 
	printf("1/%d ", b);
	return 0;
}
Copy