poj 1930 （循环小数转化分数）

本文主要是介绍poj 1930 （循环小数转化分数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//思路

简单起见我们不考虑整数位。首先循环小数有两种，纯循环小数和混循环小数，先考虑前一种。
考虑小数 $A=0.\ \alpha \ \alpha \ \alpha \ \cdots$ ，其中 $\alpha$ 是一个n位整数.那么就可以写成分数求和形式,
$A=\frac{\alpha}{10^n} +\frac{\alpha}{10^{2n}}+\frac{\alpha}{10^{3n}}+\cdots$
利用等比数列求和公式，
$A=\alpha \frac{\frac{1}{10^n} }{1-\frac{1}{10^n}}=\frac{\alpha}{10^n-1}$

（其中的α，β可以代表多位数（比如α=2，那么n=1, α=13，那么n=2,α=523，那么n=3，同理β和m的关系也是这样的））
这时候结果就出来了， $10^n-1$ 恰好是n个9，因此
一个循环节长度为n的纯循环小数，化成分数的话，分子是循环节，分母是n个9.
那么再来看混循环小数，也就是小数 $0.\ \beta \ \alpha \ \alpha \ \alpha \ \cdots$ ，其中 $\alpha$ 是一个n位整数， $\beta$ 是一个m位整数.
由于 $B=0.\ \beta \ +\frac{1}{10^m} 0. \ \alpha \ \alpha \ \alpha \ \cdots$
利用上一步的结果，就有
$B=\frac{\beta}{10^m} +\frac{\alpha}{10^m (10^n-1)}=\frac{(10^n\beta+\alpha)-\beta}{10^m(10^n-1)}$
我们来看分子分母分别是什么，首先分母是n个9后面拼上m个0.
分子的话， $10^n\beta+\alpha$ 恰好是不循环部分拼上一个循环节，然后后面再减掉一个不循环部分.因此
一个循环节长度为n，不循环部分长度为m的混循环小数，化成分数的话，分母是n个9拼上m个0，分子是不循环部分和一个循环节拼起来的数减掉不循环部分.
第一部分还是很好理解的，举个例子
$0.171717\cdots=\frac{17}{99}$
$0.621621621\cdots=\frac{621}{999}=\frac{23}{37}$
第二部分的话，举个例子就容易明白了
$0.3171717\cdots=\frac{317-3}{990} =\frac{314}{990} =\frac{157}{495}$
$0.2718281828\cdots=\frac{271828-27}{999900} =\frac{271801}{999900}$

#include<stdio.h>
#include<string.h>
long int Tpow[10];
long int gcd(long int a, long int b)      //辗转相除法
{
                if(b==0)
                return a;
               else
                return gcd(b,a%b);
}
void init(void)       //预先计算了10的n次方，放入Tpow数组里
{
       int i;
      Tpow[0]=1;
     for(i=1;i<10;i++)
      {
                 Tpow[i]=Tpow[i-1]*10;
              // printf("%d\n",Tpow[i]);
       }
}
int main(void)
{
          char str[200];
          long int ans,a,b,c,temp,mina,minb,t,i;
         init();
           while(~scanf("%s",str))
         {
                   if(str[0]=='0'&&strlen(str)==1)
                               break;
                   ans=0;
                      t=0;
                   mina=-1;minb=-1;
                     for(i=2;str[i]!='.';i++)   // 把字符串转化成一个整数好计算    i从2开始，是因为忽略了前面的0.
                        {
                              ans=ans*10+str[i]-'0';
                                t++;
                      }
//   printf("ans=%d t=%d\n",ans,t);
                  for(i=t;i>0;i--)
                   {
                               c=ans;
                               b=Tpow[t-i]*(Tpow[i]-1); // 计算分母其中t-i代表上面的m    i代表上面的n

                              c=c/Tpow[i];     // 这时算出的c就是上面的β ，而上面的10^m*β+α就是ans
                              a=ans-c;          //计算分子
                               temp=gcd(a,b);
//    printf("a=%d b=%d temp=%d\n",a,b,temp);
                          if(b/temp<minb||mina==-1)
                              {
                                     mina=a/temp;
                                     minb=b/temp;
                              }
                     }

                  printf("%d/%d\n",mina,minb);
   }
}