首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。