Grup­pe 1: das „echte“ Ver­fah­ren von Eu­klid

Eu­klid hat in sei­nem Werk „Die Ele­men­te“ selbst sei­nen Al­go­rith­mus geo­me­trisch vor­ge­stellt. Er ging dabei von zwei Stre­cken (AB und CD) aus, die un­ter­schied­lich lang sind und in mög­lichst große, gleich lange Teile un­ter­teilt wer­den sol­len (be­ach­te: gleich lang, nicht gleich viele!). Im Wort­laut liest sich das so:

„Wenn CD aber AB nicht misst und man bei AB, CD ab­wech­selnd immer das Klei­ne­re vom Grö­ße­ren weg­nimmt, dann muss eine Zahl übrig blei­ben, wel­che die vor­an­ge­hen­de misst.“

An­schau­lich kann man das an­statt mit Stre­cken auch mit Stä­ben ma­chen, zum Bei­spiel den fol­gen­den bei­den:

Schritt 1:

Man nimmt vom grö­ße­ren (obe­ren) Stab ein­mal die Länge des klei­ne­ren Sta­bes weg und legt den Rest wie­der bün­dig neben den klei­ne­ren Stab:

Schritt 2:

Man führt Schritt 1 er­neut durch. Damit fährt man fort, bis die bei­den ne­ben­ein­an­der lie­gen­den Stäbe gleich lang sind.

Der Eu­kli­di­sche Al­go­rith­mus: Her­un­ter­la­den [odt][466 KB]

Der Eu­kli­di­sche Al­go­rith­mus: Her­un­ter­la­den [pdf][857 KB]

Wei­ter zu Grup­pe 2