Python implementiert die Methode zur Lösung des größten gemeinsamen Teilers

Dieses Mal werde ich Ihnen Python zur Implementierung der Methode zur Lösung des größten gemeinsamen Teilers bringen. Welche Vorsichtsmaßnahmen gibt es für Python, um die Methode zur Lösung des größten gemeinsamen Teilers zu implementieren? Das Folgende ist ein praktischer Fall.

Ziehen Sie zunächst eine Beschreibung des Algorithmus aus dem Internet wie folgt aus:

Zusätzliche Phasensubtraktionsmethode: Auch Phasenänderungssubtraktionsmethode genannt, handelt es sich um eine Maximumkonvention aus „Neun Kapitel“. Der Algorithmus der Arithmetik ist ein Algorithmus für Zahlen. Er wurde ursprünglich für die Reduktion entwickelt, eignet sich aber für alle Situationen, in denen der größte gemeinsame Teiler gefunden werden muss.

„Neun Kapitel über Arithmetik“ ist eine alte chinesische Mathematikabhandlung. Die darin enthaltene „Zusätzliche Subtraktionstechnik“ kann verwendet werden, um den größten gemeinsamen Teiler zweier Zahlen zu finden, d. h. „. derjenige, der die Hälfte sein kann. „Die Hälfte, wenn die Hälfte nicht erlaubt ist, ersetzen Sie die Zahl des Nenners und des Kindes und reduzieren Sie die größere Zahl, indem Sie sie reduzieren, sodass sie um gleiche Zahlen reduziert werden kann.“

In die moderne Sprache übersetzt:

Schritt 1: Bestimmen Sie bei zwei beliebigen positiven Ganzzahlen, ob beide gerade Zahlen sind. Wenn ja, verwenden Sie 2 zum Reduzieren; wenn nicht, führen Sie den zweiten Schritt aus.

Schritt 2: Subtrahieren Sie die kleinere Zahl von der größeren Zahl, vergleichen Sie dann die resultierende Differenz mit der kleineren Zahl und reduzieren Sie die Zahl von der größeren Zahl. Setzen Sie diesen Vorgang fort, bis der resultierende Subtrahend und die Differenz gleich sind.

Nachdem ich die obige Beschreibung gelesen hatte, war meine erste Reaktion: Stimmt etwas mit dieser Beschreibung nicht? Im Hinblick auf die Universalität dürfte es Probleme geben. Wenn ich zum Beispiel den größten gemeinsamen Teiler von 4 und 4 finde, aber nach halb und halb, muss das Ergebnis falsch sein! Auch der folgende Algorithmus kann nicht ausgeführt werden!

Wie auch immer, implementieren wir zuerst die obige Algorithmusbeschreibung:

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  # even process
  while m % 2 == 0 and n % 2 == 0:
    m = m / 2
    n = n / 2
  # exchange order when needed
  if m < n:
    m,n = n,m
  # calculate the max comm pisor
  while m - n != n:
    diff = m - n
    if diff > n:
      m = diff
    else:
      m = n
      n = diff
  return n
print(MaxCommpisor(55,120))
print(MaxCommpisor(55,77))
print(MaxCommpisor(32,64))
print(MaxCommpisor(16,128))

Laufende Ergebnisse:

Unnötig zu sagen, das obige Programm Die Ausführung ist voller Fehler. Wie kann man es also korrigieren?

Zunächst einmal sollten alle Divisionen durch 2 am Ende zurückgezählt werden! Auf diese Weise wird das Programm wie folgt geändert:

def MaxCommpisor(m,n):
  com_factor = 1
  if m == n:
    return n
  else:
    # process for even number
    while m % 2 == 0 and n % 2 == 0:
      m = int(m / 2)
      n = int(n / 2)
      com_factor *= 2
    if m < n:
      m,n = n,m
    diff = m - n
    while n != diff:
      m = diff
      if m < n:
        m,n = n,m
      diff = m - n
    return n * com_factor
print(MaxCommpisor(55,120))
print(MaxCommpisor(55,77))
print(MaxCommpisor(32,64))
print(MaxCommpisor(16,128))

Nach der Änderung ist das Ausführungsergebnis des obigen Programms wie folgt

Obwohl dies Das Programm sieht beim Schreiben etwas seltsam aus, aber der Gesamtalgorithmus ist immer noch implementiert. Im Vergleich zu Algorithmen wie der euklidischen Division wird diese Wahrscheinlichkeit auf der Ebene der

Schleife bis zu einem gewissen Grad reduziert. Insbesondere bei den letzten beiden Testzahlenpaaren ist der Effekt in diesem Fall besser. Ich bin jedoch noch nicht in der Lage, eine genaue Messung der Gesamteffizienz des Algorithmus zu geben.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website !

Empfohlene Lektüre:

Zusammenfassung der Pycharm-Nutzungsfähigkeiten

So erhalten Sie den lokalen Spitzenwert einer Zweidimensionalität Array in Python

Das obige ist der detaillierte Inhalt vonPython implementiert die Methode zur Lösung des größten gemeinsamen Teilers. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!