Dead Fraction!
給定一個循環小數,求出原始分數形式是多少,輸出分母最小的那個。
分數形式,記得要約分。
跟國中學的小數轉分數一樣,但是必須枚舉所有可能,也就是嘗試各種不同循環節長度,並找到分母最小的那一組。
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;
}