yjm0105 阅读(720) 评论(6)
[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
;
}


评论列表
周星星
re: 求循环小数的分数形式
俺对“d1-2”表示怀疑,我想这个2来自于整数位数加上一个小数点,但题目是不是规定了整数位数只有一个?(洋文不好,所以没看题目)。
流云
re: **
The second character in decimalNumber will always be '.'
是啊,第2个位置上总是小数点.

...俺英语也不好,应该没理解错吧w_w
周星星
re 流云:
呵呵,我应该看一下题目的。谢谢!
jzhang
d1,d2看着晕了
搂主你就描述一下算法就好了,呵呵。
流云
re: 求循环小数的分数形式
汗,不太会取名字~~
最上面的d1是用来计算非循环部分的数的位数的;
算法嘛,其实就是...
比如2.85(23),2.85是非循环部分(记为ND,小数点后位数为sD,去掉小数点后记为N,N的长度记为sN),23是循环部分(记为L,L的长度记为sL) ,

要求的结果是A/B:
A/B由下面2部分之和化简而来:1.N / (10的sN次方); 2. L / (10的sL次方 - 1) / (10的sD次方)

对于2.85(23)就是: 285/100 + 23/99/100 = 14119/4950
jzhang
good
明白了,呵呵。谢谢

发表评论
切换编辑模式