|
|
[Google挑战赛第二轮真题]1000分 RecurringNumbers
Google™ Code Jam - 中国编程挑战赛
Problem Statement
A rational number is defined as a/b, where a and b are integers,
and b is greater than 0. Furthermore, a rational number can be written
as a decimal that has a group of digits that repeat indefinitely. A
common method of writing groups of repeating digits is to place them
inside parentheses like 2.85(23) = 2.852323 ... 23...
Given a decimal representation of a rational number in decimalNumber,
convert it to a fraction formatted as "numerator/denominator", where
both numerator and denominator are integers. The fraction must be
reduced. In other words, the denominator must be as small as possible,
but greater than zero.
Definition
Class: RecurringNumbers
Method: convertToFraction
Parameters: string
Returns: string
Method signature: string convertToFraction(string decimalNumber)
(be sure your method is public)
Constraints
- decimalNumber will have between 3 and 10 characters inclusive.
- decimalNumber will contain only characters '0' - '9', '.', '(' and ')'.
- The second character in decimalNumber will always be '.'.
- There will be at most one '(' and ')' in decimalNumber.
- '(' in decimalNumber will be followed by one or more digits ('0' -
'9'), followed by ')'.
- ')' in decimalNumber will not be followed by any other character.
Examples
0) "0.(3)"
Returns: "1/3"
0.(3) = 0.333... = 1/3
1) "1.3125"
Returns: "21/16"
Note there are no recurring digits here, although we could write it as
1.3125(0) or 1.3124(9).
2) "2.85(23)"
Returns: "14119/4950"
2.85(23) = 2.852323... = 285/100 + 23/9900 = 28238/9900 = 14119/4950.
Make sure to reduce the fraction, as shown in the final step.
3) "9.123(456)"
Returns: "3038111/333000"
4) "0.111(1)"
Returns: "1/9"
5) "3.(000)"
Returns: "3/1"
大意就是：假设输入2.85(23)，一对圆括号内的数表示循环部分，则要求输出这个数的分数形式14119/4950.
代码写的拙劣，请指正;)
 //test.cpp
#include<iostream>
#include<string>
using namespace std;
using std::string;
int cd(int a,int b);
class RecurringNumbers
   {
 public:
string convertToFraction(string decimalNumber);
 };
string RecurringNumbers::convertToFraction(string decimalNumber)
{
char flag_loop=0;
int tmp;
int d1,d2;
int a1,b1,a2,b2;
  int pows[8]={1,10,100,1000,10000,100000,1000000,10000000};
d1=decimalNumber.find('(');
if(d1>0)
{
d2=decimalNumber.find(')');
if(d2>0)
{
flag_loop=1;
// cout<<d1<<endl<<d2<<endl;
a2=atoi(decimalNumber.data()+d1+1);
b2=(pows[d2-d1-1]-1)*pows[d1-2];
 }
}
else
{
d1=decimalNumber.length();
d2=3;
a2=0;
b2=1;
}
if(d1<2)
d1=2;
b1=pows[d1-2];
a1=atof(decimalNumber.c_str())*b1;
/**//* cout<<a1<<"/"<<b1;
if(a2)
cout<<"+"<<a2<<"/"<<b2;
cout<<endl;
*/
if(a2)
{
tmp=cd(b1,b2);
a1=b2/tmp*a1;
a2=b1/tmp*a2;
a1=a1+a2;
b1=b1/tmp*b2;
// cout<<a1<<"/"<<b1<<endl;
}
tmp=cd(a1,b1);
if(tmp>1)
{
a1 /= tmp;
b1 /= tmp;
}
// cout<<a1<<"/"<<b1<<endl;
char buf[20];
sprintf(buf,"%d/%d",a1,b1);
return string(buf);
}
int cd(int a,int b) //求公约数
{
int d1,d2,tmp;
d1=a<b?a:b;
d2=a<b?b:a;
tmp=d2%d1;
while(tmp)
{
d2=d1;
d1=tmp;
tmp=d2%d1;
}
return d1;
}
int main()
{
string decNum;//="1.0(3)";
RecurringNumbers num1;
while(1)
{
cout<<"input: ";
cin>>decNum;
if(atof(decNum.c_str()))
{
cout<<"output: "<<num1.convertToFraction(decNum)<<endl;
cout<<endl;
}
else
{
cout<<"exit ";
break;
}
}
system("pause");
return 1;
}
|