Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


2. Pascal



Beispiel: Euklidischer Algorithmus

Zu Beginn wollen wir ein Pascal-Programm zur Lösung eines klassischen elementaren Problems betrachten: »Kürzen eines gegebenen Bruchs auf seine reduzierte Form«. Wir wollen 2/3 schreiben anstatt 4/6, 200/300 oder 178468/267702. Die Lösung dieses Problems ist äquivalent zur Bestimmung des Größter gemeinsamer Teilers (= gcd - greatest common divisor) von Zähler und Nenner, d.h. der größten ganzen Zahl, durch welche Zähler und Nenner teilbar sind. Ein Bruch wird in seine reduzierte Form umgewandelt, indem man sowohl Zähler als auch Nenner durch ihren größten gemeinsamen Teiler dividiert. Ein effizientes Verfahren zur Bestimmung des größten gemeinsamen Teilers wurde im alten Griechenland vor über zweitausend Jahren entdeckt. Es wird Euklidischer Algorithmus genannt, da es in Euklids berühmtem Werk Elemente ausführlich beschrieben wird.

Das Euklidische Verfahren beruht auf der Tatsache, daß, wenn u größer als v ist, der größte gemeinsame Teiler von u und v gleich dem größten gemeinsamen Teiler von v und u - v ist. Diese Erkenntnis führt zu der folgenden Implementierung in Pascal:

    program euclid(input,output);
      var x,y: integer;
    function gcd(u,v: integer): integer;
      var t: integer;
      begin
      repeat
        if u<v then 
          begin t:=u; u:=v; v:=t end;
        u:=u-v
      until u=0;
      gcd:=v
      end;
    begin
    while not eof do
      begin
      readln(x,y);
      if (x>0) and (y>0) then writeln(x,y,gcd(x,y))
      end;
    end.

Betrachten wir zunächst die Spracheigenschaften, die aus diesem Programm ersichtlich sind. Pascal besitzt die Syntax einer höheren Programmiersprache und ermöglicht dadurch eine leichte Identifizierung der Hauptmerkmale des Programms. Die Variablen (var) und Funktionen (function), die vom Programm verwendet werden, werden zuerst deklariert, danach folgt der Rumpf des Programms (Anweisungsteil). (Andere, im obigen Programm nicht verwendete Hauptteile eines Programms, die vor dem Programmrumpf deklariert werden, sind Konstanten (const) und Typen (type).) Funktionen besitzen das gleiche Format wie das Hauptprogramm, nur daß sie einen Wert liefern, der gesetzt wird, indem dem Funktionsnamen innerhalb des Rumpfs der Funktion ein Wert zugewiesen wird. (Die Funktion (function) ist ein Typ eines »Unterprogramms« in Pascal; der andere Typ, dessen Ausführung kein Resultat liefert, ist die Prozedur (procedure).) Die Standardfunktion readln liest eine Zeile der Eingabe ein und weist die gefundenen Werte den als Argumenten angegebenen Variablen zu; writeln funktioniert ähnlich. Ein internes Standardprädikat, eof, wird auf wahr (true) gesetzt, wenn keine Eingabewerte mehr vorhanden sind. (Ein- und Ausgabe innerhalb einer Zeile sind mit read, write und eoln möglich.) Die Deklaration von input und output im Programmkopf gibt an, daß das Programm die »standardmäßigen« Eingabe- und Ausgabeströme verwendet.

Der Anweisungsteil des obigen Programms ist sehr einfach: Bei der Eingabe werden Zahlenpaare eingelesen, und wenn beide positiv sind, werden sie und ihr größter gemeinsamer Teiler ausgegeben. (Was würde passieren, wenn gcd mit einem Wert von u oder v aufgerufen würde, der negativ oder gleich Null ist?)

Die Funktion gcd realisiert den Euklidischen Algorithmus selbst: Das Programm ist eine Schleife, die zunächst gewährleistet, daß u >= v ist, indem die Werte gegebenenfalls ausgetauscht werden, und in der dann u durch u-v ersetzt wird. Der größte gemeinsame Teiler der Variablen u und v stimmt stets mit dem größten gemeinsamen Teiler der ursprünglichen Werte überein, mit denen das Verfahren begonnen wurde; schließlich endet der Prozeß mit u = v, wobei beide Werte gleich dem größten gemeinsamen Teiler der ursprünglichen Werte (und aller Zwischenwerte) von u und v sind.

Dieses Beispiel wurde als ein vollständiges Pascal-Programm geschrieben, welches der Leser benutzen könnte, um sich mit einem bestimmten Pascal-Programmiersystem vertraut zu machen. Der »Treiber«-Teil des Programms liest Zahlenpaare ein und gibt sie dann zusammen mit ihrem größten gemeinsamen Teiler aus. Dieses Beispiel wurde aufgenommen, um zu zeigen, wie der Algorithmus ausgeführt werden könnte, und um die Tatsache zu unterstreichen, daß man die Algorithmen im vorliegenden Buch am besten versteht, wenn man sie implementiert und anhand von einigen beispielhaften Eingabewerten ablaufen läßt. In Abhängigkeit von der Qualität der verfügbaren Programmierumgebung hat der Leser möglicherweise den Wunsch, die Programme weiter zu entwickeln, um sie besser anwenden zu können. Zum Beispiel sind im obigen Programm die Zwischenwerte von Interesse, die von u und v in der repeat-Schleife angenommen werden.

Obwohl der Gegenstand des vorliegenden Abschnittes die Sprache und nicht der Algorithmus ist, müssen wir dem klassischen Euklidischen Algorithmus Gerechtigkeit widerfahren lassen: Die obenstehende Implementierung läßt sich verbessern, indem wir, wenn u > v gilt, so lange Vielfache von v von u subtrahieren, bis eine Zahl erreicht wird, die kleiner als v ist. Diese Zahl wiederum ist genau gleich dem Rest, der bei der Division von u durch v bleibt und durch die Funktion mod berechnet wird: Der größte gemeinsame Teiler von u und v ist gleich dem größten gemeinsamen Teiler von v und u mod v. Zum Beispiel hat der größte gemeinsame Teiler von 461952 und 116298 den Wert 18, wie aus der Folge

461952, 116298, 113058, 3240, 2898, 342, 162, 18

ersichtlich ist. (Jedes Element dieser Folge ist gleich dem Rest, der bei der Division der beiden vorangehenden Elemente bleibt.) Der Leser möchte vielleicht die obige Implementierung unter Verwendung des Operators mod modifizieren und ermitteln, um wieviel effizienter diese Modifikation ist, wenn beispielsweise der größte gemeinsame Teiler einer sehr großen Zahl und einer sehr kleinen Zahl bestimmt werden soll. Es erweist sich, daß dieser Algorithmus immer mit einer relativ kleinen Anzahl von Schritten auskommt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]