Wir nutzen aus, daß wir die Faktoren in aufsteigender Reihenfolge bestimmen; dann wissen wir also zwischendurch, daß kleinere Teiler als der gerade getestete nicht vorkommen können. Wir definieren dazu eine Routine "Zerlege2(n,t)", welche die Zerlegung von n in Faktoren liefert, wobei n keine Teiler kleiner als t hat. Diese Routine verwenden wir nur intern und nehmen sie nicht in die Schnittstelle auf (das wäre wohl möglich, aber vermutlich braucht sie sonst niemand).
Das Ganze wird durch das folgende Modul geleistet:
IMPLEMENTATION MODULE Zahlen;
(* Modul zur Faktorisierung natuerlicher Zahlen *)
(* zweite, rekursive Version *)
(* Vorlesung EI1 WS 1999/2000 *)
(* Klaus Lagally, 09.11.1999 *)
FROM InOut IMPORT WriteCard, WriteString, WriteLn;
PROCEDURE Zerlege(n: CARDINAL);
(* bestimme die Primfaktorzerlegung der Zahl n *)
(* und gib sie in der Form n = f1*f2*...*fk aus *)
(* suche und drucke aufsteigend alle Teiler von n *)
BEGIN WriteCard(n,1); WriteString(* = *);
Zerlege2(n, 2) (* noch sind alle Teiler > 1 moeglich *)
END Zerlege;
PROCEDURE Zerlege2(n, t: CARDINAL);
(* liefert Zerlegung von n, wenn kein Teiler < t existiert *)
(* Vorbedingung: t > 1 *)
BEGIN IF t >= n
THEN (* n kann nicht weiter zerlegt werden *)
WriteCard(n,1); WriteLn
ELSIF (n MOD t) = 0
THEN (* Teiler t gefunden *)
WriteCard(t,1); WriteString(" * ");
Zerlege2(n DIV t, t) (* liefert die restliche Zerlegung *)
ELSE (* t ist nicht Teiler *)
Zerlege2(n, t+1) (* zerlege: kein Teiler < t+1 existiert *)
END
END Zerlege2;
END Zahlen.
Daß die Teilprobleme richtig zusammenspielen, "sieht man";
wie sieht es aber mit der Terminierung aus,
und was ist ein sinnvolles Größenmaß
für die Instanz(n,t)
in der Problemklasse von "Zerlege2"?
Es zeigt sich, daß "n-t", die Differenz der Argumente, das Gewünschte leistet: es nimmt bei den beiden rekursiven Anwendungen von "Zerlege2" jedesmal echt ab, und wenn es <= 0 ist, lösen wir das Problem direkt (und richtig). Unsere Lösung ist also korrekt.