Algorithmik - delphi-lernen.de

Der Algorithmusbegriff - Was ist ein Algorithmus?

Ein Algorithmus ist grob gesagt ein Schema, nach dem man vorgehen muss um ein bestimmtes Problem zu lösen. Also ein (Koch-)Rezept was zu tun ist, bis man den Kuchen fertig hat. Die Zutaten dabei sind aber immer programmiertechnische Wörter. Also mit der Sprache Delphi wird der Algorithmus genau formalisiert. Im Fortgeschrittenen-Bereich wird auf Rekursive Funktionen eingegangen. Dies sind meistens die einfachsten Algorithmen. Der bekannteste ist hierbei wohl ohne Zweifel Quicksort.

Ein eigentlich einfacher Algorithmus ist z.B. der Euklidsche Algorithmus zur Berechnung des größten gemeinsamen Teilers von zwei Zahlen z1 und z2. Diesen hat der griechische Mathematiker Euklid etwa 300 v. Chr. in seinem Werke "Die Elemente" veröffentlicht.

Hier der Delphi-Quelltext:

	
function ggT( z1, z2 : Integer) : Integer;

begin

  while z2 <> 0 do

  begin

    if z1 > z2 then

      z1 := z1-z2

    else

      z2 := z2-z1;

  end;

  result := z1;

end;

Dieser Algorithmus scheint auf den ersten Blick nicht wirklich trivial zu sein, aber rechnen wir doch mal ein Beispiel durch, um zu sehen, ob er tatsächlich funktioniert:

Gesucht ist der ggT von z1:=54 und z2:=42;

z2=42<>0 stimmt
somit erster Durchlauf:
z1>z2 stimmt
=> z1:=z1-z2=54-42=12
erster Durchlauf endet.

z2=42<>0 stimmt
zweiter Durchlauf:
z1>z2 stimmt nicht
=> z2:=z2-z1=42-12=30
zweiter Durchlauf endet.

z2=30<>0 stimmt
dritter Durchlauf:
z1>z2 stimmt nicht
=> z2:=z2-z1=30-12=18
dritter Durchlauf endet.

z2=18<>0 stimmt
vierter Durchlauf: z1>z2 stimmt nicht
=> z2:=z2-z1=18-12=6
vierter Durchlauf endet.

z2=6<>0 stimmt
fünfter Durchlauf: z1>z2 stimmt
=> z1:=z1-z2=12-6=6
fünfter Durchlauf endet.

z2=6<>0 stimmt
sechster Durchlauf:
z1>z2 stimmt nicht
=> z2:=z2-z1=6-6=0
sechster Durchlauf endet.

s2=0<>0 stimmt nicht, while-Schleife wird abgebrochen
=> z1=6 wird als Resultat zurückgegeben
=> der größte gemeinsame Teiler von 54 und 42 ist 6.

Wer sich hier eine weitere Erklärung wünscht, darf mir gerne via SocialMedia oder Mail schreiben. Das bewerte ich dann als "upvote" und investiere hier auch gerne noch mehr Zeit für euch ;)