Algorithme de détection des décimales répétitives?

Question

Existe-t-il un algorithme pour déterminer les éléments suivants?

1. Si le résultat d'une division est un nombre décimal répétitif (en binaire).
2. Si elle se répète, à quel chiffre (représenté par une puissance de 2) la répétition commence-t-elle?
3. Quels sont les chiffres qui se répètent?

Quelques exemples:

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 

Est-il possible de le faire? L'efficacité est une grande préoccupation. Une description de l'algorithme serait préférable au code, mais je prendrai la réponse que je peux obtenir.

Il est également intéressant de noter que la base n'est pas une grosse affaire; Je peux convertir l'algorithme en binaire (ou s'il est en, disons base 256 pour utiliser char s pour la facilité, je pourrais juste l'utiliser). Je dis cela parce que si vous expliquez cela pourrait être plus facile pour vous d'expliquer dans la base 10 :).

Answer 1

Pour trouver le motif répétitif, il suffit de garder la trace des valeurs que vous utilisez le long de la ligne:

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 

Comme vous atteindre la même valeur que vous aviez au second bit, le processus vient répéter de cette point produisant le même motif de bits encore et encore. Vous avez le motif "0011" qui se répète à partir du deuxième bit (premier après le séparateur décimal).

Si vous voulez que le motif à commencer par un "1", il vous suffit de tourner jusqu'à ce qu'elle corresponde à cette condition:

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

Edit:
Exemple en 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."); 
    } 
} 

Appelé avec vos exemples, il sort:

.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

1. si le diviseur est pas une puissance de deux (en général, ne contient facteurs premiers pas partagés avec la base de la représentation)
2. longueur de cycle de répétition sera entraîné par le plus grand facteur premier du dividende (mais pas lié à la longueur de la représentation de ce facteur - voir 1/7 en décimal), mais la longueur du premier cycle peut différer de l'unité de répétition (par exemple 11/28 = 1/4 + 1/7 en décimal).
3. Le cycle réel dépendra du numérateur.

Answer 3

Découvrez decimal expansion, et plus particulièrement la période d'une fraction.

Answer 4

Je peux donner un indice - les décimales répétitives dans la base dix sont toutes les fractions avec le dénominateur ayant au moins un facteur premier autre que deux et cinq. Si le dénominateur ne contient pas de facteurs premiers deux ou cinq, ils peuvent toujours être représentés avec un dénominateur de tous les neuf. Alors le nominateur est la partie répétitive et le nombre de neuf est la longueur de la partie répétée.

3  _ 
- = 0.3 
9 

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

S'il existe des facteurs premiers deux ou cinq dans le dénominateur, la partie répétée ne commence pas à la première position. Mais je ne me souviens pas comment dériver la partie non-répétitive et sa longueur.

Ceci semble bien se traduire en base deux. Seule la fraction ayant une puissance de deux dénominateurs est non répétitive. Cela peut être facilement vérifié en affirmant que seulement un seul bit dans le dénominateur est défini.

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

Toutes les fractions avec des dénominateurs impairs devraient être répètent et le motif et sa longueur peut être obtenue en exprimant la fraction dont le dénominateur est sous la forme 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 

Quant à base dix, je ne peux pas dire comment gérer dénominateurs contenant, mais ne pas être une puissance de deux - par exemple 12 = 3 * 2^2.

Answer 5

Tout d'abord, un de vos exemples est faux. La partie répétitive de 1/5 est 0011 plutôt que 1100, et elle commence au tout début de la partie fractionnaire.

Une répétition décimale est quelque chose comme:

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

dans lequel n et d sont ce que vous voulez.

Par exemple,

1/10(dec) = 1/1010(bin) = 0.0001100110011... // 1 = true, 2 = -1, 3 = 0011

pourrait être représenté par la formule avec

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

Par conséquent, 1/10 = 0.1 * 0.0011/0.1111. La partie clé d'une représentation décimale répétitive est générée en divisant par (2n - 1) ou son multiple de 2. Vous pouvez donc soit trouver un moyen d'exprimer votre dénominateur en tant que tel (comme construire des tables constantes), soit faire une division en grands nombres (qui est relativement lent) et trouver la boucle. Il n'y a pas de moyen rapide de faire ça.

Answer 6

Vous pouvez n faire un long division, en notant les restes. La structure des reliquats vous donnera la structure de toute décimale rationnelle:

1. le dernier reste est nul: il est une décimale sans partie répéter
2. le premier et le dernier reste sont égaux: la décimal répète juste après le point
3. la distance entre le premier et le premier reste égale à la dernière sont les chiffres non répétitif, le reste est la partie répétant

En général, les distances wi Je vais vous donner la quantité de chiffres pour chaque partie.

Vous pouvez voir cet algorithme codé en C++ dans la méthode decompose()here.

Try228142/62265, il a une période de chiffres!