Standardalgorithmen

Bild19Dieses Teilprogramm gibt Ihnen die Möglichkeit, einfache, standardisierte Algorithmen der Mathematik Schritt für Schritt nachzuvollziehen. Zu diesen unkomplizierten, u.a. für das Erstellen kleiner Computerprogramme wichtigen Algorithmen gehören:

  • Die Bestimmung des größten gemeinsamen Teilers nach Euklid
  • Die Bauernmultiplikation zweier natürlicher Zahlen
  • Die Berechnung der Fibonacci-Zahlenfolge
  • Das schnelle Berechnen einer Potenz
  • Die Transformation einer Dezimalzahl in ein anderes Zahlsystem

Wählen Sie zuerst in der Liste den gewünschten Algorithmus. Danach geben Sie die Grundgrößen, z.B. die zwei natürlichen Zahlen bei der ggT-Bestimmung oder die Nummer der gesuchten Fibonacci-Zahl, ein. Betätigen Sie nun wiederholt den Schalter Nächster Schritt, durchläuft das Programm schrittweise den Algorithmus. In der linken Hälfte des Fensters sehen sie den ausgeführten Einzelschritt, in der rechten Hälfte die Zwischenergebnisse.

ggT-Bestimmung nach Euklid
Zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen eignet sich besonders gut das von Euklid entwickelte Verfahren. Dieser Algorithmus findet sich im Kapitel 7 der „Elemente“, Satz 1-2. Ausgehend von der Tatsache, dass für zwei natürliche Zahlen m und n stets eine Darstellung der Form a = b q1 + r1 existiert, kann durch wiederholtes Zerlegen der Zahlen und Austausch der Zwischenergebnisse der größte gemeinsame Teiler von a und b ermittelt werden. Dabei wird: a = b q1 + r1, wobei dann r(n) der gesuchte größte gemeinsame Teiler ist.

Der Listeneintrag Euklid-Verfahren berechnet mit diesem Verfahren den größten gemeinsamen Teiler. Dabei können Sie schrittweise die Zwischenergebnisse verfolgen. Im linken Teil des Fensters finden Sie den Programmablaufplan, der in eine Computersprache umgesetzt werden könnte. Geben Sie zuerst unter X = und Y = die zwei zu untersuchenden Zahlen ein. Für eine optimale Darstellung sollten Sie maximal fünfstellige Zahlen benutzen. Betätigen Sie nun den Schalter Nächster Schritt, absolviert das Programm jeweils einen Schritt des Algorithmus, zeigt diesen links an und rechts die aktuellen Werte für die Variablen X, Y und R.

Bauernmultiplikation
a325Das Verfahren einer Multiplikation, ausschließlich durch Verdoppelungen und Halbierungen durchzuführen, war schon im alten Ägypten bekannt. Da es vor kurzer Zeit auch noch bei alltäglichen Rechnungen in Russland benutzt wurde, wird es russische Bauernmultiplikation genannt.

Fibonacci-Zahlen
Der hier genutzte Algorithmus zur Berechnung der Fibonacci-Zahlenfolge basiert auf deren impliziten Definition

F0 = 0; F1 = 1; Fn+2 = Fn + Fn+1

Weitere Erläuterungen hierzu finden Sie im Lexikon des Programms.

Schnelles Potenzieren
Ein besonders schnelles Verfahren zur Berechnung der Potenz einer natürlichen Zahl basiert auf einfacher Multiplikation und Division ohne Rest. Damit ist dieser Algorithmus gerade für Computerprogramme sehr effektiv, da schnell und einfach umzusetzen.

Zahltransformation
Erstaunlich häufig ist es notwendig, eine Dezimalzahl z in ein anderes Positionssystem der Basis b zu transformieren. Dazu wird im Allgemeinen in der Schule gelehrt, dass man eine Liste der Potenzen von b erstellt, um nun beginnend mit der größten Potenz von b, die noch kleiner ist als z, durch wiederholte Subtraktion eine Summe von Potenzen zu ermitteln, die gerade gleich z ist. Zum Beispiel würde die Zahl z = 430 wie folgt in das Dreiersystem transformiert: Dreierpotenzen 1 3 9 27 81 243 729 …

Subtraktion Potenz Exponent Ziffer
430 – 243 = 187 243 = 35 5 1
187 – 81 = 106 ; 106 – 81 = 25 81 = 34 4 2
27 ist größer als 25 27 = 33 3 0
25 – 9 = 16 ; 16 – 9 = 7 9 = 32 2 2
7 – 3 = 4 ; 4 – 3 = 1 3 = 31 1 2
1 – 1 = 0 1 = 30 0 1

Als Ziffernfolge im Dreiersystem ergibt sich damit 120221. So schön wie dieser Algorithmus aussieht, so unpraktisch, langsam und aufwendig ist er. Gerade die Berechnung der Potenzen der Basis ist mühevoll.
Viel eleganter ist der hier benutzte, auf dem Euklidischen Verfahren basierende Algorithmus. Da hier ausschließlich dividiert wird, erhält man sehr schnell das Gewünschte. Einziger Nachteil: Man erhält die Ziffern in umgekehrter Reihenfolge.