Programmeren met spreadsheets/Voorbeeld: KGV en GGD

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).