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了,只是字符串怎么提取出来并且转成整数求分子呢?貌似有点麻烦,我的代码用了函数itoa,挺好用的
仅供参考:
#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;
}
分享到:
相关推荐
各种小数化分数的算法,acm的同学都喜欢看,仅供参考!
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
自己做的HDU ACM已经AC的题目
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类