首页 > 代码库 > Fraction to Recurring Decimal 166

Fraction to Recurring Decimal 166

题目描述:

给出一个小数的分子和分母,将这个小数转化成string类型表示的小数形式

当小数出现循环时,用小括号将循环节括起来


 

题目分析:

这个题目重点是找到循环节

对于存在循环节的情况,找到循环节是重点,我们

  当什么情况下循环节完整的出现出现了呢?

  我们不断的做除法,每次都会有一个余数,如果当前的余数在之前出现过,那么循环节就完整的出现了


代码:

 1 typedef  int64_t   LL; 2 //typedef __int64 LL; 3  4 string itos(LL n)    //将整形数据转化为string类型 5 { 6     if(n==0)return "0"; 7     string ret=""; 8     while(n) 9     {10         unsigned m=n%10;11         ret=(char)(m+0)+ret;12         n=n/10;13     }14     return ret;15 }16 17 string fractionToDecimal(LL numerator, LL denominator) {18         vector<LL> quo;    //19         vector<LL> rem;    //余数20 21         string ret="";22         if((numerator<0 && denominator>0) || (numerator>0 && denominator<0))ret+=-;    //确定最终结果的正负号23 24         //确定符号之后可以将两个数字都转化为整数运算,不过,对于负数 (1<<31)转化为整数会溢出,这里采用了64位整数存储25         LL n;26         LL m;27         n=numerator<0?-numerator:numerator;28         m=denominator<0?-denominator:denominator;29 30         int s=-1;    //标志循环节开始位置31         32 33         LL intPart=n/m;34         n=n%m;35         ret+=itos(intPart);    //整数部分36         if(n==0)return ret;37 38         int tag=1;        //tag表示是否找到了循环节,当tag==1时表示没有找到,当tag==0时表示已经找到循环节39         while(tag && n)    //当n==0时表示除尽40         {41             rem.push_back(n);42             n=n*10;43 44             LL quotient=n/m;45             LL remainder=n%m;46             47             for(int i=0;i<rem.size();i++)48             {49                 if(remainder==rem[i])50                 {51                     s=i;    //循环节开始位置52                     tag=0;53                     break;54                 }55             }56             quo.push_back(quotient);57             n=remainder;58         }59 60         ret+=.;            //小数点61 62         if(tag)        //除尽时添加小数63         {64             for(int i=0;i<quo.size();i++)65                 ret=ret+(char)(quo[i]+0);66         }67         else        //找到循环节时添加小数68         {69             for(int i=0;i<quo.size();i++)70             {71                 if(i==s)ret=ret+(;72                 ret+=(char)(quo[i]+0);73             }74             ret+=);75         }76 77         return ret;78 }

 

Fraction to Recurring Decimal 166