V tem primeru se boste naučili poiskati GCD dveh števil s pomočjo dveh različnih metod: funkcije in zank ter evklidskega algoritma
Če želite razumeti ta primer, morate poznati naslednje programske teme Python:
- Python funkcije
- Python rekurzija
- Argumenti funkcije Python
Najvišji skupni faktor (HCF) ali največji skupni delilec (GCD) dveh števil je največje pozitivno celo število, ki popolnoma deli dve dani števili. Na primer, HCF 12 in 14 je 2.
Izvorna koda: Uporaba zank
# 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))
Izhod
HCF je 6
Tu se compute_hcf()funkciji posredujeta dve celi števili, shranjeni v spremenljivkah num1 in num2 . Funkcija izračuna HCF ti dve številki in jo vrne.
V funkciji najprej določimo manjše od obeh števil, saj je HCF lahko le manjše ali enako najmanjšemu številu. Nato z forzanko preidemo od 1 do te številke.
V vsaki ponovitvi preverimo, ali naše število popolnoma deli obe vhodni številki. V tem primeru shranimo številko kot HCF. Na koncu zanke dobimo največje število, ki popolnoma deli obe številki.
Zgornjo metodo je enostavno razumeti in uporabiti, vendar ni učinkovita. Veliko bolj učinkovita metoda za iskanje HCF je evklidski algoritem.
Evklidov algoritem
Ta algoritem temelji na dejstvu, da HCF dveh številk deli tudi njihovo razliko.
V tem algoritmu delimo večjega na manjšega in vzamemo preostanek. Zdaj delite manjše s tem preostankom. Ponavljajte, dokler ostanek ni 0.
Na primer, če želimo najti HCF 54 in 24, delimo 54 z 24. Preostanek je 6. Zdaj delimo 24 z 6, ostanek pa 0. Torej je 6 zahtevani HCF
Izvorna koda: Uporaba evklidskega 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)
Tukaj se vrtiva, dokler y ne postane nič. Stavek x, y = y, x % yne zamenja vrednosti v Pythonu. Kliknite tukaj, če želite izvedeti več o zamenjavi spremenljivk v Pythonu.
V vsako ponovitev hkrati postavimo vrednost y v x, preostanek pa (x % y)v y. Ko y postane nič, imamo HCF v x.
