板子:

 int gcd(int a, int b) { return b >  ? gcd(b, a % b) : a; }

POJ1930

题意:给你一个无限循环小数,给到小数点后 9 位,要求这个数的分数形式。

解法:

要想解决这道题,首先应该了解如何将循环小数化为分数:

一,纯循环小数化分数:循环节的数字除以循环节的位数个 9 组成的整数。例如: 
$0.3333……=3/9=1/3$;
$0.285714285714……=285714/999999=2/7$. 
二,混循环小数:(例如:$0.24333333……$)不循环部分和循环节构成的的数减去不循环部分的差,再除以循环节位数个 9 添上不循环部分的位数个  0。例如: 
$0.24333333…………=(243-24)/900=73/300 $
$0.9545454…………=(954-9)/990=945/990=21/22$

这便是循环小数化成分数的方法,知道这个后,解决这道题也好办了。

代码如下:

 #pragma GCC optimize(3)
#include <time.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
const double EPS = 1e-;
const int INF = ;
const long long LLINF = ;
const double PI = acos(-1.0); inline int READ() {
char ch;
while ((ch = getchar()) < || < ch)
;
int ans = ch - ;
while ( <= (ch = getchar()) && ch <= )
ans = (ans << ) + (ans << ) + ch - ;
return ans;
} #define REP(i, a, b) for (int i = (a); i <= (b); i++)
#define PER(i, a, b) for (int i = (a); i >= (b); i--)
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); i++)
#define MP(x, y) make_pair(x, y)
#define PB(x) push_back(x)
#define SET(a) memset(a, -1, sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(x) begin(x), end(x)
#define LL long long
#define Lson (index * 2)
#define Rson (index * 2 + 1)
#define pii pair<int, int>
#define pll pair<LL, LL>
#define MOD ((int)1000000007)
#define MAXN 20 + 5
///**********************************START*********************************///
string ss, sn; char s[MAXN], ns[MAXN];
int nex[MAXN]; void get_next(char* p, int next[]) {
int pLen = strlen(p) + ; //要求循环节长度时这里才+1
next[] = -;
int k = -;
int j = ;
while (j < pLen - ) {
if (k == - || p[j] == p[k]) {
++j;
++k;
if (p[j] != p[k])
next[j] = k;
else
next[j] = next[k];
} else {
k = next[k];
}
}
} int gcd(int a, int b) { return b > ? gcd(b, a % b) : a; } void cal_cal(int len) {
int up = , down = ;
for (int i = len - ; i >= ; i--)
up += int(s[i] - '') * pow(, len - i - );
for (int i = ; i < len; i++) down += * pow(, i);
int g = gcd(up, down);
printf("%d/%d\n", up / g, down / g);
return;
} void cal_cal2(int st, int len) {
char tmp[];
int up = , down = ;
int a, b; for (int i = ; i < st; i++) tmp[i] = s[i];
tmp[st] = '\0';
a = atoi(tmp);
for (int i = st; i < st + len; i++) tmp[i - st] = s[i];
tmp[len] = '\0';
b = atoi(tmp); up = a * pow(, len) + b - a;
int pos = ;
for (int i = ; i < len; i++) tmp[pos++] = '';
for (int i = ; i < st; i++) tmp[pos++] = '';
down = atoi(tmp);
int g = gcd(up, down);
printf("%d/%d\n", up / g, down / g);
return;
} int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif // !ONLINE_JUDGE
while (cin >> ss) {
if (ss.size() == ) break;
int pos = ;
for (int i = ; ss[i] != '.'; i++) s[pos++] = ss[i];
s[pos] = '\0';
int flag = ; // 1为全循环,2为混合循环
get_next(s, nex);
int len = pos - nex[pos];
if (len != pos) {
cal_cal(len);
} else {
int st;
for (st = ; st < pos; st++) {
int nlen = ;
for (int i = st; i < pos; i++) {
ns[nlen++] = s[i];
}
CLR(nex);
get_next(ns, nex);
if (nlen - nex[nlen] != nlen) {
cal_cal2(st, nlen);
break;
} else
continue;
}
}
}
return ;
}

最新文章

  1. mysql数据引擎的概念介绍
  2. Android应用更换package name以及ui refactoring error问题的有效解决
  3. 数据仓库专题(23):总线矩阵的另类应用-Drill Down into a More Detailed Bus Matrix
  4. Unity CombineChildren和MeshCombineUtility
  5. 在 MVC 控制器中使用 构造函数时行依赖注入 (IoC)
  6. jQuery cookie插件保存用户登陆信息
  7. Comet、SSE、Web Socket
  8. angular下H5上传图片(可多张上传)
  9. springmvc-时间类型转换器
  10. POJ 2404 Jogging Trails
  11. HTML,login文本框&#183;
  12. 解构声明(Destructuring Declarations)
  13. 构建Spring Cloud微服务分布式云架构
  14. Spring IOC注入接口多实现解决
  15. django 问题总结
  16. HTML-XML数据解析
  17. UML序列图的理解:
  18. 大数据【四】MapReduce(单词计数;二次排序;计数器;join;分布式缓存)
  19. 11.SolrCloud集群环境搭建
  20. 转 Spring Boot之No session repository could be auto-configured, check your configuration问题解决

热门文章

  1. python(从放弃到从头开始)
  2. 如何获取 C# 类中发生数据变化的属性信息
  3. 重磅!K8S 1.18版本将内置支持SideCar容器。
  4. Redis系列(三):Redis的持久化机制(RDB、AOF)
  5. 关于java String类的getBytes(String charsetName)和String(byte[] bytes, String charsetName)
  6. WTL改变对话框大小
  7. CCF_201612-4_交通规划
  8. DOCKER 学习笔记9 Kubernetes (K8s) 生产级容器编排 上
  9. 2、HotSpot虚拟机对象探秘
  10. 安装Mysql时提示尚未安装Python 解决方案