小数转分数

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1717

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

 

思路：

1.对于不循环小数，小数位乘倍数，再除去倍数。例如, 0.351转化成，0.351 * 1000 / 1000, 即求351/1000，求gcd约分即可。

2.对于循环小数，利用循环小数的性质，x = 0.31(25)，令m = 0.31(25) * 100 = 31.(25), n = 0.31（25） * 1000 = 3125.(25)，即 (m - n) = x * (100 - 1000); x = (m - n) / (100 - 1000);求gcd约分

#include<stdio.h>
#include<string.h>
#define LL long long

char s[20];

LL GCD(LL a, LL b)//求最大公约数 
{
    LL c;
    while(b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T --)
    {
        LL x = 0, y = 1;
        int flag = 0, id;
        scanf("%s", s);
        int len = strlen(s);
        for(int i = 2; i < len; i ++)
        {
            if(s[i] == '(')
            {
                flag = 1;
                id = i;
                break;
            }
            x = x * 10 + (s[i] - '0');//分子扩大多少 
            y *= 10;//分母就除去多少 
        }
        if(flag == 0)  //没有循环小数
        {
            LL temp = GCD(x, y);
            printf("%lld/%lld
", x / temp, y / temp);
        }
        else //有循环小数 利用循环小数的性质求解 
        {
            LL xx = x, yy = y;
            id ++;
            for(int i = id; i < len; i ++)
            {
                if(s[i] == ')')
                    continue;
                xx = xx * 10 + (s[i] - '0');
                yy *= 10;
            }
            LL a = xx - x;
            LL b = yy - y;
            LL temp = GCD(a, b);
            printf("%lld/%lld
", a / temp, b / temp);
        }
    }
    return 0;
}