浏览 2220 次
锁定老帖子 主题:HDU 1717 小数化分数2
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-06-06
最后修改:2011-11-19
http://acm.hdu.edu.cn/showproblem.php?pid=1717
题意:小数化分数 Sample Input 3 0.(4) 0.5 0.32(692307) //括号里是循环节 Sample Output 4/9 1/2 17/52 众所周知,有限小数是十进分数的另一种表现形式,因此,任何一个有限小数都可以直接写成十分之几、百分之几、千分之几……的数。那么无限小数能否化成分数? 首先我们要明确,无限小数可按照小数部分是否循环分成两类:无限循环小数和无限不循环小数。无限不循环小数不能化分数,这在中学已经得到详尽的解释 无限循环小数是可以化成分数的。那么,无限循环小数又是如何化分数的呢? 由于它的小数部分位数是无限的,显然不可能写成十分之几、百分之几、千分之几……的数。 其实,循环小数化分数难就难在无限的小数位数。 所以我就从这里入手,想办法“剪掉”无限循环小数的“大尾巴”。 策略就是用扩倍的方法 例子: 把0.4777……和0.325656……化成分数。 1:0.4777……×10=4.777……① 0.4777……×100=47.77……② 用②-①即得: 0.4777……×90=47-4 所以, 0.4777……=43/90 2:0.325656……×100=32.5656……① 0.325656……×10000=3256.56……② 用②-①即得: 0.325656……×9900=3256.5656……-32.5656…… 0.325656……×9900=3256-32 所以, 0.325656……=3224/9900 以上是网上复制的分析 下面我描述一下算法: 第一步:找出最少扩展k1位使其小数部分刚好成周期串,此时整数部分为xx 第二步:找出再次扩展k2位(k2>0)使其小数部分刚好成周期串,此时总共扩展了(k1+k2)位,整数部分为yy 第三步:分子==yy-xx, 分母==pow(10.0, k1+k2) - pow(10.0, k1) 第四步:利用最大公约数化简 其实说到这里,大家都可以YY了,只是字符串怎么提取出来并且转成整数求分子呢?貌似有点麻烦,我的代码用了函数atoi,挺好用的 仅供参考: #include <iostream> #include <fstream> #include <algorithm> #include <string> #include <set> #include <map> #include <queue> #include <utility> #include <stack> #include <list> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <ctype.h> using namespace std; int gcd (int a, int b) { int t; while (a) { t = a; a = b % a; b = t; } return b; } int main() { int a, b, i, len, t, xx, yy, p, q; char s[20], x[20], y[20]; scanf ("%d", &t); while (t--) { scanf ("%s", s); len = strlen (s); for (i = 0; i < len; i++) if (s[i] == '.') break; a = 0; for (i = i + 1; i < len; i++) { if (s[i] == '(') break; x[a] = y[a] = s[i]; a++; } x[a] = 0; xx = atoi (x); //把x转成整数 b = 0; for (i = i + 1; i < len; i++) { if (s[i] == ')') break; y[a+b] = s[i]; b++; } y[a+b] = 0; yy = atoi (y); if (b == 0) //说明这是有限非循环小数 { p = yy; q = pow (10.0, a); } else { p = yy - xx; q = pow (10.0, a+b) - pow (10.0, a); } int temp = gcd (p, q); p /= temp, q /= temp; printf ("%d/%d\n", p, q); } return 0; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |