Voorbereiding

Bekijk de video over test-driven development¹ om te leren werken met doctests. Hierdoor zal je de laatste twee statements begrijpen in het skelet van de broncode dat wordt meegegeven met deze opgave.

Opgave

We hebben hieronder reeds het skelet opgemaakt voor de oplossing van deze opgave. Je taak bestaat erin om de functies ggd en kgv te implementeren, zodat ze respectievelijk de grootste gemene deler en het kleinste gemene veelvoud van de natuurlijke getallen $$a$$ en $$b$$ teruggeven. De grootste gemene deler is het grootste natuurlijke getal dat zowel een deler is van $$a$$ als van $$b$$. Het kleinste gemene veelvoud is het kleinste natuurlijke getal dat zowel een veelvoud is van $$a$$ als van $$b$$.

def ggd(a, b):
    
    """
    Berekent de grootste gemene deler van de twee 
    natuurlijke getallen a en b.
    
    >>> ggd(252, 105)
    21
    >>> ggd(48, 18)
    6
    """
    
    # berekening grootste gemene deler op basis van
    # het algoritme van Euclides

def kgv(a, b):
    
    """
    Berekent het kleinste gemene veelvoud van de
    twee natuurlijke getallen a en b.

    >>> kgv(252, 105)
    1260
    >>> kgv(48, 18)
    144
    """
    
    # berekening kleinste gemene veelvoud

if __name__ == '__main__':
    import doctest
    doctest.testmod()

De fractions module uit de Python Standard Library² bevat een functie gcd die de grootste gemene deler van twee natuurlijke getallen teruggeeft. Voor deze opgave mag je de fractions module echter niet gebruiken, en is het de bedoeling dat je grootste gemene deler zelf berekent. Baseer je implementatie van de functie ggd op het algoritme van Euclides. Het algoritme start met een paar natuurlijke getallen, en vormt daarmee een nieuw paar dat bestaat uit het kleinste van de twee getallen, en het verschil tussen het grootste en het kleinste getal. Deze procedure herhaalt zich totdat het paar bestaat uit twee gelijke getallen. Dat getal is de grootste gemene deler van het oorspronkelijke paar natuurlijke getallen.

Het basisprincipe dat hierbij gehanteerd wordt, is dat de grootste gemene deler niet verandert als het grootste getal van het kleinste afgetrokken wordt. Zo is de grootste gemene deler van 252 en 105 ook de grootste gemene deler van 147 (= 252 - 105) en 105. Aangezien grootste getal verlaagd wordt, resulteert het herhaald uitvoeren van deze procedure in steeds kleinere getallen, zodat de herhaling vroeger of later zal stoppen wanneer de twee getallen gelijk zijn (als de procedure daarna nog een keer zou herhaald worden, dan zou één van beide getallen nul worden).

Het kleinste gemene veelvoud van twee natuurlijke getallen $$a$$ en $$b$$ kan bepaald worden als het product van beide getallen, gedeeld door hun grootste gemene deler.

Voorbeeld

>>> ggd(252, 105)
21
>>> ggd(48, 18)
6

>>> kgv(252, 105)
1260
>>> kgv(48, 18)
144