算法检测循环小数？ [英] Algorithm for detecting repeating decimals?
问题描述
是否有一个算法，找出以下的事情？
Is there an algorithm for figuring out the following things?
- 如果一个部门的结果是重复十进制（二进制）。
- 如果它重复，在什么数字（重psented为2的幂$ P $）不重复启动？
- 在什么数字重复？
一些例子：
1/2 = 1/10 = 0.1 // 1 = false, 2 = N/A, 3 = N/A, 4 = N/A
1/3 = 1/11 = 0.010101... // 1 = true, 2 = -2, 3 = 10
2/3 = 10/11 = 0.101010... // 1 = true, 2 = -1, 3 = 10
4/3 = 100/11 = 1.010101... // 1 = true, 2 = 0, 3 = 10
1/5 = 1/101 = 0.001100110011... // 1 = true, 2 = -3, 3 = 1100
有没有办法做到这一点？效率是一个大问题。该算法的描述是pferred超过code $ P $，但我会采取什么样的答案，我可以得到的。
Is there a way to do this? Efficiency is a big concern. A description of the algorithm would be preferred over code, but I'll take what answer I can get.
另外值得一提的是，该基地是不是一个大问题;我可以转换算法在二进制（或者，如果它在，说基地256使用字符 S代表放心，我可以只使用）。我这样说是因为，如果你解释可能更容易为你的基部10解释：）
It's also worth noting that the base isn't a big deal; I can convert the algorithm over to binary (or if it's in, say base 256 to use chars for ease, I could just use that). I say this because if you're explaining it might be easier for you to explain in base 10 :).
推荐答案
要找到重复的图案，只是记录你前进的线路上使用的值：
To find the repeating pattern, just keep track of the values you use along the line:
1/5 = 1/101:
1 < 101 => 0
(decimal separator here)
10 < 101 => 0
100 < 101 => 0
1000 >= 101 => 1
1000 - 101 = 11
110 >= 101 => 1
110 - 101 = 1
10 -> match
当你到达，你必须在第二位相同的值，这个过程只会从该点一遍又一遍产生相同的位模式重复。你有图案0011从第二位（第一位小数分隔符后）重复。
As you reach the same value as you had at the second bit, the process will just repeat from that point producing the same bit pattern over and over. You have the pattern "0011" repeating from the second bit (first after decimal separator).
如果您希望的模式开始一个1，你可以旋转它，直到它的条件匹配：
If you want the pattern to start with a "1", you can just rotate it until it matches that condition:
"0011" from the second bit
"0110" from the third bit
"1100" from the fourth bit
编辑：
例如，在C＃中：
Example in C#:
void FindPattern(int n1, int n2) {
int digit = -1;
while (n1 >= n2) {
n2 <<= 1;
digit++;
}
Dictionary<int, int> states = new Dictionary<int, int>();
bool found = false;
while (n1 > 0 || digit >= 0) {
if (digit == -1) Console.Write('.');
n1 <<= 1;
if (states.ContainsKey(n1)) {
Console.WriteLine(digit >= 0 ? new String('0', digit + 1) : String.Empty);
Console.WriteLine("Repeat from digit {0} length {1}.", states[n1], states[n1] - digit);
found = true;
break;
}
states.Add(n1, digit);
if (n1 < n2) {
Console.Write('0');
} else {
Console.Write('1');
n1 -= n2;
}
digit--;
}
if (!found) {
Console.WriteLine();
Console.WriteLine("No repeat.");
}
}
与调用你的例子是输出：
Called with your examples it outputs:
.1
No repeat.
.01
Repeat from digit -1 length 2.
.10
Repeat from digit -1 length 2.
1.0
Repeat from digit 0 length 2.
.0011
Repeat from digit -1 length 4.
这篇关于算法检测循环小数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
