首页 > 代码库 > hdu 1717

hdu 1717

2024-07-17 20:34:44   216人阅读

小数化分数2

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3037    Accepted Submission(s): 1237

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）
 
Recommend
lcy
 
题解：首先要知道无限循环小数分数形式的构造方法：分子为最小循环节，分母为对应位数的99..9 如已知无限循环小数：0.568568……以568为循环节，那么这个小数的分数形式就是568/999，题中，我们将小数的有限部分和无限循环部分分开处理，得到两个分数，再相加化简，所得即为所求。
来源：http://www.cnblogs.com/kevince/p/3905378.html

 

  1 #include<iostream>  2 #include<cstring>  3 #include<cstdlib>  4 #include<cstdio>  5 #include<algorithm>  6 #include<cmath>  7 #include<queue>  8 #include<map>  9  10 #define N 1010 11 #define M 15 12 #define mod 1000000007 13 #define mod2 100000000 14 #define ll long long 15 #define maxi(a,b) (a)>(b)? (a) : (b) 16 #define mini(a,b) (a)<(b)? (a) : (b) 17  18 using namespace std; 19  20 int T; 21 char s[N]; 22 int f1,f2; 23  24 ll gcd(ll x,ll y) 25 { 26     if(y==0) 27         return x; 28     return gcd(y,x%y); 29 } 30  31 int main() 32 { 33     int i; 34     //freopen("data.in","r",stdin); 35     scanf("%d",&T); 36     getchar(); 37     //for(int cnt=1;cnt<=T;cnt++) 38     while(T--) 39     //while(scanf("%d%d",&n,&q)!=EOF) 40     { 41         scanf("%s",s); 42        // getchar() 43         //printf(" %s\n",s); 44         int l=strlen(s); 45         int flag=0; 46         f1=f2=0; 47         ll x1; 48         ll a,x; 49         ll b=0; 50         ll te; 51         a=0; 52         x1=1; 53         x=1; 54         ll g1,g2; 55         ll y; 56         for(i=2;i<l;i++){ 57             if(flag==0) 58             { 59                 if(s[i]!=‘(‘){ 60                     f1=1; 61                     x1*=10; 62                     b*=10; 63                     b+=s[i]-‘0‘; 64                 } 65                 else{ 66                     flag=1; 67                     f2=1; 68                 } 69             } 70             else{ 71                 if(s[i]!=‘)‘){ 72                     x*=10; 73                     a*=10; 74                     a+=s[i]-‘0‘; 75                 } 76             } 77            // printf("   %d %d %I64d %I64d %I64d %I64d\n",i,flag,b,x1,a,x); 78         } 79         //printf("   %d %d %I64d %I64d %I64d %I64d\n",f1,f2,b,x1,a,x); 80        te=1; 81        if(f1==1){ 82             g1=gcd(b,x1); 83             if(g1!=0){ 84                 b/=g1; 85                 te=x1; 86                 x1/=g1; 87             } 88        } 89  90         if(f2==1){ 91             y=x-1; 92             y*=te; 93             g2=gcd(a,y); 94             if(g2!=0){ 95                 a/=g2; 96                 y/=g2; 97             } 98         } 99 100 101 102         //printf(" %d %d %d %d\n",b,x1,a,y);103         //printf("   %d %d %I64d %I64d %I64d %I64d\n",f1,f2,b,x1,a,y);104         if( (f1+f2)==2){105            // y*=x1106 107             ll c=(x1*a+y*b);108             ll d=y*x1;109             // printf(" %I64d/%I64d\n",c,d);110             ll g3=gcd(c,d);111             if(g3!=0){112                 c/=g3;113                 d/=g3;114             }115             printf("%I64d/%I64d\n",c,d);116         }117         else{118             if(f1==1)119                 printf("%I64d/%I64d\n",b,x1);120             else121                 printf("%I64d/%I64d\n",a,y);122         }123 124 125 126 127 128 129     }130 131     return 0;132 }

 


联系
我们