首页 > ACM题库 > HDU-杭电 > HDU 1717 小数化分数2-数论应用-[解题报告] C++
2013
12-21

HDU 1717 小数化分数2-数论应用-[解题报告] C++

小数化分数2

问题描述 :

Ray 在数学课上听老师说,任何小数都能表示成分数的形式,他开始了化了起来,很快他就完成了,但他又想到一个问题,如何把一个循环小数化成分数呢?
请你写一个程序不但可以将普通小数化成最简分数,也可以把循环小数化成最简分数。

输入:

第一行是一个整数N,表示有多少组数据。
每组数据只有一个纯小数,也就是整数部分为0。小数的位数不超过9位,循环部分用()括起来。

输出:

对每一个对应的小数化成最简分数后输出,占一行。

样例输入:

3
0.(4)
0.5
0.32(692307)

样例输出:

4/9
1/2
17/52

小数(纯循环小数、混循环小数、不循环小数)化成分数

纯循环小数的小数部分可以化成分数,这个分数的分子是一个循环节表示的数,分母各位上的数都是9。9的个数与循环节的位数相同。
一个混循环小数的小数部分可以化成分数,这个分数的分子是第二个循环节以前的小数部分组成的数与小数部分中不循环部分组成的数的差。分母的头几位数是9,末几位是0。9的个数与循环节中的位数相同,0的个数与不循环部分的位数相同
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
__int64 fun(__int64 a,__int64 b)
{
    __int64 r=1;
    while(r!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    int n;
    char chl[15];
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",chl);
        char str1[15],str2[15];
        memset(str1,0,sizeof(str1));//没加这两句,错了四次。
        memset(str2,0,sizeof(str2));
        if(chl[2]=='(')
        {
            int i,j;
            for(i=0,j=3;chl[j]!=')';j++)
                str1[i++]=chl[j];
            str1[i]='\0';
            __int64 d1=atol(str1);
            for(j=0;j<i;j++)
             str2[j]='9';
            __int64 d2=atol(str2);
            __int64 m=fun(d1,d2);
            printf("%I64d/%I64d\n",d1/m,d2/m);
        }
        else if(chl[strlen(chl)-1]!=')')
        {
            int i,j;
            for(i=2,j=0;i<strlen(chl);i++)
               str1[j++]=chl[i];
            str1[j]='\0';
            __int64 d1=atol(str1);
            str2[0]='1';
            for(i=1;i<=j;i++)
               str2[i]='0';
            __int64 d2=atol(str2);
            __int64 m=fun(d1,d2);
            printf("%I64d/%I64d\n",d1/m,d2/m);
        }
        else
        {
            int i,j;
            for(i=2,j=0;i<strlen(chl);i++)
            {
                if(chl[i]=='('||chl[i]==')') continue;
                str1[j++]=chl[i];
            }
            str1[j]='\0';
            __int64 d1=atol(str1);
            for(i=2,j=0;chl[i]!='(';i++)
              str1[j++]=chl[i];
              str1[j]='\0';
              __int64 d2=atol(str1);
              d1=d1-d2;
              for(i=0;i<strlen(chl)-4-j;i++)
                str2[i]='9';
               for(int t=0;t<j;t++)
                 str2[i++]='0';
                 str2[i]='\0';
                d2=atol(str2);
              __int64 m=fun(d1,d2);
              printf("%I64d/%I64d\n",d1/m,d2/m);
        }
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/chl_3205/article/details/8648056


  1. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了