有理数的表示方式

Published: April 20, 2020 by Daltao

• Categories:
• problems 4

• Tags:

• 分数与有理数的互相转换

分数与有理数的互相转换

考虑分数$\frac{1}{3}$，其对应的有理数为$0.(3)$，括号内的数会被无限追加到数值尾部，并且不存在$0.(9)$，因为$0.99\ldots$无限趋近于$1$。

我们先考虑如何将分数转换为有理数。我们先将整数部分放到有理数的最前面，接下来我们只需要考虑真分数$\frac{a}{b}$，其中$a<b$。我们可以用小学学到的算术计算方式来不断做除法计算余数的方式得到有理数小数每一位。由于$b$是固定不变的，但是$a$在这个过程中可能会不断改变，即计算小数第$i$位前$a$的值为$a_i$。假设$j$是最小的整数，存在某个更小的数$i$，满足$a_i=a_j$，那么这意味着之后所有数都会开始重复，而整个周期就是$[i,j)$。重复这个过程，直到找到第一次重复为止。

上面的过程，按照生日悖论，其长度的期望应该是$O(\sqrt{b})$，时间复杂度也应该如此。

接下来考虑如何从有理数转分数。我们先考虑形如$0.(x)$的小数，这里记$k$为$x$的位数，那么其对应的分数为$\frac{x}{10^k-1}$。因为$\frac{x}{10^k-1}-0.(x)=\frac{x-x.(x)+0.(x)}{10^k-1}=0$。

现在我们知道怎处理循环节了，下面考虑形如$0.y(x)$的小数，我们可以将其乘上$10^d$，转换成$y.(x)$的形式，处理出分数后再除去$10^d$即可。同理对于$z.y(x)$的数，先处理出$0.y(x)$对应的分数在加上整数$z$即可。

这里也给出了处理出分数的算法，这个算法很显然是$O(n)$的，$n$是小数的长度。

提供一道题目: SRM761 AddPeriodic。