Ebben a példában megtanulják megtalálni két szám GCD-jét két különböző módszer segítségével: függvény és hurkok, valamint euklideszi algoritmus
A példa megértéséhez ismernie kell a következő Python programozási témákat:
- Python függvények
- Python rekurzió
- Python Function Arguments
Két szám legmagasabb közös tényezője (HCF) vagy legnagyobb közös osztója (GCD) a legnagyobb pozitív egész szám, amely tökéletesen elosztja a két megadott számot. Például a 12 és 14 HCF értéke 2.
Forráskód: Hurkok használata
# 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))
Kimenet
A HCF értéke 6
Itt a num1 és a num2 változóban tárolt két egész számot továbbítják a compute_hcf()függvénynek. A függvény kiszámítja a HCF ezt a két számot, és visszaadja.
A függvényben először meghatározzuk a két szám közül a kisebbet, mivel a HCF csak kisebb vagy egyenlő lehet a legkisebb számmal. Ezután egy forhurok segítségével léphetünk 1-ről erre a számra.
Minden iterációban ellenőrizzük, hogy számunk tökéletesen elosztja-e mindkét bemeneti számot. Ha igen, akkor a számot HCF-ként tároljuk. A ciklus befejezésekor a legnagyobb számra jutunk, amely tökéletesen elosztja mindkét számot.
A fenti módszer könnyen érthető és megvalósítható, de nem hatékony. Sokkal hatékonyabb módszer a HCF megtalálásához az euklideszi algoritmus.
Euklideszi algoritmus
Ez az algoritmus azon a tényen alapul, hogy két szám HCF-je elosztja a különbségüket is.
Ebben az algoritmusban elosztjuk a nagyobbat kisebbel, és a maradékot vesszük. Most ossza el a kisebbet ezzel a maradékkal. Addig ismételje, amíg a maradék értéke 0 nem lesz.
Például, ha meg akarjuk találni az 54-es és a 24-es HCF-et, akkor az 54-et elosztjuk 24-vel. A fennmaradó rész 6. Most a 24-et 6-ra osztjuk, a maradék pedig 0. Ezért a 6 a szükséges HCF
Forráskód: Az euklideszi algoritmus használata
# 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)
Itt addig ciklálunk, amíg y nulla lesz. Az utasítás x, y = y, x % ykicseréli az értékeket a Pythonban. Kattintson ide, ha többet szeretne megtudni a változók cseréjéről a Pythonban.
Minden iterációban y értékét (x % y)egyszerre helyezzük x-be, a maradékot pedig y-be. Amikor y nulla lesz, akkor HCF-je van x-ben.
