[USACO][2.4.5]Fractions to Decimals
Fractions to DecimalsWrite a program that will accept a fraction of the form N/D, where N isthe numerator and D is the denominator and print the decimalrepresentation. If the decimal representation has a repeating sequenceof digits, indicate the sequence by enclosing it in brackets. Forexample, 1/3 = .33333333...is denoted as 0.(3), and 41/333 =0.123123123...is denoted as 0.(123). Use xxx.0 to denote an integer.Typical conversions are:
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
INPUT FORMAT
A single line with two space separated integers, N and D, 1 <= N,D <= 100000.
SAMPLE INPUT (file fracdec.in)
45 56
OUTPUT FORMAT
The decimal expansion, as detailed above. If the expansion exceeds 76characters in length, print it on multiple lines with 76 characters perline.
SAMPLE OUTPUT (file fracdec.out)
0.803(571428) 分数化小数
译 by tim green
写一个程序，输入一个形如N/D的分数(N是分子，D是分母)，输出它的小数形式。
如果小数有循环节的话，把循环节放在一对圆括号中。例如，
1/3 = .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
INPUT FORMAT
单独的一行包括被空格分开的 N和D， 1 <= N,D <= 100000。
SAMPLE INPUT (file fracdec.in)
45 56
OUTPUT FORMAT
小数的表示方法上面说的很明白了，如果输出的长度超过76个字符，每行输出76个。
SAMPLE OUTPUT (file fracdec.out)
0.803(571428) （官方题解 译 by 逆铭）
记得长除法吗？我们知道只有当出现了曾经出现过的余数时，小数部分才会出现重复。重复的部分就是自从我们上次见到同样的余数之后计算出的部分。
我们先读入并打印整数部分。接下来，我们对剩下的真分数部分进行长除直到我们发现了重复的余数或余数变为0。如果我们发现了重复的余数，即出现了循环节，就分别恰当地打印重复的部分和不重复的部分。如果余数变为0，即已经除尽，就打印整个小数部分。如果小数位根本没有被生成，那么打印一个0就是正确答案了。
下面是另一个更加优美的解法，来自Anatoly Preygel。
计算循环开始前的小数位数，这样你甚至无需保存各个小数位和余数，程序的空间花费将大幅减小，而运行速度也能有所提高。我们知道2和5的幂是仅有的两种不导致循环的数，因此要找到循环前的各数位，我们只需分别找到分子分母中包含的因子2和5个数的差，再取两者的最大值。然后我们仅使用第一个余数，在计算时输出各个数位即可。
我们知道，a/b的每位运算所得的余数只可能是0..b-1，如果在某处出现一个余数之前曾经出现过（在小数位上），那么可以肯定此时从该处到上次用出现这个这个商之间存在循环节。
用m记录每种余数是否曾经出现过，ss记录余数第一次出现的位置，如果余数为0就是整除，否则就找到循环节，输出。
页:
[1]