Elementare Algorithmen Algorithmus zur Addition und Subtraktion von mehrstelligen Zahlen

Ein Algorithmus ist eine ist eine Schritt-für-Schritt-Anleitung für einen bestimmten Vorgang. Ein wichtiges Kennzeichen eines Algorithmus ist, dass die Schritte so eindeutig und detailliert angegeben sind, dass sie von demjenigen, der den Algorithmus ausführen soll, unmittelbar umgesetzt werden können. Wir bezeichnen diese Schritte als Elementar­operationen des Algorithmus.

Ein Algorithmus, den wir in der Schule schon sehr früh lernen, ist das schriftliche Addieren von zwei mehr­stelligen Zahlen. Im Folgenden ist dieser Algorithmus in programmier­sprachlicher Notation dargestellt, und im Anschluss daran sind die verwendeten Elementar­operationen angegeben, die ein Mensch oder eine Maschine können muss, um den Algorithmus auszuführen.

Die schriftliche Subtraktion, wie wir sie in der Schule lernen, lässt sich in ähnlicher Weise formulieren (Aufgabe).

Tatsächlich lässt sich die Subtraktion einer Zahl jedoch auch noch in ganz anderer Weise realisieren, nämlich durch Addition des Komplements der Zahl. Dieser Algorithmus ist besonders für das Rechnen im Binärsystem geeignet, weil dort die Komplement­bildung sehr einfach ist. Daher findet dieser Subtraktions­algorithmus in der Computer­arithmetik Verwendung.

Die Algorithmen funktionieren auch mit Zahlen, die in einem Stellen­wert­system mit anderer Basis B als 10 dargestellt sind (die in den Algorithmen vorkommenden Zahlen 10 bzw. 9 müssen dann durch B bzw. B-1 ersetzt werden).

 

Addition

Die Schulmethode der Addition zweier nicht­negativer ganzer Zahlen lässt sich durch folgenden Algorithmus beschreiben. Voraus­gesetzt sei hier, dass beide Zahlen die gleiche feste Länge n haben. Dies lässt sich gegebenen­falls durch Anfügen von führenden Nullen erreichen. Auch das Ergebnis soll die Länge n haben, anderenfalls ist der zulässige Zahlen­bereich über­schritten und es wird ein Fehler gemeldet.

Es wird eine Variable übertrag_vorhanden verwendet, die true oder false als Wert annehmen kann (einen Wahrheits­wert). Durch übertrag_vorhanden wird angezeigt, ob noch ein Übertrag aus der vorherigen Stelle zu berück­sichtigen ist.

 

Algorithmus Addition
Eingabe:	Zwei nichtnegative ganze Zahlen a = an-1 ... a0 und b = bn-1 ... b0 in Dezimaldarstellung
Ausgabe:	Summe s = a + b in Dezimaldarstellung
Methode:	Initialisierung setze übertrag_vorhanden = false Iteration für i = 0 bis n-1 wiederhole setze x = ai + bi wenn übertrag_vorhanden dann erhöhe x um 1 setze übertrag_vorhanden = false wenn x10 dann setze x = x – 10 setze übertrag_vorhanden = true setze si = x Finalisierung wenn übertrag_vorhanden dann Fehler: "Zulässiger Zahlenbereich überschritten"

 

Als Elementar­operationen werden benötigt: Addition zweier Ziffern, Weiterzählen um 1, Vergleich mit 10 sowie Subtraktion von 10.

Subtraktion

Subtraktion durch Komplementbildung

Die Subtraktion einer Zahl b lässt sich auch durch Addition des Komplementes von b realisieren. Das Komplement von b ergibt sich durch Ergänzen jeder seiner Ziffern zu 9. Beispiels­weise ergibt sich das Komplement von 428 als 571.

Zusätzlich muss bei diesem Verfahren noch 1 addiert werden. Dies geschieht, indem übertrag_vorhanden mit true initialisiert wird.

Auf diese Weise wird Folgendes gerechnet, beispiels­weise bei einer Länge der Zahlen von n=3:

a + (999 – b) + 1

Dies ist dasselbe wie

a – b + 1000

Das richtige Ergebnis a – b ergibt sich also, indem im Anschluss an diese Berechnung wieder 1000 subtrahiert wird. Dies geschieht, indem einfach der letzte Übertrag ignoriert wird.

 

Algorithmus Subtraktion durch Komplementbildung
Eingabe:	Zwei nichtnegative ganze Zahlen a = an-1 ... a0 und b = bn-1 ... b0 mit ab in Dezimaldarstellung
Ausgabe:	Differenz d = a + b in Dezimaldarstellung
Methode:	Initialisierung setze übertrag_vorhanden = true Iteration für i = 0 bis n-1 wiederhole setze x = 9 – bi     // Komplement bilden setze x = ai + x wenn übertrag_vorhanden dann erhöhe x um 1 setze übertrag_vorhanden = false wenn x10 dann setze x = x – 10 setze übertrag_vorhanden = true setze si = x

 

Wie bei der Addition wird eine Variable übertrag_vorhanden verwendet, die true oder false als Wert annehmen kann. Anders als bei der Addition wird übertrag_vorhanden jedoch mit true initialisiert.

Als Elementar­operationen werden benötigt: Ergänzen einer Ziffer zu 9 (Komplement­bildung), Addition zweier Ziffern, Weiterzählen um 1, Vergleich mit 10 sowie Subtraktion von 10.

 

Weiter mit:

 

H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 15.05.2009   Updated: 04.06.2018