算法用于检测循环小数？(Algorithm for detecting repeating deci

有没有搞清楚下面的东西的算法？

如果除法的结果是重复十进制（二进制）。
如果重复，在什么数字（表示为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 :)解释。

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

Answer 2:

如果除数不是2的幂（通常，包含素因子不与表示的基共享）
重复周期长度将被除数的最大素数因子被驱动的（但不与因子的表示的长度连接的 - 见十进制1/7），但在第一周期长度可以从重复单元不同（例如11/28 = 1/4 + 1 /十进制7）。
实际周期将取决于分子。

Answer 3:

我可以给一个提示 - 十进制中循环小数与具有两个以上与其他五个至少一个主要因素分母分数全部。如果分母不包含素因子两个或五种，它们总是可以与所有花枝招展的分母表示。然后，提名是重复部分和的9的数目是重复部分的长度。

3     _
- = 0.3
9

1   142857     ______
- = ------ = 0.142857
7   999999

如果有质因子两个或五个分母，重复部分开始没有在第一位置。

17    17        ______
-- = ----- = 0.4857142
35   5 * 7

但我不记得如何推导出非重复的部分，它的长度。

这似乎很好地转化为基地二期。仅具有两个分母的功率部分是非重复。这可以通过断言，只有在分母单位设置便于检查。

1/2 =   1/10   = 0.1
1/4 =   1/100  = 0.01
3/4 =  11/100  = 0.11
5/8 = 101/1000 = 0.101

与奇分母所有分数应该重复和可通过表达与分母的分数的形式获得的图案和其长度2^n-1 。

                                                     __
 1/3            =  1/(2^2-1) =        1/11       = 0.01
                                                     __
 2/3            =  2/(2^2-1) =       10/11       = 0.10
                       __
 4/3  => 1 + 1/3 =>  1.01
                       __
10/3  => 3 + 1/3 => 11.01
                                                     ____
 1/5  =   3/15  =  3/(2^4-1) =       11/1111     = 0.0011
                                                     ________
11/17 = 165/255 = 11/(2^8-1) = 10100101/11111111 = 0.10100101

至于碱10，我不能告诉如何处理包含分母但不是二的幂-例如12 = 3 * 2^2 。