algorithm - 小数の繰り返しを検出するアルゴリズム?

Question

次のことを理解するためのアルゴリズムはありますか?

除算の結果が繰り返し 10 進数 (2 進数) の場合。
繰り返す場合、繰り返しは何桁 (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進数で説明する方が簡単かもしれないからです:)。

score 10 · Accepted Answer

除数が 2 の累乗でない場合 (一般に、表現の基数と共有されない素因数が含まれます)
繰り返しサイクルの長さは、被除数の最大の素因数によって駆動されます (ただし、その係数の表現の長さとは関係ありません。10 進数で 1/7 を参照してください)。ただし、最初のサイクルの長さは繰り返し単位とは異なる場合があります (例: 11/28 = 10 進数で 1/4+1/7)。
実際のサイクルは分子によって異なります。

score 8 · Accepted Answer

ヒントを与えることができます-10を底とする循環小数はすべて分数であり、分母は2と5以外の少なくとも1つの素因数を持っています。分母に素因数2または5が含まれていない場合、それらは常に9つすべての分母で表すことができます。その場合、指名者は繰り返し部分であり、9の数は繰り返し部分の長さです。

3     _
- = 0.3
9

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

分母に素因数2または5がある場合、繰り返し部分は最初の位置から始まりません。

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

しかし、繰り返さない部分とその長さをどのように導き出すかは思い出せません。

これは、2進数にうまく変換されるようです。2の分母の累乗を持つ分数だけが繰り返されません。これは、分母の1ビットのみが設定されていることを表明することで簡単に確認できます。

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の累乗を含むが、2の累乗ではない分母の処理方法がわかりません（たとえば、12 =）3 * 2^2。

score 5 · Accepted Answer

まず、あなたの例の 1 つが間違っています。の繰り返し部分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 の任意の倍数で除算することによって生成されます。そのため、分母をそのように表現する方法を見つけるか (定数テーブルを作成するなど)、大きな数の除算を行うことができます (これは比較的遅い）ループを見つけます。これを行う簡単な方法はありません。(2ⁿ - 1)

score 3 · Accepted Answer

3

小数展開、特に分数のピリオドについて調べてください。

于 2009-08-22T09:37:30.613 に答える

score 2 · Accepted Answer

剰余に注意して、長い除算を行うことができます。剰余の構造は、任意の有理小数の構造を示します。

最後の剰余がゼロ: 繰り返し部分のない小数です
最初と最後の剰余が等しい: 小数はドットの直後に繰り返されます
最初の部分と最初の部分の間の距離は、最後の部分に等しい剰余は非反復数字であり、剰余は反復部分です。

一般に、距離は各部分の桁数を示します。

C++でコーディングされたこのアルゴリズムは、decompose() こちらのメソッドで確認できます。

試してみてください 228142/62265。ピリオドは1776桁です。

score 1 · Accepted Answer

繰り返しパターンを見つけるには、線に沿って使用する値を追跡してください。

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

2 番目のビットと同じ値に到達すると、その時点からプロセスが繰り返され、同じビットパターンが何度も生成されます。パターン「0011」が 2 番目のビット (小数点の後の最初) から繰り返されています。

パターンを「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.

algorithm - 小数の繰り返しを検出するアルゴリズム?

6 に答える 6

Related

Reference