如何计算重复数字？

鉴于两个整数a和b,我怎么会去计算的循环小数a / b？这可以是任何语言; 无论你最简单的表达它.

您可以a / b使用您在学校学到的长分算法来计算十进制表示,正如Mark Ransom所说.要计算每个连续数字,将当前被除数(分子或余数)除以b,并找到下一个被除数作为余数乘以10("降低0").当余数与之前的余数相同时,意味着从那时开始的数字也将重复,因此您可以注意到这一事实并停止.

请注意这里优化的可能性:除以b时得到的余数在0到b-1范围内,因此只保留不同的非零余数,您不必搜索先前余数列表以查看如果有什么重复的话.因此,可以使算法在每个分步骤中采用恒定时间,并且O(b)空间足够.只需跟踪每个剩余首次出现的数字位置.

(这个论点,BTW,也是一个数学证明,即重复部分最多可以是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)