代码之家 › 专栏 › 技术社区 › Imagist

检测重复小数的算法?

rational-numbers algorithm

Imagist · 技术社区 · 17 年前

有没有一种算法可以解决以下问题?

如果除法的结果是重复的十进制(二进制)。
如果重复,重复从哪个数字(表示为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 (为了方便起见,我可以用它)。我这样说是因为如果你在解释的话,你可能更容易用10进制来解释:)。

6 回复 | 直到 17 年前

Steve Gilham 17 年前

如果除数不是2的幂(通常,包含不与表示基共享的素因子)
重复周期长度将由股息的最大素因子驱动(但与该因子表示的长度无关——见十进制中的1/7),但第一个周期长度可能与重复单位不同(例如,11/28=1/4+1/7十进制)。
实际循环将取决于分子。

Daniel Brückner 17 年前

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

至于基数10,我不知道如何处理包含但不是2的幂的分母,例如12= 3 * 2^2

Todd Li 17 年前

首先,你的一个例子是错误的。重复部分 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)

Nick Dandoulakis 17 年前

decimal expansion ,特别是关于分数的周期。

Heiko Schäfer 10 年前

long division ,注意到剩余部分。余数的结构将为您提供任何 有理小数 :

最后一个余数是零:它是一个没有任何重复部分的十进制数
第一个余数和最后一个余数相等:小数点正后方重复

您可以在中看到编码的算法 C++ 在方法中 decompose() here

Try 228142/62265 ,它有一段时间数字!

Guffa 17 年前

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

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.