8

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

4

4 回答 4

10

a / b正如 Mark Ransom 所说，您可以使用在学校学习的长除法算法计算十进制表示。要计算每个连续的数字，请将当前被除数（分子或余数）除以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)

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

于 2008-10-30T20:17:10.913 回答
7

你可以用长除法来做到这一点。一次计算一个数字并减去以获得余数，然后将其乘以 10 以获得下一步的分子。当这个新分子与以前的分子之一匹配时，您知道您将从该点开始重复。您只需要保留一堆以前的分子并在每次迭代时搜索它。

于 2008-10-30T05:54:42.370 回答
1

我想这就是你要找的..

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;
    }
于 2013-03-05T18:00:21.067 回答
0

我不是专家，我认为这个解决方案可能效率不高，但至少它很容易做到：

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

评论很受欢迎

于 2015-06-23T12:11:48.433 回答