 |
#include <stdio.h>
/* Groesster gemeinsamer Teiler */
int a, b;
void main(void)
{
scanf("%d %d", &a, &b); /* Eingabe */
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
}
printf("GGT: %d\n",a); /* Ausgabe GGT = a = b */
}
Die Anweisung A lautet
a = a - b wenn a > b
b = b - a wenn b > a
und die Bedingung B heißt a = b. Dabei sind a und b natürliche Zahlen, mit
Anfangswerten a > O, b > O und a != b. Eine zweckmäßige Wahl von
N ist N = max(a,b).
Der Effekt von A auf N muß in zwei gesonderten Fällen betrachtet werden. Ist a > b,
so bleibt b unverändert, und der Wert von a wird um b erniedrigt. Da anfänglich
a > O, b > O und a != b, bleiben die ersten Beziehungen erhalten, und N nimmt ab.
Ist b > a, so bleibt a unverändert, b = max(a,b) = N nimmt um den Betrag a ab, und
die Beziehungen a > 0 und b > 0 bleiben erhalten. Da also N = max(a,b) stets
abnimmt, anderseits aber min(a,b) positev bleibt, muß nach einer endlichen Anzahl
von Durchläufen max(a,b) = min(a,b) werden, also a != b nicht mehr erfüllt sein.
Damit ist die Endlichkeit dieses Programms erwiesen.
|
|
|
DIENSTE
