În acest exemplu, veți învăța să găsiți GCD-ul a două numere folosind două metode diferite: funcție și bucle și, algoritmul euclidian
Pentru a înțelege acest exemplu, ar trebui să aveți cunoștințele următoarelor subiecte de programare Python:
- Funcții Python
- Recursiune Python
- Argumente ale funcției Python
Cel mai mare factor comun (HCF) sau cel mai mare divizor comun (GCD) a două numere este cel mai mare întreg pozitiv care împarte perfect cele două numere date. De exemplu, HCF de 12 și 14 este 2.
Cod sursă: Utilizarea buclelor
# 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))
Ieșire
HCF este 6
Aici, două numere întregi stocate în variabilele num1 și num2 sunt transmise compute_hcf()funcției. Funcția calculează HCF aceste două numere și o returnează.
În funcție, determinăm mai întâi cel mai mic dintre cele două numere, deoarece HCF nu poate fi decât mai mic sau egal cu cel mai mic număr. Apoi folosim o forbuclă pentru a merge de la 1 la acel număr.
În fiecare iterație, verificăm dacă numărul nostru împarte perfect atât numerele de intrare. Dacă da, stocăm numărul ca HCF La finalizarea buclei, ajungem cu cel mai mare număr care împarte perfect ambele numere.
Metoda de mai sus este ușor de înțeles și implementat, dar nu este eficientă. O metodă mult mai eficientă pentru a găsi HCF este algoritmul euclidian.
Algoritm euclidian
Acest algoritm se bazează pe faptul că HCF din două numere le împarte și diferența.
În acest algoritm, împărțim cel mai mare la cel mai mic și luăm restul. Acum, împărțiți cel mai mic cu acest rest. Repetați până când restul este 0.
De exemplu, dacă vrem să găsim HCF de 54 și 24, împărțim 54 la 24. Restul este 6. Acum, împărțim 24 la 6 și restul este 0. Prin urmare, 6 este HCF necesar
Cod sursă: Utilizarea algoritmului euclidian
# 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)
Aici facem o buclă până când y devine zero. Declarația x, y = y, x % yface schimb de valori în Python. Faceți clic aici pentru a afla mai multe despre schimbarea variabilelor în Python.
În fiecare iterație, plasăm valoarea lui y în x și restul (x % y)în y, simultan. Când y devine zero, avem HCF în x.
