Programmeren met spreadsheets/Voorbeeld: KGV en GGD - Bewerkingsoverzicht

Eelco: /* Algoritme van Euclides voor de GGD */

2019-03-13T15:33:56Z

Algoritme van Euclides voor de GGD

← Oudere versie		Versie van 13 mrt 2019 15:33
Regel 5:		Regel 5:
	== Algoritme van Euclides voor de GGD ==		== 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.		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 = pN en b = qN. Als a > b, dan kunnen we (a-b) schrijven als (p-q)*N. Met andere woorden: ggd(a, b) = ggd(a-b, b).		We kunnen A en B schrijven als: A = pN en B = qN. 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(a,b).		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:

Eelco op 13 mrt 2019 om 15:30

2019-03-13T15:30:25Z

← Oudere versie		Versie van 13 mrt 2019 15:30
Regel 1:		Regel 1:
	Het algoritme van Euclides is een voorbeeld van het gebruik van conditionele expressies in spreadsheets. Een conditionele expressie heeft de vorm: <code>=IF(<cond>;<true-value>;<false-value>)</code>.		Het algoritme van Euclides is een voorbeeld van het gebruik van conditionele expressies in spreadsheets. Een conditionele expressie heeft de vorm: <code>=IF(<cond>;<true-value>;<false-value>)</code>.

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

	== Algoritme van Euclides voor de GGD ==		== Algoritme van Euclides voor de GGD ==

Eelco op 13 mrt 2019 om 15:28

2019-03-13T15:28:48Z

← Oudere versie		Versie van 13 mrt 2019 15:28
Regel 1:		Regel 1:
			Het algoritme van Euclides is een voorbeeld van het gebruik van conditionele expressies in spreadsheets. Een conditionele expressie heeft de vorm: <code>=IF(<cond>;<true-value>;<false-value>)</code>.

	== Algoritme van Euclides voor de GGD ==		== Algoritme van Euclides voor de GGD ==

Eelco: /* Algoritme van Euclides voor de GGD */

2019-03-13T15:25:45Z

Algoritme van Euclides voor de GGD

← Oudere versie		Versie van 13 mrt 2019 15:25
Regel 6:		Regel 6:

	De basisstap van het algoritme is:		De basisstap van het algoritme is:
	<~~code~~>		<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
	</~~code~~>		</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).

Eelco: 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...'

2019-03-13T15:24:21Z

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

Nieuwe pagina

== 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:
<code>
a, b := if a>b then a-b else a, if b>a then b-a else b
</code>
Deze stap herhaal je tot a=b: dan geldt a=b=ggd(a,b).

In een spreadsheet kunnen we dit schrijven als:

{| class="wikitable"
! !! 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).