Calculer la longueur de la période de la fraction décimale récurrente

Question

Je veux faire un programme en Python (3.6.5) qui indique la longueur de par exemple 1/7. La sortie devrait être pour cet exemple quelque chose comme: "longueur: 6, nombres répétés: 142857". J'ai fait ceci jusqu'à présent:

n = int(input("numérateur: "))
d = int(input("dénominateur: "))

def t(n, d):
    x = n * 9
    z = x
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1
        print ("longueur:", k)
        print ("nombres répétés:", t)

    return k, z / d

t(n, d)

Answer 1

En exécutant print ("nombres répétés :", t), on imprime la représentation de la fonction t, et non sa sortie.

Voici une version corrigée de votre code. J'utilise une f-string de Python 3.6+ pour convertir les chiffres répétés en une chaîne de caractères, et j'ajoute des zéros devant pour avoir la bonne longueur.

def find_period(n, d):
    z = x = n * 9
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1

    digits = f"{z // d:0{k}}"
    return k, digits

# Test

num, den = 1, 7
period, digits = find_period(num, den)
print('num:', num, 'den:', den, 'period:', period, 'digits:', digits)

num, den = 1, 17
period, digits = find_period(num, den)
print('num:', num, 'den:', den, 'period:', period, 'digits:', digits)

sortie

num: 1 den: 7 period: 6 digits: 142857
num: 1 den: 17 period: 16 digits: 0588235294117647

---

Cette ligne peut sembler un peu mystérieuse :

f"{z // d:0{k}}"

Cela signifie : Trouver le plus grand entier inférieur ou égal à z divisé par d, le convertir en une chaîne de caractères, et le remplir de zéros à gauche (si nécessaire) pour lui donner une longueur de k.

---

Comme le souligne Goyo dans les commentaires, cet algorithme n'est pas parfait. Il tourne en boucle si la décimale contient une partie non répétée, c'est-à-dire si le dénominateur contient des facteurs de 2 ou de 5. Voyez si vous pouvez trouver un moyen de gérer cela.

Answer 2

Voici mon implémentation Python de https://www.geeksforgeeks.org/find-recurring-sequence-fraction/

def fraction_to_decimal(numerator, denominator):
    """ Cette fonction renvoie la séquence récurrente d'une fraction.
        Si la séquence récurrente n'existe pas, renvoie une chaîne vide """

    # Créer une carte pour stocker les reste déjà vus
    # le reste est utilisé comme clé et sa position dans
    # le résultat est stocké comme valeur. Notez que nous avons
    # besoin de la position pour des cas comme 1/6.  Dans ce cas,
    # la séquence récurrente ne commence pas par le premier
    # reste.
    result = ""
    mapping = {}

    # Trouver le premier reste
    remainder = numerator % denominator

    # Continuer à trouver des restes jusqu'à ce que le reste soit
    # de 0 ou se répète
    while remainder != 0 and remainder not in mapping:

        # Stocker ce reste
        mapping[remainder] = len(result)

        # Multiplier le reste par 10
        remainder = remainder * 10

        # Ajouter le reste / dénominateur au résultat
        result_part = int(remainder / denominator)
        result += str(result_part)
        # print(f"Resultat: {result}")

        # Mettre à jour le reste
        remainder = remainder % denominator
        # print(f"Map: {mapping}")

    return result

if __name__ == '__main__':
    result = fraction_to_decimal(1, 7)
    if result == "":
        print("Aucune séquence récurrente")
    else:
        print(f"\nLongueur de la séquence récurrente: {len(result)}")
        print(f"\nLa séquence récurrente est {result}\n")