华为OJ——将真分数分解为埃及分数

将真分数分解为埃及分数

题目描述

分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。

接口说明

 /*  功能: 将分数分解为埃及分数序列  输入参数：      String pcRealFraction:真分数(格式“8/11”)  返回值：      String pcEgpytFraction:分解后的埃及分数序列(格式“1/2+1/5+1/55+1/100”)  */

 public static String  ConvertRealFractToEgpytFract(String pcRealFraction)  {   return null;  }

输入描述:

输入一个真分数，String型

输出描述:

输出分解后的string

输入例子:

8/11

输出例子:

1/2+1/5+1/55+1/110

解答代码：

#include<iostream> #include<fstream> #include<string> #include<cstring> #include<vector> #include<set> #include<algorithm> #include<ctime> #include<sstream> using namespace std; int converFromString(const string &s) { istringstream i(s); int x; if(i>>x) return x; return 0; } string getStr(int a) { string res=""; do { res.insert(0, 1, a%10 + '0'); a/=10; } while(a); return res; } int main() { string s; int a,b,c,pos; while(cin>>s) { string result=""; pos=s.find('/'); a=converFromString(s.substr(0,pos)); b=converFromString(s.substr(pos+1,s.length())); c=0; while(a!=1) { if(b%(a-1)==0) { result += "1/"+getStr(b/(a-1))+'+'; a=1; } else { c=b/a+1; result+="1/"+getStr(c)+'+'; a=a*c-b; b=c*b; if(b%a==0) { b=b/a; a=1; } } } result+= "1/"+getStr(b); cout<<result<<endl; } return 0; }