首页 > > 程序设计 > C/C++ >

poj1930解法（C++）

2018-06-17 23:37:05来源：未知阅读 ()

这道题题意如下：给出一个循环小数，将它化成分数并化简为最简分数，然后输出该分数。由于不知道这些循环小数从哪开始是循环节，于是就规定，输出当该小数所化成的分数分母最小时，该小数所化成的分数。（原题地址：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 }