Programmeren met spreadsheets/Voorbeeld: KGV en GGD: verschil tussen versies
Geen bewerkingssamenvatting |
|||
| Regel 5: | Regel 5: | ||
== Algoritme van Euclides voor de GGD == | == Algoritme van Euclides voor de GGD == | ||
De grootste gemene deler van twee getallen | 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 | 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). | 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: | De basisstap van het algoritme is: | ||
| Regel 13: | Regel 14: | ||
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> | </syntaxhighlight> | ||
Deze stap herhaal je tot a=b: dan geldt a=b=ggd( | Deze stap herhaal je tot a=b: dan geldt a=b=ggd(A,B). | ||
In een spreadsheet kunnen we dit schrijven als: | In een spreadsheet kunnen we dit schrijven als: | ||
Huidige versie van 13 mrt 2019 om 15:33
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).