版权声明:此文章转载自_infocool
原文链接:http://www.infocool.net/kb/CPlus/201610/207102.html
如需转载请联系听云College团队成员小尹 邮箱:yinhy#tingyun.com
这道题题意如下:给出一个循环小数,将它化成分数并化简为最简分数,然后输出该分数。由于不知道这些循环小数从哪开始是循环节,于是就规定,输出当该小数所化成的分数分母最小时,该小数所化成的分数。(原题地址:http://poj.org/problem?id=1930)
要想解决这道题,首先应该了解如何将循环小数化为分数:
一,纯循环小数化分数:循环节的数字除以循环节的位数个9组成的整数。例如:
0.3333……=3/9=1/3;
0.285714285714……=285714/999999=2/7.
二,混循环小数:(例如:0.24333333……)不循环部分和循环节构成的的数减去不循环部分的差,再除以循环节位数个9添上不循环部分的位数个0。例如:
0.24333333…………=(243-24)/900=73/300
0.9545454…………=(954-9)/990=945/990=21/22
这便是循环小数化成分数的方法,知道这个后,解决这道题也好办了。
代码如下:
1 /* 2 Name:poj1930 3 Copyright: 4 Author: yuyang 5 Date: 29/10/16 11:58 6 Description: 7 */ 8 9 #include<cstdio> 10 #include<stdlib.h> 11 #include<algorithm> 12 #include<cstring> 13 #include<string> 14 #include<iostream> 15 using namespace std; 16 string str; 17 18 //判断两数的最大公因数 19 int gcd(int x,int y){ 20 int ret; 21 if(y==0){ 22 ret=x; 23 }else if(x<y){ 24 ret=gcd(y,x); 25 }else{ 26 ret=gcd(y,x%y);
27 } 28 return ret; 29 } 30 31 //将所得到的分数化简,得到当分数为最简分数时分子和分母的值 32 pair<int,int> jh(int x,int y){ 33 int li=gcd(x,y); 34 if(li==1){ 35 return make_pair(x,y); 36 }else{ 37 return jh(x/li,y/li); 38 } 39 } 40 41 int main(){ 42 while(cin>>str&&str.size()!=1){ 43 int fmmin=99999999; 44 int fzmin; 45 int yjr=0;int start,end,fxhj; 46 //判断小数部分是从第几位开始,从第几位结束(开头的0算一位,小数点算一位),start为起始位数,end为结束位数 47 for(int i=0;i<str.size();i++){ 48 if(yjr==0&&str[i]=='.'){ 49 start=i+1; 50 yjr=1; 51 } 52 if(yjr==1&&str[i+1]=='.'){ 53 end=i; 54 }
55 } 56 end-=2; 57 for(int i=start;i<=end;i++){//求出当从第i位开始为循环节时,该小数对应的分数值,并判断在此情况下分母是否取最小值 58 int fz=0,fm=0;//fz为分子值,fm为分母值 59 /* 60 一,纯循环小数化分数:循环节的数字除以循环节的位数个9组成的整数。例如: 61 0.3333……=3/9=1/3; 62 0.285714285714……=285714/999999=2/7. 63 二,混循环小数:(例如:0.24333333……)不循环部分和循环节构成的的数减去不循环部分的差,再除以循环节位数个9添上不循环部分的位数个0。例如: 64 0.24333333…………=(243-24)/900=73/300 65 0.9545454…………=(954-9)/990=945/990=21/22 66 */ 67 for(int j=i;j<=end;j++){ 68 fz=fz*10+(str[j]-'0'); 69 fm=fm*10+9; 70 } 71 int plus=0; 72 if(i>start){ 73 for(int j=start;j<i;j++){ 74 plus=plus*10+(str[j]-'0'); 75 fm=fm*10; 76 } 77 int qian=plus; 78 for(int j=i;j<=end;j++){ 79 qian=qian*10; 80 } 81 qian=fz+qian; 82 fz=qian-plus;
83 } 84 //判断分母是否取最小值 85 if(jh(fz,fm).second<fmmin){ 86 fmmin=jh(fz,fm).second; 87 fzmin=jh(fz,fm).first; 88 } 89 } 90 printf("%d/%d\n",fzmin,fmmin); 91 } 92 return 0; 93 }
我将这个代码提交到poj后通过了: