如何計算分區的無限值？

可能重複：
How to know the repeating decimal in a fraction?如何計算分區的無限值？

1/3是由3/10不同。 0.33333！= 0.3

所以1/3將是0.3（用上述三個數的線）

1/12 = 0.833333 = 0.083（與上述三個數的線）

1/13 = 0.076923076923 = 0. | 076923 |

這些線代表重複的部分。

我打算在一個班上有這個模型。我對這種情況有點失落。我只需要一些想法來確定重複的價值。謝謝。

來源

2012-07-02 Darf Zon

基本上，仿效長期分工。跟蹤每個長餘數。如果您遇到以前見過的剩餘部分，則自從您看到剩餘部分之後的序列就是重複值。 – cheeken

雖然它是重複的，但是在重複問題中沒有人提到週期查找算法。 – nhahtdh

在每個步驟中，除以floor，取其餘部分，乘以10，直到得到相同的數字。

例如，對於1/81：

1/81 = 0 with remainder 1  0 
10/81 = 0 with remainder 10  0.0 
100/81 = 1 with remainder 19 0.01 
190/81 = 2 with remainder 28 0.012 
280/81 = 3 with remainder 37 0.
... 
10/81 = 0 with remainder 10; saw this already. 
0.||

這裏是一個示例實現：

private static string GetRepeatingPart(int n, int d) { 
    var seen = new HashSet<int>(); 
    var result = new StringBuilder(); 

    n = (n % d) * 10; 

    while(true) { 
     int p = n/d; 
     n = (n % d) * 10; 

     if(seen.Contains(n)) { 
      return result.ToString(); 
     } 

     result.Append(p); 
     seen.Add(n); 
    } 
}

來源

2012-07-02 14:59:38 Ryan

這是一個正確的方法，與O（1）空間相比，O（λ+ mu）的空間複雜度和時間複雜度的隱藏常數更低，並且週期尋找算法的時間複雜度的隱藏常數更高。 – nhahtdh

Cycle detection algorithm就是答案。您可以使用Floyd's cycle detection algorithm或Brent's cycle detection algorithm。

插入這些算法的函數是產生商的下一個數字的函數。

來源

2012-07-02 14:59:47 nhahtdh

如何計算分區的無限值？

回答

相關問題