In questo esempio, imparerai a trovare il MCD di due numeri utilizzando due metodi diversi: funzione e loop e, algoritmo euclideo
Per comprendere questo esempio, dovresti avere la conoscenza dei seguenti argomenti di programmazione Python:
- Funzioni Python
- Ricorsione Python
- Argomenti della funzione Python
Il massimo comune divisore (MCD) o il massimo comune divisore (GCD) di due numeri è il più grande intero positivo che divide perfettamente i due numeri dati. Ad esempio, l'HCF di 12 e 14 è 2.
Codice sorgente: utilizzo di loop
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Produzione
L'HCF è 6
Qui, due numeri interi memorizzati nelle variabili num1 e num2 vengono passati alla compute_hcf()funzione. La funzione calcola l'HCF di questi due numeri e lo restituisce.
Nella funzione, determiniamo prima il più piccolo dei due numeri poiché l'HCF può essere solo minore o uguale al numero più piccolo. Quindi utilizziamo un forciclo per passare da 1 a quel numero.
In ogni iterazione, controlliamo se il nostro numero divide perfettamente entrambi i numeri di input. In tal caso, memorizziamo il numero come HCF. Al completamento del ciclo, si ottiene il numero più grande che divide perfettamente entrambi i numeri.
Il metodo sopra è facile da capire e implementare ma non efficiente. Un metodo molto più efficiente per trovare l'HCF è l'algoritmo euclideo.
Algoritmo euclideo
Questo algoritmo si basa sul fatto che anche l'HCF di due numeri divide la loro differenza.
In questo algoritmo, dividiamo il maggiore per minore e prendiamo il resto. Ora, dividi il più piccolo per questo resto. Ripeti fino a quando il resto è 0.
Ad esempio, se vogliamo trovare l'HCF di 54 e 24, dividiamo 54 per 24. Il resto è 6. Ora, dividiamo 24 per 6 e il resto è 0. Quindi, 6 è l'HCF richiesto
Codice sorgente: utilizzo dell'algoritmo euclideo
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Qui eseguiamo un ciclo finché y diventa zero. L'istruzione x, y = y, x % yesegue lo scambio di valori in Python. Fare clic qui per saperne di più sullo scambio di variabili in Python.
In ogni iterazione, mettiamo il valore di y in x e il resto (x % y)in y, simultaneamente. Quando y diventa zero, abbiamo HCF in x.
