Programma Python per trovare il massimo comune divisore (HCF) o il massimo divisore comune (GCD)

Enciclopedia di esempi di Python

In questo esempio, imparerai a trovare il GCD di due numeri utilizzando due metodi diversi: funzione e ciclo, nonché l'algoritmo di Eulero

Per comprendere questo esempio, dovresti conoscere i seguentiProgrammazione PythonArgomento:

• Funzione Python

• Ricorsione Python

• Parametri della funzione Python

Il massimo comune divisore (H.C.F) o il massimo divisore comune (G.C.D) è il più grande numero intero positivo che può dividere perfettamente due numeri dati. Ad esempio, H.C.F(12, 14) è uguale a 2.

Codice sorgente: utilizzo del ciclo

# Programma Python per trovare il massimo comune divisore (H.C.F) di due numeri
# Definire una funzione
def compute_hcf(x, y):
# Scegliere il numero più piccolo
　　　　se x > y:
　　　　　　　　smaller = y
　　　　altrimenti:
　　　　　　　　smaller = x
　　　　per i in range(1, smaller+1):
　　　　　　　　se (x % i == 0) e (y % i == 0):
　　　　　　　　　　　　hcf = i　
　　　　return hcf
num1 = 54　
num2 = 24
print("L'HCF è", compute_hcf(num1, num2))

Risultato di output

L'H.C.F. è 6

Qui, i due interi memorizzati nelle variabili num1 e num2 vengono passati alla funzione compute hcf(). La funzione calcola l'H.C.F. di questi due numeri e lo restituisce.

In questa funzione, determiniamo prima quale dei due numeri è più piccolo e può essere uguale o minore del numero più piccolo. Poi usiamo un ciclo for da 1 a quel numero.

In ogni iterazione, controlliamo se i nostri numeri dividono perfettamente i due numeri di input. Se è così, memorizziamo questo numero come H.C.F., alla fine del ciclo, otteniamo il numero più grande che divide perfettamente i due numeri.

Il metodo menzionato sopra è facile da comprendere e implementare, ma non è efficiente. Un metodo più efficace per trovare l'HCF è l'algoritmo di Eulero.

Algoritmo di Eulero

Questo algoritmo si basa sul fatto che l'HCF di due numeri dividerà anche la loro differenza.

In questo algoritmo, dividiamo il maggiore per il minore e prendiamo il resto. Ora, dividiamo il minore per questo resto. Ripetiamo fino a quando il resto è 0.

Ad esempio, se vogliamo trovare l'HCF di 54 e 24, dividiamo 54 per 24. Il resto è 6. Dividiamo 24 per 6, il resto è 0. Quindi, 6 è l'HCF necessario

Codice sorgente: utilizzo dell'algoritmo di Eulero

# La funzione trova l'HCF utilizzando l'algoritmo di Eulero
def compute_hcf(x, y):
　　　while(y):
　　　　　　　x, y = y, x % y
　　　return x
hcf = compute_hcf(300, 400)
print("L'HCF è", hcf)

Qui loopiamo fino a quando y diventa zero. La frase x, y = y, x % y scambia i valori in Python. Clicca qui per informazioni suScambio delle variabili in PythonUlteriori informazioni.

In ogni iterazione, mettiamo contemporaneamente il valore di y in x, e il resto (x % y) in y. Quando y diventa 0, otteniamo l'HCF di x.

Enciclopedia di esempi di Python