U ovom ćete primjeru naučiti pronaći GCD dva broja koristeći dvije različite metode: funkciju i petlje i, Euklidov algoritam
Da biste razumjeli ovaj primjer, trebali biste imati znanje o sljedećim temama programiranja na Pythonu:
- Python funkcije
- Python rekurzija
- Argumenti funkcije Python
Najveći zajednički faktor (HCF) ili najveći zajednički djelitelj (GCD) dvaju brojeva najveći je pozitivni cijeli broj koji savršeno dijeli dva zadana broja. Na primjer, HCF od 12 i 14 je 2.
Izvorni kod: Korištenje petlji
# 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))
Izlaz
HCF je 6
Ovdje se compute_hcf()funkciji prosljeđuju dvije cijele vrijednosti pohranjene u varijablama num1 i num2 . Funkcija izračunava HCF ova dva broja i vraća ga.
U funkciji prvo određujemo manji od dva broja jer HCF može biti samo manji ili jednak najmanjem broju. Zatim pomoću forpetlje idemo od 1 do tog broja.
U svakoj iteraciji provjeravamo dijeli li naš broj savršeno oba ulazna broja. Ako je tako, pohranjujemo broj kao HCF. Po završetku petlje na kraju imamo najveći broj koji savršeno dijeli oba broja.
Gornju je metodu lako razumjeti i primijeniti, ali nije učinkovita. Puno učinkovitija metoda za pronalaženje HCF-a je euklidski algoritam.
Euklidov algoritam
Ovaj se algoritam temelji na činjenici da HCF dva broja dijeli i njihovu razliku.
U ovom algoritmu dijelimo veće s manjima i uzimamo ostatak. Sada, podijelite manje s ovim ostatkom. Ponavljajte dok ostatak ne postane 0.
Na primjer, ako želimo pronaći HCF od 54 i 24, podijelimo 54 sa 24. Ostatak je 6. Sada, dijelimo 24 sa 6, a ostatak je 0. Dakle, 6 je potreban HCF
Izvorni kod: Korištenje euklidskog algoritma
# 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)
Ovdje petljamo dok y ne postane nula. Izjava x, y = y, x % yvrši zamjenu vrijednosti u Pythonu. Kliknite ovdje da biste saznali više o zamjeni varijabli u Pythonu.
U svaku iteraciju istovremeno stavljamo vrijednost y u x, a ostatak (x % y)u y. Kad y postane nula, imamo HCF u x.
