题目描述：
分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。
注：真分数指分子小于分母的分数，分子和分母有可能gcd不为1！
如有多个解，请输出任意一个。
请注意本题含有多组样例输入！
输入描述：
输入一个真分数，String型
输出描述：
输出分解后的string
示例：
输入：
8/11
2/4
输出：
1/2+1/5+1/55+1/110
1/3+1/6
说明：
第二个样例直接输出1/2也是可以的
解题思路：
本题有两个方法：1）取巧；2）贪心算法。
1）直接输出n个1/X即可，比如8/11就输出1/11+1/11+。。。+1/11，emm取巧。
2）贪心算法即在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解 。令真分数8/11进行拆分，先找到比其小的最大埃及分数，也就是1/2，那么8/11-1/2等于5/22，则找其最大埃及分数，即1/5，以此类推直到找完所有的埃及分数。其算法实现如下：
- 假设真分数为a/b，那么b除以a可以得到c，余数为d。即
； - 两侧同除a，可以得到
; - 因为d是a的余数，所以d<a，那么
; - 两边取倒数，即
，1/(c+1)就是我们要找的最大埃及分数； - 令e=c+1，则有
； - 即表示减去一个最大埃及分数后，新的a=a*e-b，新的b等于b*e;
- 当a等于1时说明分解到头了，此时的b就是最后一个埃及分数的分母。
测试代码：
1）取巧方法。
#include<iostream> #include<string> using namespace std; int main() { string s; while (cin >> s) { string ans; int n; for (int i = 0; i < s.size(); i++) { if (s[i] == '/') { n = stoi(s.substr(0, i)); s = "1/" + s.substr(i + 1) + "+"; break; } } while (n--) { ans += s; } cout << ans.substr(0,ans.size()-1) << endl; } return 0; }
2）贪心算法。
#include<iostream> #include<string> using namespace std; int main() { string s; while (cin >> s) { string ans; int a,b; for (int i = 0; i < s.size(); i++) { if (s[i] == '/') { a = stoi(s.substr(0, i)); b = stoi(s.substr(i + 1)); break; } } while(1) { int e=b/a+1; ans+="1/"; ans+=to_string(e); a=a*e-b; b=b*e; ans+="+"; if(a==1) { ans+="1/"; ans+=to_string(b); break; } else if(a>1&&b%a==0) { ans+="1/"; ans+=to_string(b/a); break; } } cout<<ans<<endl; } return 0; }
