Programmeren met spreadsheets/Voorbeeld: KGV en GGD: verschil tussen versies
Naar navigatie springen
Naar zoeken springen
(Nieuwe pagina aangemaakt met '== 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...') |
|||
| Regel 6: | Regel 6: | ||
De basisstap van het algoritme is: | De basisstap van het algoritme is: | ||
< | <syntaxhighlight lang=pascal> | ||
a, b := if a>b then a-b else a, if b>a then b-a else b | a, b := if a>b then a-b else a, if b>a then b-a else b | ||
</ | </syntaxhighlight> | ||
Deze stap herhaal je tot a=b: dan geldt a=b=ggd(a,b). | Deze stap herhaal je tot a=b: dan geldt a=b=ggd(a,b). | ||
Versie van 13 mrt 2019 15:25
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).