Peter's codebook A blog full of codes

POJ 1930 Dead Fraction

Dead Fraction!

傳送門

POJ1930

題目概述

給定一個循環小數,求出原始分數形式是多少,輸出分母最小的那個。

限制

輸入的小數位數不超過 9 位。

輸出格式

分數形式,記得要約分。

解題想法

跟國中學的小數轉分數一樣,但是必須枚舉所有可能,也就是嘗試各種不同循環節長度,並找到分母最小的那一組。

程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
int se[]={0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

inline int str2b(string &s) {
    int res=0;
    for(string::iterator v=s.begin(); v!=s.end(); ++v) {
        res*=10;
        res+=(*v-'0');
    }
    return res;
}

pair<int,int> solv(string s, int m) {
    int a=str2b(s);
    a-=(a/se[m+1]);
    int n=s.length()-m;
    int b=0;
    for(int i=0; i!=m; ++i) {b*=10; b+=9;}
    b*=se[n+1];
    int g=__gcd(a,b);
    return make_pair(a/g,b/g);
}

int main(void) {
    ios::sync_with_stdio(false);
    //cin.tie(0);
    string str;
    int p, q, r;
    while(cin>>str&&str!="0") {
        int minval=-1;
        pair<int,int>ans(INT_MAX,INT_MAX);
        for(int i=str.length()-5; i>=1; --i) {
            int off=str.find('.',2);
            pair<int,int>temp=solv(str.substr(2,off-2),i);                      
            if(temp.second<ans.second) ans=temp;
        }
        cout<<ans.first<<"/"<<ans.second<<'\n';
    }
    return 0;
}
comments powered by Disqus