在阅读维基百科页面上关于重复小数的信息后,我找到了一种方法来计算小数重复部分的位数。
例如,
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);
}
有人可以向我解释一下这个算法是如何工作的吗?谢谢。
最佳答案
这里是奈雪。代码来自Project Euler p026.java .让我解释一下这是怎么回事。
主要思想是我们模拟长除法并检测余数何时开始重复。让我们用计算 1/7 的例子来说明。
0.142857...
-------------
7 | 1.000000000
7
---
30
28
--
20
14
--
60
56
--
40
35
--
50
49
--
10
...
要执行长除法,我们执行以下步骤:
设置除数 = 7。设置被除数 = 1。(我们正在计算 1/7。)
---- 7 | 1
除数多少次进入被除数?让它成为k。将此数字附加到商。
0 --- 7 | 1
从被除数中减去 k × 除数。这是剩余部分。
0 --- 7 | 1 -0 -- 1
在右侧移入一个新数字。在我们的例子中,它是零的无限小数。这相当于将股息乘以 10。
0 --- 7 | 1.0 -0 -- 10
转到第 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。
关于java - 有人可以解释以下用于查找重复循环或重复小数周期长度的方法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16976441/