java - 有人可以解释以下用于查找重复循环或重复小数周期长度的方法吗？

Question

在阅读维基百科页面上关于重复小数的信息后，我找到了一种方法来计算小数重复部分的位数。

例如，

1/3 = 0.333333333333333333333333333333...所以结果是 1 位数。

1/7 = 0.142857142857142857142857142857...所以结果是 6 位数字。

但是，我的方法(在 Java 中)对 1/6 不起作用，应该产生 1，因为:

1/6 = 0.1666... 所以结果是 1 位数字，尽管小数部分不重复。

我找到了一个可行的解决方案(归功于 Nayuki Minase)。

private static int getCycleLength(int n)
{
    Map<Integer,Integer> stateToIter = new HashMap<Integer,Integer>();
    int state = 1;
    int iter = 0;
    while (!stateToIter.containsKey(state))
    {
        stateToIter.put(state, iter);
        state = state * 10 % n;
        iter++;
    }
    System.out.println(iter + " - " + stateToIter.get(state));
    return iter - stateToIter.get(state);
}

有人可以向我解释一下这个算法是如何工作的吗？谢谢。

Answer 1

这里是奈雪。代码来自Project Euler p026.java .让我解释一下这是怎么回事。

主要思想是我们模拟长除法并检测余数何时开始重复。让我们用计算 1/7 的例子来说明。

    0.142857...
  -------------
7 | 1.000000000
      7
    ---
      30
      28
      --
       20
       14
       --
        60
        56
        --
         40
         35
         --
          50
          49
          --
           10
           ...

---

要执行长除法，我们执行以下步骤:

1. 设置除数 = 7。设置被除数 = 1。(我们正在计算 1/7。)

     ----
   7 | 1
   

2. 除数多少次进入被除数？让它成为k。将此数字附加到商。

       0
     ---
   7 | 1
   

3. 从被除数中减去 k × 除数。这是剩余部分。

       0
     ---
   7 | 1
      -0
      --
       1
   

4. 在右侧移入一个新数字。在我们的例子中，它是零的无限小数。这相当于将股息乘以 10。

       0
     ---
   7 | 1.0
      -0
      --
       10
   

5. 转到第 2 步并无限重复。

       0.1
     -----
   7 | 1.0
      -0
      --
       10
       -7
       --
        3
        ...
   

我们在长除法的每次迭代中更新股息。如果股息采用之前的值，那么它将生成相同的小数位。

现在，在代码中:

// Step 1
int divisor = 7;
int dividend = 1;

while (true) {
  // Step 2
  int k = dividend / divisor;  // Floor

  // Step 3
  dividend -= k * divisor;

  // Step 4
  dividend *= 10;
}

通过一些数学运算，第 2 步和第 3 步可以合并为 dividend %= divisor;。此外，这可以与步骤 4 结合得到 dividend = dividend % divisor * 10;。

---

该 map 记录了第一次看到每个红利状态的时间。在我们的示例中:

• 余数 1 在第 0 次迭代中出现。
• 在第 1 次迭代中看到了剩余的 3 个。
• 余数 2 在迭代 2 中看到。
• 其余 6 个在第 3 次迭代中出现。
• 在第 4 次迭代中看到了剩余的 4 个。
• 在第 5 次迭代中看到了剩余的 5 个。
• 余数 1 在第 6 次迭代中出现。

第6次迭代的状态与第0次迭代的状态相同，而且这是最短的循环。因此，循环长度为6 − 0 = 6。