[PYTHON] Kaninchen- und Schildkrötenalgorithmus

Im Frühjahr 2014, am Nachmittag des dritten Quartals der Prüfung zum Ingenieur für angewandte Informationstechnologie, wurde ein Problem hinsichtlich des Algorithmus der Floyd-Zirkulationserkennungsmethode aufgeworfen.

Der Fragentext ist zu lang. Überprüfen Sie daher die Frage unter Applied Information Engineer Examination.com. In dem Problem wird das Verfahren des Verfolgens des Kreislaufs mit den Schritten von Kaninchen und Schildkröten verglichen.

Ich habe es in Python implementiert, machen Sie sich also hier eine Notiz. Ich möchte einen Kommentar hinzufügen, wenn ich Zeit habe.

Implementiert von Python

Ich habe den Standard unittest für das Python-Testframework verwendet. In dem Problem induziere ich, ** tapple (Pair) ** von (s, t) zurückzugeben, aber ich habe es hier ein wenig geändert, weil ich die Länge des kreisförmigen Knotens mit einer Funktion berechnen wollte.

import unittest


def cycle_finding(n):
    m, p = 1, 1  # m..Rest der Schildkrötenberechnung p..Rest der Kaninchenberechnung
    s, t = 0, 0  # s..Erste gebrochene Ziffernposition des Kreisknotens t..Letzte gebrochene Ziffernposition des Kreisknotens

    #Bis die restlichen übereinstimmen
    while True:
        m = (m * 10) % n                #Die Schildkröte macht einen Schritt
        p = (((p * 10) % n) * 10) % n   #Kaninchen macht zwei Schritte
        if m == p:
            break

    if p != 0:
        #Erkennung des Beginns des Kreisknotens
        p = 1
        s = 1
        while m != p:
            s += 1
            m = (m * 10) % n
            p = (p * 10) % n
        #Erkennung des Endes des Kreisknotens
        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()

Fortsetzung der Antwort

Basierend auf dem gegebenen n, ausgedrückt in O-Notation, ist die Größe des Speicherbereichs, der vom Programm der Funktion junkan benötigt wird, "o" und der Berechnungsbetrag "ka".

In dem Python-Code, den ich oben geschrieben habe, habe ich den Funktionsnamen in cycle_finding anstelle von junkan geändert. Ich war überrascht, weil es keinen Kommentar auf der Seite gab, aber als meine Antwort,

** Da die Größe des Speicherbereichs nur vier Variablen umfasst, m, p, s und t, Ο (1) **

Die berechnete Zeit

Auf diese Weise holt das Kaninchen in allen n, die kreisförmige Fraktionen sind, immer die Schildkröte ein, die in einigen Runden des zirkulierenden Teils geläppt ist, und die Reste von beiden sind gleich.

...

Wenn die Reste der beiden übereinstimmen, fährt die Schildkröte fort, das Kaninchen kehrt zum Anfang zurück, und diesmal machen beide einen Schritt nach dem anderen, wie in Abbildung 4 gezeigt. Der Quotient der nächsten Division, bei dem die Reste beider zuerst übereinstimmen (<9> und << 9 >>), ist der Anfang des Zirkelsatzes.

...

Nach dem Erkennen des Beginns des kreisförmigen Knotens, wie in 5 gezeigt, rückt nur das Kaninchen Schritt für Schritt das Ende des kreisförmigen Knotens vor, bis die Schildkröte und der Rest wieder übereinstimmen (<9> und << 15 >>). Zu erkennen.

** Sie können erkennen, dass es Ο (n) ist, da die obigen drei Schleifen höchstens Ο (n) sind. ** ** **

Ich kann keine Verantwortung für die Erklärung übernehmen. Ich werde beim nächsten Mal eine Sammlung vergangener Probleme kaufen.

schließlich

Zuerst habe ich es in C ++ geschrieben, aber ich dachte, es wäre besser, es in Zukunft in Python zu schreiben, also habe ich es in Python umgeschrieben.