poj1930解法(C++)

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

新老客户大回馈,云服务器低至5折

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

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:SDUT 3343 数据结构实验之二叉树四:还原二叉树

下一篇:[C++]运用表达式树将后缀表达式转换成中缀表达式