P1530 分数化小数 Fractions to Decimals
- 103通过
- 348提交
- 题目提供者该用户不存在
- 标签USACO
- 难度普及/提高-
提交 讨论 题解
最新讨论
- 暂时没有讨论
题目描述
写一个程序，输入一个形如N/D的分数(N是分子，D是分母)，输出它的小数形式。 如果小数有循环节的话，把循环节放在一对圆括号中。
例如, 1/3 =0.33333333写成0.(3), 41/333 = 0.123123123...写成0.(123), 用xxx.0 等表示整数。 典型的转化例子：
1/3 = 0.(3)
22/5 = 4.4
1/7 = 0.(142857)
2/2 = 1.0
3/8 = 0.375
45/56 = 0.803(571428)
PROGRAM NAME fracdec输入输出格式
输入格式：
单独的一行包括被空格分开的N和D(1 <= N,D <= 100000)。
输出格式：
按照上面规则计算出的小数表达式.如果结果长度大于76,每行输出76个字符.
输入输出样例
输入样例#1：
45 56
输出样例#1：
0.803(571428)
说明
翻译来自NOCOW
USACO 2.4
分析：看着和数学有关，其实是一道大模拟......细节非常多:
1.因为要76行一输出，所以要先用一个变量记录长度，小数点也要加上去.
2.如果能够除尽，直接输出答案即可.
3.对于整数部分的长度，不断除以10，直到等于0，每次除的时候累加长度.
4.如果除以10恰好等于0，那么长度+1.
然后就是小数部分的处理了，难点是循环节的处理，如果一个余数之前恰好出现过，而当前的除数正好是之前余数对应的除数，那么就出现循环节，这里用两个数组记录，一个记录上一个相同余数位置，一个记录除数.
最后输出的时候判断累加的长度是否为76，是则换行即可.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
int n,d,a[],check[],tot1 = ,tot,ans[],cur[],h[],integer[],remainder[],flag,l,r; int main()
{
scanf("%d%d",&n,&d);
if (n % d == )
{
printf("%d.0\n",n/d);
return ;
}
printf("%d.",n/d);
int temp = n / d;
while (temp)
{
tot1++;
temp /= ;
}
if (n / d == )
tot1++;
remainder[] = n % d;
while ()
{
tot++;
integer[tot] = remainder[tot - ] * / d;
remainder[tot] = remainder[tot - ] * % d;
if (remainder[tot] == )
break;
if (cur[remainder[tot]] > && h[cur[remainder[tot]]] == integer[tot])
{
l = cur[remainder[tot]];
r = tot - ;
break;
}
cur[remainder[tot]] = tot;
h[cur[remainder[tot]]] = integer[tot];
}
for (int i = ; i <= tot; i++)
{
if (i == l)
{
printf("(");
tot1++;
}
printf("%d",integer[i]);
tot1++;
if (i == r)
{
printf(")");
break;
}
if (tot1 % == )
printf("\n");
}
printf("\n"); return ;
}