Algorithmus für die Erkennung von sich wiederholenden Nachkommastellen?

Finden, die sich wiederholenden Muster, verfolgen Sie die Werte, die Sie verwenden, entlang der Linie:

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

So erreichen Sie den gleichen Wert wie an der zweiten bit, wird der Vorgang einfach wiederholen, von diesem Zeitpunkt produzieren die gleiche bit-Muster über und über. Sie haben das Muster "0011" die Wiederholung aus dem zweiten bit (das erste nach dem Dezimaltrennzeichen).

Wenn Sie wollen, die Muster beginnen mit einer "1", können Sie einfach drehen, bis es passt, Zustand:

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

Edit:

Beispiel in 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.");
   }
}

Genannt, mit Ihrem Beispiele gibt es:

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

InformationsquelleAutor Guffa

Kann ich einen Tipp geben - sich wiederholende Dezimalstellen in der Basis zehn sind alle Bruch mit dem Nenner mit mindestens einem prime, andere Faktoren als die zwei und die fünf. Wenn der Nenner enthält keine Primfaktoren zwei oder fünf ist, können Sie immer dargestellt werden mit einem Nenner von allen Neunen. Dann wird der Zähler ist der sich wiederholende Teil und die Anzahl der Neunen ist die Länge der sich wiederholenden Teil.

3     _
- = 0.3
9

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

Ob es Primzahlen sind Faktoren, die zwei oder fünf in den Nenner, der die Wiederholung beginnt der Teil, der nicht an der ersten Stelle.

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

Aber ich kann mich nicht erinnern, wie zur Ableitung der nicht-wiederholenden Teil und seine Länge.

Diese scheinen gut übersetzen zu Basis zwei. Nur die Fraktion mit einer Leistung von zwei Nenner sind nicht zu wiederholen. Dies kann leicht überprüft werden, indem man behauptet, dass nur ein einziges bit in den Nenner gesetzt wird.

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

Alle Fraktionen mit ungeradem Nenner sollte die Wiederholung und die Muster und kann in der Länge erhalten werden, indem man den Bruch mit einem Nenner der form 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

Als für die Basis zehn ist, kann ich nicht sagen, wie Sie zu behandeln Nenner enthält, aber nicht eine Potenz von zwei sein - zum Beispiel 12 = 3 * 2^2.

InformationsquelleAutor Daniel Brückner

Check-out Nachkommastellen, und insbesondere über den Zeitraum von einem Bruchteil.

InformationsquelleAutor Nick Dandoulakis