algorithm - 如何计算循环数字？

Question

给定两个整数 a 和 b，我将如何计算 a/b 的重复小数？这可以是任何语言；无论您用什么最容易表达它。

Answer 1

正如 Mark Ransom 所说，您可以使用在学校学到的长除法算法计算 a/b 的十进制表示。要计算每个连续的数字，请将当前被除数(分子或余数)除以 b，然后找到下一个被除数，即余数乘以 10(“减去 0”)。当一个余数与前一个余数相同时，表示此后的数字也将重复，所以你可以注意到这一点并停止。

请注意此处的优化潜力:除以 b 时得到的余数在 0 到 b-1 的范围内，因此由于您只保留不同的非零余数，因此您不必搜索之前的列表余数以查看是否重复。因此可以使该算法在每个分割步骤中花费恒定的时间，O(b) 空间就足够了。只需跟踪每个余数首先出现在哪个数字位置。

(顺便说一句，这个论点也是一个数学证明，即重复部分最多可以有 b-1 位数字:例如 1/7=0.(142857) 有一个 6 位数字的重复部分，而 1/17 = 0.(0588235294117647) 有 16 位数字的重复部分。长度总是除以 b-1，实际上。)

这是执行此操作的 Python 代码，它在 O(b) 时间内运行。

def divide(a, b):
  '''Returns the decimal representation of the fraction a / b in three parts:
  integer part, non-recurring fractional part, and recurring part.'''
  assert b > 0
  integer = a // b
  remainder = a % b
  seen = {remainder: 0}  # Holds position where each remainder was first seen.
  digits = []
  while(True):  # Loop executed at most b times (as remainders must be distinct)
    remainder *= 10
    digits.append(remainder // b)
    remainder = remainder % b
    if remainder in seen:  # Digits have begun to recur.
      where = seen[remainder]
      return (integer, digits[:where], digits[where:])
    else:
      seen[remainder] = len(digits)

# Some examples.
for a, b in [(5,4), (1,6), (17,7), (22,11), (100,17)]:
  (i, f, r) = divide(a, b)
  print "%d/%d = %d.%s(%s)" % (a, b, i, ''.join(map(str, f)),''.join(map(str,r)))
# Output:
# 5/4 = 1.25(0)
# 1/6 = 0.1(6)
# 17/7 = 2.(428571)
# 22/11 = 2.(0)
# 100/17 = 5.(8823529411764705)

您还可以使用大小为 b 的数组(Python 中的列表)来代替字典，这样会稍微快一些(不是在渐近方面，而是在常数因子方面)。