Algorithme de lapin et de tortue

Au printemps 2014, dans l'après-midi Q3 de l'Examen Applied Information Technology Engineer, un problème a été soulevé concernant l'algorithme de la méthode de détection de circulation Floyd.

Le texte de la question est trop long, veuillez donc vérifier la question sur Applied Information Engineer Examination.com. Dans le problème, la procédure de suivi de la circulation est assimilée aux étapes des lapins et des tortues.

Je l'ai implémenté en Python, alors notez ici. Je voudrais ajouter un commentaire si j'ai du temps à perdre.

Implémenté par Python

J'ai utilisé le test unittest standard pour le framework de test Python. Dans le problème, j'incite à retourner ** tapple (Pair) ** de (s, t), mais je l'ai un peu changé ici car je voulais calculer la longueur du nœud circulaire avec une fonction.

import unittest


def cycle_finding(n):
    m, p = 1, 1  # m..Reste du calcul des tortues p..Reste du calcul du lapin
    s, t = 0, 0  # s..Position du premier chiffre fractionnaire du nœud circulaire t..Position du dernier chiffre fractionnaire du nœud circulaire

    #Jusqu'à ce que le reste corresponde
    while True:
        m = (m * 10) % n                #La tortue fait un pas
        p = (((p * 10) % n) * 10) % n   #Le lapin fait deux pas
        if m == p:
            break

    if p != 0:
        #Détection du début du nœud circulaire
        p = 1
        s = 1
        while m != p:
            s += 1
            m = (m * 10) % n
            p = (p * 10) % n
        #Détection de la fin du nœud circulaire
        p = (p * 10) % n
        t = s
        while m != p:
            t += 1
            p = (p * 10) % n

    if s == 0 and t == 0:
        return 0
    else:
        return t - s + 1


class TestCycleFinding(unittest.TestCase):
    def test_1st_decimal_place(self):
        # n = 3     1 / 3 = 0.33333... -> 0.(3)
        self.assertEqual(cycle_finding(3), 1)

    def test_2nd_decimal_place(self):
        # n = 6     1 / 6 = 0.16666... -> 0.1(6)
        self.assertEqual(cycle_finding(6), 1)

    def test_max_digits(self):
        # n = 7     1 / 7 = 0.14285714285714... -> 0.(142857)
        self.assertEqual(cycle_finding(7), 6)

    def test_two_digit_number(self):
        # n = 56    1 / 56 = 0.01785714285714285... -> 0.017(857142)
        self.assertEqual(cycle_finding(56), 6)


if __name__ == '__main__':
    unittest.main()

Suite de la réponse

Sur la base du n donné, exprimé en notation O, la taille de la zone de stockage requise par le programme de la fonction junkan est «o», et la quantité de calcul est «ka».

Dans le code Python que j'ai écrit ci-dessus, j'ai changé le nom de la fonction en cycle_finding au lieu de junkan. J'ai été surpris car il n'y avait pas de commentaire sur le site, mais comme ma réponse,

** Étant donné que la taille de stockage ne concerne que quatre variables, m, p, s et t, Ο (1) **

Le temps calculé

De cette façon, dans tous les n qui sont des fractions circulaires, le lapin rattrape toujours la tortue qui est rodée dans quelques tours de la partie circulante, et les restes des deux sont les mêmes.

...

Lorsque le reste des deux correspond, la tortue continue, le lapin revient au début, et cette fois les deux font un pas à la fois, comme le montre la figure 4. Le quotient de la division suivante où les restes des deux correspondent en premier (<9> et << 9 >>) est le début de la clause circulaire.

...

Après avoir détecté le début du nœud circulaire, comme le montre la figure 5, seul le lapin avance pas à pas la fin du nœud circulaire jusqu'à ce que la tortue et le reste correspondent à nouveau (<9> et << 15 >>). Détecter.

** Vous pouvez dire que c'est Ο (n) parce que les trois boucles ci-dessus sont au plus Ο (n). ** **

Je ne peux pas assumer la responsabilité de l'explication. J'achèterai une collection de problèmes passés la prochaine fois.

à la fin

Au début, je l'ai écrit en C ++, mais je pensais qu'il serait préférable de l'écrire en Python à l'avenir, alors je l'ai réécrit en Python.