👀 Voorbeeld - Algoritme van Euclides

De volgende functie berekent de grootste gemene deler van twee getallen a en b. De grootste gemene deler (ggd) is het grootste getal waardoor beide getallen deelbaar zijn. Bijvoorbeeld, de ggd van 14 en 35 is 7 (want 7 × 2 = 14 en 7 × 5 = 35).

def ggd(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a

Bestudeer deze functie nauwkeurig en probeer ze eens uit in de sandbox. Deze functie past een gekend stappenplan toe: het algoritme van Euclides. Euclides van Alexandrië had het inzicht dat de grootste gemene deler van twee getallen niet verschilt wanneer de getallen van elkaar worden afgetrokken.

🧐 Wist je dat…

het algoritme van Euclides vele toepassingen kent in de wiskunde? Zo wordt het gebruikt om de hoofdstelling van de rekenkunde aan te tonen of om vergelijkingen op te lossen met meerdere onbekenden (diofantische vergelijkingen). Maar er bestaan ook meer praktische toepassingen van het algoritme van Euclides. Het wordt gebruikt om muzikale ritmes te genereren en in het gekende RSA-algoritme dat zorgt voor encryptie.

❓ Vraag

Wat is een algoritme en hoe kan je het gebruiken?

💻 Programmeeroefening - Algoritme van Euclides

Kopieer en plak het algoritme van Euclides in de editor hieronder om dit onderdeel af te ronden.