用于检测重复小数的算法？

一尘不染

用于检测重复小数的算法？

algorithm

是否有一种算法可以解决以下问题？

如果除法结果是重复的十进制（二进制）。
如果重复，重复从哪一位开始（以2的幂表示）？
什么数字重复？

一些例子：

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

有没有办法做到这一点？效率是一个大问题。对算法的描述比对代码的描述更可取，但我将尽我所能。

还值得注意的是，这个基数并不大。我可以将算法转换为二进制（或者，如果它位于基数256中以char方便使用s，我也可以使用它）。我之所以这样说是因为，如果您要解释的话，以10为基的解释可能会更容易。

阅读 236

2020-07-28

共1个答案

一尘不染

要查找重复模式，只需跟踪沿线使用的值即可：

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”。

如果您希望模式以“ 1”开头，则可以旋转模式直到它符合该条件：

"0011" from the second bit
"0110" from the third bit
"1100" from the fourth bit

编辑：
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.");
   }
}

用您的示例调用它输出：

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

2020-07-28