Euklids Algoritme beregner den største fælles divisor af to positive heltal, n og p. Algoritmen er baseret på følgende tre observationer:
1. Hvis n er lig med p, så er største fælles divisor af n og p lig med n.
2. Hvis n er større end p, så er største fælles divisor af n og p lig med største fælles divisor af tallene n - p og p.
3. Hvis p er større end n, så er største fælles divisor af n og p lig med største fælles divisor af tallene n og p - n.
a) Skriv et iterativt program der vha. en while-løkke beregner den største fælles divisor af to positive heltal.
Hint: Gem tallene i to heltalsvariable, x og y, som manipuleres på passende vis ved hvert gennemløb af while-løkken.
b) Argumenter for at programmet ovenfor altid standser med det rigtige resultat.
Hint 1: Argumenter omhyggeligt for, at hvis variablene x og y begge er positive før et gennemløb af while-løkken, så er de også begge positive efter gennemløbet.
Hint 2: Argumenter omhyggeligt for, at hvis x og y før et gennemløb begge er positive, så er summen af x og y efter gennemløbet strengt mindre end den var før gennemløbet.
Argumenterne i Hint 1 og Hint 2 giver tilsammen anledning til at konkludere, at programmet altid standser. Forklar hvorfor.
Hint 3: Argumenter omhyggeligt for, at hvis x og y før et gennemløb begge er positive, så er største fælles divisor af x og y før gennemløbet lig med største fælles divisor af x og y efter gennemløbet.
Argumenterne i Hint 1 og Hint 3 giver tilsammen anledning til at konkludere, at hvis programmet standser, så standser det med det rigtige resultat. Forklar hvorfor.
Se evt. side 267 - 270 i CCJ3 (265 - 267 i JC) hvor et lignende argument er beskrevet i detaljer.