检测重复小数的算法？

是否有算法来计算以下内容？如果除法的结果是重复的十进制（二进制）。如果它重复，那么重复开始的是什么数字（表示为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以使用chars轻松，我可以使用它）。我这样说是因为如果你在解释它可能更容易在基地10解释:)。

已邀请:

6 个回复

帆攀缺锯欧

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

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.

为陡土

如果除数不是2的幂（一般来说，包含不与表示基础共享的素数因子）重复周期长度将由被除数的最大素因子驱动（但不与该因子的表示长度相关 - 见十进制的1/7），但第一周期长度可能与重复单位不同（例如11/28 = 1/4 + 1/7（十进制）。实际周期取决于分子。

量华

我可以给出一个提示 - 基数十位的重复小数是所有分数，分母至少有一个素数因子而不是两个和五个。如果分母不包含素数因子2或5，则它们总是可以用所有9的分母表示。然后，分子是重复部分，9的数量是重复部分的长度。

3     _
- = 0.3
9

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

如果分母中存在两个或五个素因子，则重复部分不在第一个位置开始。

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

但我不记得如何推导非重复部分及其长度。这似乎很好地转化为基础二。只有具有2分母幂的分数是非重复的。通过断言分母中只有一个位被设置，可以很容易地检查这一点。

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

至于十号基础，我不知道如何处理包含但不是两个幂的分母 - 例如12 =3 * 2^2。

艾食魄轻县

首先，你的一个例子是错误的。 1/5的重复部分是0011而不是1100，它从小数部分的最开始处开始。重复的小数是这样的：

a/b = c + d(2^-n + 2^-n-k + 2^-n-2k + ...)

    = c + 2^-n * d / (1 - 2^-k)

其中n和d是你想要的。例如， 1/10_(dec) = 1/1010_(bin) = 0.0001100110011... // 1 = true, 2 = -1, 3 = 0011 可以用公式表示

a = 1, b = 10_(dec), c = 0, d = 0.0011_(bin), n = 1, k = 4; 

(1 - 2^-k) = 0.1111

因此，1/10 = 0.1 * 0.0011/0.1111。重复十进制表示的关键部分是通过除以(2ⁿ - 1)或其任意倍数2来生成的。因此，您可以找到一种方法来表达您的分母（如构建常量表），或者执行大数除法（这是相对慢）并找到循环。没有快速的方法来做到这一点。

艰管垮淮

查看十进制扩展，特别是关于分数的周期。

郡豪靠暖

你可以进行长时间的划分，注意剩余部分。余数的结构将为您提供任何有理小数的结构：最后一个余数为零：它是一个小数，没有任何重复部分第一个和最后一个余数相等：小数点在点之后重复第一个和第一个剩余部分之间的距离等于最后一个是非重复数字，其余部分是重复部分通常，距离将为您提供每个零件的位数。你可以在这里的方法decompose()中看到用C ++编写的算法。试试228142/62265，它的周期为1776位！

要回复问题请先登录或注册

检测重复小数的算法？

6 个回复

发起人

rational_numbers

问题状态

检测重复小数的算法？

与内容相关的链接

6 个回复

发起人

rational_numbers

问题状态