如何計算週期性數字？

Question

給定兩個整數a和b，我怎麼會去計算a/b重複小數？這可以用任何語言;不管它是最簡單的你來表達它。

Answer 1

你可以用長除法做到這一點。一次計算一個數字並減去一個餘數，乘以10得到下一步的分子。當這個新的分子與前面的分子之一相匹配時，你就知道你將會從這一點開始重複。你只需要保留一堆以前的分子，並在每次迭代中搜索它。

Answer 2

你可以使用你在學校學到的長除法算法計算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中的列表），這將是稍快（不是漸進性的方面，而是在不斷的因素）。

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; 
    } 

Answer 4

我不是專家，我覺得這種解決方案可能是效率不高，但至少這是很容易做到：

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

評論已被廣泛接受