Programmeren met spreadsheets/Voorbeeld: KGV en GGD

Uit Lab
Naar navigatie springen Naar zoeken springen
De printervriendelijke versie wordt niet langer ondersteund en kan weergavefouten bevatten. Werk uw browserbladwijzers bij en gebruik de gewone afdrukfunctie van de browser.

Het algoritme van Euclides is een voorbeeld van het gebruik van conditionele expressies in spreadsheets. Een conditionele expressie heeft de vorm: =IF(<cond>;<true-value>;<false-value>).

Voorbeeld: het maximum van A1 en B1: =IF(A1>=B1; A1; B1)

Algoritme van Euclides voor de GGD

De grootste gemene deler van twee getallen A en B, ggd(A,B), is het grootste getal N waarvoor geldt: A mod N = 0 en B mod N = 0. We kunnen A en B schrijven als: A = p*N en B = q*N. Als A > B, dan kunnen we (A-B) schrijven als (p-q)*N. Met andere woorden: ggd(A, B) = ggd(A-B, B). Dit is het principe van het algoritme van Euclides (https://nl.wikipedia.org/wiki/Algoritme_van_Euclides). We gebruiken twee variabelen a en b, met als beginwaarden a=A en b=B.

De basisstap van het algoritme is:

  a, b := if a>b then a-b else a, if b>a then b-a else b

Deze stap herhaal je tot a=b: dan geldt a=b=ggd(A,B).

In een spreadsheet kunnen we dit schrijven als:

A B
1 12961 10967
2 =IF(A1>B1; A1-B1; A1) =IF(B1>A1; B1-A1; B1)
... ... ...

Opdracht: bepaal ggd(12961, 10967) en ggd(12961, 10978).