首页 > 代码库 > POJ 1930 Dead Fraction
POJ 1930 Dead Fraction
http://poj.org/problem?id=1930
小学奥数忘了吗
求无限循环小数的分数方法
//计算循环小数的公式
/*
用9和0做分母,首先有几个循环节就几个9,接着有几个没加入循环的数就加几个0,
再用小数点后面的数减 没加入循环的数,比如0.43,3的循环,有一位数没加入循环,
就在9后面加一个0做分母,再用43减4做分子,得 90分之39,0.145,5的循环就用9后
面加2个0做分母,再用145减14做分子,得900分之131,0.549,49的循环,就 用99后
面加1个0做分母,用549减5做分子,最后得990分之545,以此类推,能约分的要化简。
*/
但是因为题目并没有说 循环部分是多少
所以直接枚举不重复的部分即可 "by simplest, he means the the one with smallest denominator" 找使得最简的分母即可
denominator --分母
numerator --分子
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <queue> 5 #include <algorithm> 6 #include <math.h> 7 #include <string> 8 #include <fstream> 9 #define READ() freopen("in.txt", "r", stdin); 10 #define MAXV 2007 11 #define MAXE 20007 12 #define INF 9999999999 13 using namespace std; 14 15 typedef long long LL; 16 17 LL pow10(int n)//10^n 18 { 19 LL res = 1; 20 for (int i = 0; i < n; i++) 21 { 22 res *= 10; 23 } 24 return res; 25 } 26 LL gcd(LL x, LL y) 27 { 28 if (y == 0) return x; 29 else return gcd(y, x%y); 30 } 31 //vjudge的好代码!!! 32 int main() 33 { 34 READ() 35 char str[128]; 36 LL len, num, all, i, a, b, g; 37 while (cin >> str && strcmp(str,"0")) 38 { 39 LL min_a = INF, min_b = INF; 40 for (i = 2, all = 0, len = 0; str[i] != ‘.‘; i++ )//读取数字 41 { 42 all = all * 10 + str[i] - ‘0‘; 43 len++; 44 } 45 for (LL j = 1; j <= len; j++) 46 { 47 num = all / pow10(j);//不循环的数字 48 a = all - num;//分子 49 b = pow10(len) - pow10(len - j); 50 g = gcd(a, b); 51 if (b/g < min_b) 52 { 53 min_b = b/g; 54 min_a = a/g; 55 } 56 } 57 cout << min_a << "/" << min_b << endl; 58 } 59 return 0; 60 }
POJ 1930 Dead Fraction
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。