Het algoritme van Euclides
Hoe kan ik de correctheid van het algoritme van Euclides beargumenteren, vooral de invoer dat a $>$ b $>$ 0 is (voorwaarden voldoet) en de uitvoer g = ggd (a , b) idd de grootste gemeenschappelijke deler is.
Alvast bedankt!
Bra
Student hbo - zondag 14 februari 2021
Antwoord
Je moet drie dingen bewijzen:- het stopt (dat volgt omdat je een strikt dalende rij natuurlijke getallen maakt)
- het resultaat, $d$, deelt $a$ en $b$, dat doe je door terug te lopen door de rij resten: $d$ deelt ze allemaal, en dus ook $a$ en $b$
- elke gemeenschappelijke deler van $a$ en $b$ deelt alle resten, en dus ook het resultaat.
Zie Proof of validity
kphart
zondag 14 februari 2021
©2001-2024 WisFaq
|