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

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