如何计算周期性数字？

给定两个整数a和b，我怎么会去计算a/b重复小数？这可以用任何语言;不管它是最简单的你来表达它。如何计算周期性数字？

来源

2008-10-30 Claudiu

输出是否需要小数？ – 2008-10-30 15:10:04

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

来源

2008-10-30 05:54:42

马克，你如何做搜索？这似乎是这个算法中最困难的部分，但你跳过了它。 – 2008-10-30 12:17:06

Night Rider：扫描一个整数列表很困难？ – Deestan 2008-10-30 12:24:03

你可以使用你在学校学到的长除法算法计算a/b十进制表示，马克赎金说。要计算每个连续的数字，将当前的分红（分子或余数）除以b，并找到下一个分红，其余的乘以10（“减少0”）。当余数与以前的余数相同时，这意味着从此以后的数字也会重复，所以您可以注意到这一事实并停止。

请注意这里优化的可能性：除以b得到的余数范围为0到b-1，因此，如果只保留不同的非零余数，则不必搜索以前的剩余部分，看看是否有重复。因此，可以使算法每分步骤采取恒定的时间，并且空间足够。只需跟踪每个剩余首先发生在什么位数。（这个参数，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)

你也可以用大小b，而不是一本字典的数组（Python中的列表），这将是稍快（不是渐进性的方面，而是在不断的因素）。

来源

2008-10-30 20:17:10 ShreevatsaR

我认为这是你在找什么..

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-05 18:00:21

我不是专家，我觉得这种解决方案可能是效率不高，但至少这是很容易做到：

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

评论已被广泛接受

来源

2015-06-23 12:11:48 Pigna

如何计算周期性数字？

回答

相关问题