小数化分数2http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=2§ionid=1&problemid=12 |
| Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 1646 Accepted Submission(s): 613 |
|
Problem Description
Ray 在数学课上听老师说，任何小数都能表示成分数的形式，他开始了化了起来，很快他就完成了，但他又想到一个问题，如何把一个循环小数化成分数呢?
请你写一个程序不但可以将普通小数化成最简分数，也可以把循环小数化成最简分数。 |
|
Input
第一行是一个整数N，表示有多少组数据。
每组数据只有一个纯小数，也就是整数部分为0。小数的位数不超过9位，循环部分用()括起来。 |
|
Output
对每一个对应的小数化成最简分数后输出，占一行。
|
|
Sample Input
3 0.(4) 0.5 0.32(692307) |
|
Sample Output
4/9 1/2 17/52 |
|
Source
2007省赛集训队练习赛（2）
|
首先我们要明确，无限小数可按照小数部分是否循环分成两类：无限循环小数和无限不循环小数。无限不循环小数不能化分数，这在中学将会得到详尽的解释；无限循环小数是可以化成分数的。那么，无限循环小数又是如何化分数的呢？由于它的小数部分位数是无限的，显然不可能写成十分之几、百分之几、千分之几……的数。其实，循环小数化分数难就难在无限的小数位数。所以我就从这里入手，想办法“剪掉”无限循环小数的“大尾巴”。策略就是用扩倍的方法，把无限循环小数扩大十倍、一百倍或一千倍……使扩大后的无限循环小数与原无限循环小数的“大尾巴”完全相同，然后这两个数相减，“大尾巴”不就剪掉了吗！我们来看两个例子：
⑴ 把0.4747……和0.33……化成分数。
想1： 0.4747……×100=47.4747……
0.4747……×100－0.4747……=47.4747……－0.4747……
(100－1)×0.4747……=47
即99×0.4747…… =47
那么 0.4747……=47/99
想2： 0.33……×10＝3.33……
0.33……×10－0.33……=3.33…－0.33……
(10-1) ×0.33……=3
即9×0.33……=3
那么0.33……=3/9=1/3
由此可见, 纯循环小数化分数,它的小数部分可以写成这样的分数：纯循环小数的循环节最少位数是几，分母就是由几个9组成的数；分子是纯循环小数中一个循环节组成的数。
⑵把0.4777……和0.325656……化成分数。
想1：0.4777……×10=4.777……①
0.4777……×100=47.77……②
用②－①即得:
0.4777……×90=47－4
所以, 0.4777……=43/90
想2：0.325656……×100=32.5656……①
0.325656……×10000=3256.56……②
用②－①即得:
0.325656……×9900=3256.5656……－32.5656……
0.325656……×9900=3256－32
所以, 0.325656……=3224/9900
将纯循环小数改写成分数，分子是一个循环节的数字组成的数；分母各位数字都是9，9的个数与循环节中的数字的个数相同.
将混循环小数改写成分数，分子是不循环部分与第一个循环节连成的数字组成的数，减去不循环部分数字组成的数之差；分母的头几位数字是9，末几位数字是0，9的个数跟循环节的数位相同，0的个数跟不循环部分的数位相同.
#include<stdio.h> #include<string.h> int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int main(){ char str[20]; int n; scanf("%d",&n); getchar(); while(n--){ scanf("%s",str); int i,flag=1; int a1=1,b1=0,a2=1,b2=0; for(i=2;str[i]!='\0';i++){ if(str[i]=='(') flag=0; if(str[i]>='0' && str[i]<='9'){ if(flag){ a1*=10; b1=b1*10+str[i]-'0'; } a2*=10; b2=b2*10+str[i]-'0'; } } //printf("a1=%d b1=%d a2=%d b2=%d\n",a1,b1,a2,b2); if(flag) printf("%d/%d\n",b1/gcd(a1,b1),a1/gcd(a1,b1)); else{ int tmp=gcd((a2-a1),(b2-b1)); printf("%d/%d\n",(b2-b1)/tmp,(a2-a1)/tmp); } } return 0; }