1

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

例如，

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

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

4

3 回答 3

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

该地图记录了第一次看到每个股息状态的时间。在我们的示例中：

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

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

于 2013-08-16T05:22:17.587 回答
1

所以在这个算法中，这条线是关键。

while(!stateToIter.containsKey(state))

当它发现重复状态时，它正在破坏程序。现在找到重复状态意味着我们正在检测重复循环。让我们来解决这个问题，假设我们必须找出 6。我们做 1 / 6 的方式是

Problem :6 | 1 | Result = ?  
 Step 1: 
 Add 0. in the result and multiply 1 with 10
 6 | 10 | 0.

 Iteration 

 Step 2: 
 Do the division
 6 | 10 | 0.1
      6
    -----
      4 [Mod]

 Iteration = 0

 Step 3: 
 Multiply mod with 10 and carry on
 6 | 10 | 0.16
      6
    -----
      40 
      36
    -----
      04 [Mod]


 Iteration = 1

 Now we find a repeating mod so now matter how far we go we always get 4 as mod and our result will be 0.166666.. and so on so our repeating cycle will be 1 which is our iteration.
于 2013-06-07T05:36:18.803 回答
0

转换为十进制时，您逐渐将您拥有的值乘以 10，直到您拥有 0（不再写）或放弃（您已达到精度的极限）

一旦您再次使用相同的值，您将从该点重复相同的数字。该方法的作用是在您获得重复值时找到并计算自您第一次看到它以来已经过了多长时间（重复周期的长度）

顺便说一句，这个问题的另一个解决方案是避免使用地图。任何重复序列必须是 1/9 或 1/99 或 1/999 或 1/9999 等的倍数。这会找出除数需要多少个 9 才能成为一个因数。这是它重复的点。

public static void main(String... args) throws IOException {
    for (int i = 3; i < 100; i++) {
        System.out.println("i: " + i + " f: " + 1.0 / i + " repeat: " + getRepeatingCount(i));
    }
}

public static final BigInteger TEN_TO_19 = BigInteger.TEN.pow(19);

public static int getRepeatingCount(int divisor) {
    if (divisor <= 0) throw new IllegalArgumentException();
    while (divisor % 2 == 0) divisor /= 2;
    while (divisor % 5 == 0) divisor /= 5;
    int count = 1;
    if (divisor == 1) return 0;
    for (long l = 10; l > 0; l *= 10) {
        long nines = l - 1;
        if (nines % divisor == 0)
            return count;
        count++;
    }
    for(BigInteger bi = TEN_TO_19; ; bi = bi.multiply(BigInteger.TEN)) {
        BigInteger nines = bi.subtract(BigInteger.ONE);
        if (nines.mod(BigInteger.valueOf(divisor)).equals(BigInteger.ZERO))
            return count;
        count++;
    }
}
于 2013-06-07T06:40:20.087 回答