|
|
|
\require{AMSmath}
Reageren...
Re: Meetniveaus
ik moet voor wiskunde een som berekenen met het uitgebreid euclidisch algoritme. De getallen zijn: 404 en 284. Ik heb al een voorbeeldsom maar ik weet niet hoe het nou precies in elkaar zit en hoe ik het zelf dus moet toepassen:
voorbeeldsom:
202 = 1 · 202
142=1·142
60= 1·202 - 1·142
22=-2·202+3·142
16=5·202-7·142
6=-7·202+10·142
4=19·202-27·142
2=-26·202+37·142
0=71·202-101·142
ik hoop dat jullie mij kunnen helpen!
Antwoord
Op uitgebreid euclidisch algoritme kun je lezen:
Het uitgebreide algoritme van Euclides is een manier om een x en y te vinden in de vergelijking xa+yb=ggd(a,b)
waarbij de ggd de grootste gemene deler (g.g.d.) is van a en b. Dit is de uitgebreide versie op het eenvoudigere algoritme van Euclides.
Het algoritme gaat als volgt:
stap 1) Neem de variabelen x=v=1 en y=u=0
stap 2)Bepaal q en r in de vergelijking a=qb+r met 0 b r.
Vervang daarna (simultaan):
a door b, b door r
x door u en y door v
u door x-qu en v door y-qv
stap 3)Herhaal stap 2 totdat b gelijk is aan 0
De waardes x en y zijn nu zo dat ggd(a,b)=xa+yb.
De opdracht
"Bepaal q en r in de vergelijking a=qb+r met 0br." voer je het makkelijkst zo uit:
deel a door b, het gehele deel van de deling is q, de rest bij deling is r.
In onderstaande tabel heb ik dat eens in praktijk gebracht.
Op de eerste regel staan de namen van de variabelen.
Op de tweede regel staat de situatie als je stap 2 de eerste keer ingaat.
Op de volgende regels de situatie nadat je stap 2 weer een keer hebt uitgevoerd.
a b q r x y u v
202 142 - - 1 0 0 1
202 142 1 60 0 1 1 -1
142 60 2 22 1 -1 -2 3
60 22 2 16 -2 3 5 -7
22 16 1 6 5 -7 -7 10
16 6 2 4 -7 10 19 -27
6 4 1 2 19 -27 -26 37
4 2 2 0 -26 37 71 -101
Voor a=404 en b=284 krijg je dan:
a b q r x y u v
404 284 - - 1 0 0 1
404 284 1 120 0 1 1 -1
284 120 2 44 1 -1 -2 3
120 44 2 32 -2 3 5 -7
44 32 1 12 5 -7 -7 10
32 12 2 8 -7 10 19 -27
12 8 1 4 19 -27 -26 37
8 4 2 0 -26 37 71 -101
Gebruik dit formulier alleen om te reageren op de inhoud van de vraag en/of het
antwoord hierboven. Voor het stellen van nieuwe vragen kan je gebruik maken
van een vraag stellen in het menu aan de linker kant. Alvast bedankt!
|
