Vraagstelling Bepaal de grootste gemeenschappelijke deler uit a en b. a>=1 en b>=1 Strategie De constanten a en b vervangen we door variabelen x en y en we passen de volgende regels toe: 1. x == y => GGD(x,y) = x 2. x > y => GGD(x,y) = GGD(x-y,y) 3. x < y => GGD(x,y) = GGD(x,y-x) Formele probleemspecificatie pre:a>=1 ^ b>=1 post:ggd=(Maxi:1<=i<=min(a,b) ^ a%i==0 ^ b%i==0:i) * Eindrelatie R: GGD(a,b)=ggd(p,q) ^ q=p ^ ggd = p * Invariant GGD(a,b)=ggd(p,q) ^ ggd = p * Stopcriterium q!=p Initialisatie p=a; q=b; ggd=a; Stap richting stopcriterium p > q => p = p - q ^ p < q => q = q - p Actie herstel invariant ggd = p; // hoeft alleen als p is gewijzigd. Algoritme public int ggd(int a, int b){ p=a; q=b; ggd=a; while(p!=q){ if(p > q){ p = p - q; ggd = p; } else{ q = q - p; } } return ggd; }