如何计算循环数字？

Question

给定两个整数 a 和 b，我该如何计算 a / b 的循环小数？这可以用任何语言来表达，只需让它最容易理解。

- Claudiu

---

输出需要是十进制的吗？ - Brad Gilbert

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中是列表）代替字典，这将略微更快一些（不是在渐近意义下，而是在常数因子上）。

- ShreevatsaR

---

是的，这在Python中可能是最简单的方法，但最坏情况下的时间复杂度为O(b log b)，因此如果(log b)因子值得关注，可以使用数组代替--O(b)。 - ShreevatsaR

@ShreevatsaR，Python字典查找的时间复杂度是O(1)，而不是O(log b)。尽管列表索引的常数更好，但列表仍然会更快。另外，建议使用r in seen代替seen.has_key(r)。 - Mark Ransom

@MarkRansom：谢谢，我已经将这些更改合并进去了。 - ShreevatsaR

这是一个很棒的算法。 - Murali Mohan

Answer 2

您可以使用长除法来完成这个计算。每次只计算一位数字并相减得到余数，将余数乘以10得到下一步的分子。当新的分子与之前的某个分子相同时，您就知道从那一点开始会重复。您只需要保留之前分子的堆栈，并在每次迭代时搜索即可。

- Mark Ransom

---

马克，你如何进行搜索呢？这似乎是该算法中最困难的部分，但你却跳过了它。 - Deleted account

夜行者：在列表中扫描整数很困难吗？ - Deestan

Answer 3

我想这就是你要找的内容。

public static String divide(int a,int b,boolean decimalDone,boolean isMultiplied,String result){
           if(a<b){
                a=a*10;

                if(!decimalDone ) {result+=".";decimalDone=true;}
                else if(isMultiplied) result+="0";
                isMultiplied=true;
                divide(a,b,decimalDone,isMultiplied,result);

           }
           else{
               result+=a/b;
               a=a%b;
               isMultiplied=false;
               divide(a,b,decimalDone,isMultiplied,result);
           }

           return result;
    }

- Harit Vishwakarma

Answer 4

我不是专家，而且我认为这个解决方案可能不够高效，但至少它很容易实现：

#you want to get a/b
from fractions import Fraction:
print float(Fraction(a,b))

欢迎留言评论

- Pigna