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.

# -*- 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))

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))

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.

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!