Šiame pavyzdyje jūs išmoksite rasti dviejų skaičių GCD naudodami du skirtingus metodus: funkciją ir kilpas bei Euklido algoritmą.
Norėdami suprasti šį pavyzdį, turite žinoti apie šias „Python“ programavimo temas:
- „Python“ funkcijos
- „Python“ rekursija
- „Python“ funkcijos argumentai
Didžiausias dviejų skaičių bendras faktorius (HCF) arba didžiausias bendrasis daliklis (GCD) yra didžiausias teigiamas sveikasis skaičius, kuris puikiai padalija du nurodytus skaičius. Pavyzdžiui, 12 ir 14 HCF yra 2.
Šaltinio kodas: naudojant kilpas
# 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))
Rezultatas
HCF yra 6
Čia compute_hcf()funkcijai perduodami du sveikieji skaičiai, saugomi kintamuosiuose num1 ir num2 . Funkcija apskaičiuoja HCF šiuos du skaičius ir grąžina jį.
Funkcijoje pirmiausia nustatome mažesnį iš dviejų skaičių, nes HCF gali būti mažesnis arba lygus mažiausiam skaičiui. Tada mes naudojame forkilpą nuo 1 iki šio skaičiaus.
Kiekvienoje iteracijoje patikriname, ar mūsų skaičius puikiai padalija abu įvesties skaičius. Jei taip, mes išsaugome skaičių kaip HCF. Baigę kilpą, gausime didžiausią skaičių, kuris puikiai padalija abu skaičius.
Pirmiau pateiktą metodą lengva suprasti ir įgyvendinti, bet jis nėra efektyvus. Daug efektyvesnis būdas rasti HCF yra Euklido algoritmas.
Euklido algoritmas
Šis algoritmas pagrįstas tuo, kad dviejų skaičių HCF padalija ir jų skirtumą.
Šiame algoritme didesnį dalijame iš mažesnio, o likutį imame. Dabar padalykite mažesnę iš šios likutinės dalies. Kartokite tol, kol likusi dalis bus 0.
Pvz., Jei norime rasti HCF iš 54 ir 24, padalijame 54 iš 24. Likutis yra 6. Dabar mes padalijame 24 iš 6, o likusi dalis yra 0. Taigi 6 yra reikalingas HCF
Šaltinio kodas: naudojant Euklido algoritmą
# 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)
Čia mes kilpą, kol y tampa nulis. Pareiškimas x, y = y, x % ypakeičia reikšmes „Python“. Spustelėkite čia, jei norite sužinoti daugiau apie kintamųjų keitimą „Python“.
Kiekvienoje iteracijoje y vertę dedame į x, o likusią dalį (x % y)į y, tuo pačiu metu. Kai y tampa nulis, mes turime HCF x.
