首页 > 代码库 > HDU 2522 & AOJ 441 & AOJ 364 关于小数和分数的转换
HDU 2522 & AOJ 441 & AOJ 364 关于小数和分数的转换
总结一下小数和分数之间精确转换的方法。
首先是分数转换为小数，这个比较简单，先看题 http://acm.hdu.edu.cn/showproblem.php?pid=2522
输入一个n，求1/n的精确表示，如果有循环节只输出最小的一个。
手动模拟一下出发，会发现每次都是上一次除法剩下来的余数*10然后继续下一次计算，什么时候会出现循环呢，显然是余数出现重复的时候。
余数判断重复可以搞一个hash或者set，这里n不是特别大，直接用数组就可以了。
另外写的时候注意一下处理整除的情况。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1e5 + 10;bool vis[maxn];int main() { int n, T; scanf("%d", &T); while (T--) { scanf("%d", &n); memset(vis, false, sizeof(vis)); int num = abs(n), nowmod = 1, nowval; vis[1] = true; vis[0] = true; if (num == 1) { puts("1"); continue; } if (n < 0) putchar(‘-‘); printf("0."); while (1) { nowval = (nowmod * 10) / num; nowmod = (nowmod * 10) % num; printf("%d", nowval); if (vis[nowmod]) break; vis[nowmod] = true; } putchar(‘\n‘); } return 0;}另外看一下 http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=441
输入两个数A,B(0<A<=B<=1000)，精确输出A/B,并且输出最小循环节长度。
处理方法和上面那个一样，使劲除就好了。 长度的处理就是把原来的vis数组给换成是记录上一次这个数出现的位置即可。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1000 + 10;int pre_pos[maxn];int main() { int A, B; while (scanf("%d%d", &A, &B), A) { memset(pre_pos, -1, sizeof(pre_pos)); A %= B; if (A == 0) { puts(".\nThis expansion terminates."); continue; } int nowmod = A, nowval, len, nowpos = 0; pre_pos[A] = 0; bool terminal = false; putchar(‘.‘); while (1) { nowpos++; nowval = (nowmod * 10) / B; nowmod = (nowmod * 10) % B; if (nowval == 0 && nowmod == 0) { terminal = true; break; } printf("%d", nowval); if (pre_pos[nowmod] != -1) { len = nowpos - pre_pos[nowmod]; break; } pre_pos[nowmod] = nowpos; } putchar(‘\n‘); if (terminal) puts("This expansion terminates."); else printf("The last %d digits repeat forever.\n", len); } return 0;}
然后是给你小数，指定循环节，让你求分数。 http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=364
这类问题比上面那种要麻烦，需要推一下公式。
给你一个小数 N = 0.A(B)，括号内的为循环节，假设A的长度为LenA，B的长度为LenB，有
N * 10^LenA = A.(B) ----> N * 10^LenA - A = 0.(B)
设Y = 0.(B) 有
Y * 10^LenB = B.(B)
Y * 10^LenB - B = 0.(B) = Y
Y = B / (10^LenB - 1) = N * 10^LenA - A
N = (B + A * (10^LenB - 1)) / ( 10^LenA * (10^LenB - 1))
分别计算出分子和分母的值，然后求一下gcd，约分一下就好了。
#include <cstdio>#include <cstring>#include <iostream> using namespace std; typedef long long LL; LL gcd(LL a,LL b) { return b == 0 ? a : gcd(b,a % b);} LL pow10(LL a) { LL ret = 1; while(a--) ret *= 10; return ret;} void display(int a,int b) { int n = 0,m = 0,ta = a,tb = b; while(ta) { n++; ta /= 10; } while(tb) { m++; tb /= 10; } LL denominator,numerator,div; denominator = pow10(n) * (pow10(m) - 1); numerator = a * (pow10(m) - 1) + b; div = gcd(denominator,numerator); cout << numerator / div << "/" << denominator / div << endl;} int main() { int T; cin >>T; while(T--) { int a,b; cin >> a >> b; display(a,b); } return 0;}
HDU 2522 & AOJ 441 & AOJ 364 关于小数和分数的转换