真分数的最大埃及分数

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

问题描述
把一个真分数分解为埃及分数和的形式
Input:3 5
Output:1/2 1/10(35=12+110

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!