贪心-埃及分数

本文主要是介绍贪心-埃及分数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

把一个真分数表示为埃及分数之和的形式。所谓埃及分数，是指分子为1的分数。如7/8 = 1/2 + 1/3 + 1/24。

问题分析

一个真分数a/b，要寻找其最大的1/c，那么很容易想到的方法是枚举。但是枚举法效率不高，所以这里采用贪心算法。
a/b肯定为<1的数字，那么 c = b / a 既可以理解为b比a大多少倍，那么显然余数不为0 时c = b / a + 1。这样很容易找到最大的分数的分母。

算法设计

1. 设某个真分数的分子为A(!=1),分母为B。
2. 把B除以A的商的整数部分加1后的值作为埃及分数的分母 C。
3. 输出 1/C。
4. 将A乘以C减去B作为新的A。
5. 将B乘以C作为新的B
6. 如果A大于1且能整除B，则最后一个埃及分数的分母为B/A.
7. 如果A=1,则最后一个分母为B；否则跳转到2步骤

代码实现

#include <stdio.h>int main() {int a, b, c;      //a为分子，b为分母printf("请输入分子:");scanf("%d", &a);printf("请输入分母:");scanf("%d", &b);//如果是假分数，则出错if (a >= b) {printf("输入错误!\n");return -1;}printf("%d/%d=",a,b);//分子为1或者分数可以约分if (a == 1 || b % a == 0){printf("1/%d", b / a);return 0;}while (a != 1) {c = b / a + 1;     //计算出分母a = a * c - b;b = b * c;printf("1/%d",c);if (a > 1){printf(" + ");}if (b%a == 0 || a == 1){printf("1/%d",b/a);a = 1;}}return 0;
}

这篇关于贪心-埃及分数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---