In dit voorbeeld leer je de GCD van twee getallen te vinden met behulp van twee verschillende methoden: functie en lussen en, Euclidisch algoritme
Om dit voorbeeld te begrijpen, moet u kennis hebben van de volgende programmeeronderwerpen in Python:
- Python-functies
- Python-recursie
- Python-functieargumenten
De hoogste gemene deler (HCF) of grootste gemene deler (GCD) van twee getallen is het grootste positieve gehele getal dat de twee gegeven getallen perfect deelt. De HCF van 12 en 14 is bijvoorbeeld 2.
Broncode: loops gebruiken
# 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))
Uitvoer
De HCF is 6
Hier worden twee gehele getallen opgeslagen in variabelen num1 en num2 doorgegeven aan de compute_hcf()functie. De functie berekent de HCF deze twee getallen en geeft deze terug.
In de functie bepalen we eerst de kleinste van de twee getallen, aangezien de HCF alleen kleiner of gelijk kan zijn aan het kleinste getal. We gebruiken dan een forlus om van 1 naar dat nummer te gaan.
Bij elke iteratie controleren we of ons nummer beide invoergetallen perfect verdeelt. Als dit het geval is, slaan we het nummer op als HCF. Aan het einde van de lus krijgen we het grootste nummer dat beide nummers perfect verdeelt.
De bovenstaande methode is gemakkelijk te begrijpen en toe te passen, maar niet efficiënt. Een veel efficiëntere methode om de HCF te vinden is het Euclidische algoritme.
Euclidisch algoritme
Dit algoritme is gebaseerd op het feit dat HCF van twee getallen ook hun verschil verdeelt.
In dit algoritme delen we de grotere door kleinere en nemen we de rest. Verdeel nu de kleinere door deze rest. Herhaal totdat de rest 0 is.
Als we bijvoorbeeld de HCF van 54 en 24 willen vinden, delen we 54 door 24. De rest is 6. Nu delen we 24 door 6 en de rest is 0. Daarom is 6 de vereiste HCF
Broncode: met behulp van het Euclidische algoritme
# 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)
Hier herhalen we totdat y nul wordt. De instructie x, y = y, x % ywisselt waarden in Python uit. Klik hier voor meer informatie over het wisselen van variabelen in Python.
In elke iteratie plaatsen we de waarde van y in x en de rest (x % y)in y, gelijktijdig. Als y nul wordt, hebben we HCF in x.
