I det här exemplet lär du dig att hitta GCD för två siffror med två olika metoder: funktion och loopar och euklidisk algoritm
För att förstå detta exempel bör du ha kunskap om följande Python-programmeringsämnen:
- Python-funktioner
- Python-rekursion
- Argument för Python-funktion
Den högsta gemensamma faktorn (HCF) eller den största gemensamma delaren (GCD) av två tal är det största positiva heltalet som perfekt delar de två angivna siffrorna. Exempelvis är HCF 12 och 14 2.
Källkod: Använda loopar
# 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))
Produktion
HCF är 6
Här skickas två heltal som lagras i variablerna num1 och num2 till compute_hcf()funktionen. Funktionen beräknar HCF dessa två siffror och returnerar den.
I funktionen bestämmer vi först det minsta av de två siffrorna eftersom HCF bara kan vara mindre än eller lika med det minsta antalet. Vi använder sedan en forslinga för att gå från 1 till det numret.
I varje iteration kontrollerar vi om vårt nummer delar båda ingångsnumren perfekt. I så fall lagrar vi numret som HCF. När slingan är klar slutar vi med det största numret som perfekt delar upp båda siffrorna.
Ovanstående metod är lätt att förstå och implementera men inte effektiv. En mycket effektivare metod för att hitta HCF är den euklidiska algoritmen.
Euklidisk algoritm
Denna algoritm baseras på det faktum att HCF med två siffror delar upp skillnaden också.
I denna algoritm delar vi större med mindre och tar resten. Dela nu den mindre med den här återstoden. Upprepa tills resten är 0.
Om vi till exempel vill hitta HCF på 54 och 24 delar vi 54 med 24. Resten är 6. Nu delar vi 24 med 6 och resten är 0. Därför är 6 den erforderliga HCF
Källkod: Använd den euklidiska algoritmen
# 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)
Här slingrar vi tills y blir noll. Uttalandet x, y = y, x % ybyter värden i Python. Klicka här för att lära dig mer om att byta variabler i Python.
I varje iteration placerar vi värdet på y i x och resten (x % y)i y samtidigt. När y blir noll har vi HCF i x.
