HDU 1717 小数化分数2
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;}