Praktikum Software-Engineering I: 3. Übungsaufgabe



Vorlesung:	Software-Engineering I
Semester:	Multimedia 1 (MM1)
Aufgabensteller:	M. Jeckle
Ausgabedatum:	24. November 1999
Abgabedatum:	Praktikum am 1. Dezember 1999

Ziel dieser Übung:

Mit dieser Übungsaufgabe sollen Sie Ihren sicheren Umgang mit den in der Vorlesung vermittelten Konstrollstrukturenan einem einfachen Beispiel demonstrieren.

Aufgabenstellung:

Implementieren Sie den Euklidischen Algorithmus zur Ermittung des größten gemeinsamen Teilers zweier natürlicher Zahlen in einem Java-Programm.

Hintergrundinformation und Hilfestellung:

Der Euklidische Algorithmus ermittelt den größten gemeinsamen Teiler (Abk. ggT) zweier natürlicher Zahlen auf folgende Weise:
Basisprinzip ist die wiederholte Division mit Rest, die folgendermaßen angewandt wird.
Zunächst wird die größere der beiden übergebenen Zahl mit Rest durch die kleinere dividiert. Als Resultat erhält man neben dem positiv ganzzahligen Quotienten einen Rest, der stets größer gleich Null (genau Null im Falle einer glatten Division ("die Division geht auf")) und kleiner als der Quotient selbst ist.
Im nächsten Berechnungsschritt wird der im vorhergehenden Rechenschritt ermittelte Quotient durch den ebenfalls dort ermittelten Rest (wieder mit Rest) dividiert. Dies wird solange fortgeführt, bis als Rest 0 entsteht.
Der im vorausgegangenen Rechenschritt ermittelte Rest ist der größte gemeinsame Teiler.
Anmerkung: geht die Division bereits im ersten Rechenschritt ohne Rest auf, so ist die kleine Zahl Teiler der größeren, und somit selbst der gesuchte ggT.

Es gilt somit immer:
Für a,b Eingangswerte mit a=>b, q ist der ganzzahlige Quotient a/b und r der bei der Division entstehende Rest:
a = b*q + r
Im nächsten Rechenschritt nimmt b den Platz von a bzw. r den von b ein.

Zahlenbeispiel:

Gesucht: größter gemeinsamer Teiler von 123 und 77:

(1)123 : 77 =1 Rest 46
(2)77 : 46 = 1 Rest 31
(3)46 : 31 = 1 Rest 15
(4)31 : 15 = 2 Rest 1
(5)15 :1 = 15 Rest 0.
(6)=> ggT(123,77) = 1.
(7)
(8)

Gesucht: größter gemeinsamer Teiler von 6 und 12:
Zunächst die Position der beiden Zahlen tauschen!

12 : 6 = 2 Rest 0.=> ggT(12,6)=6.

Umsetzungshinweise:

Wählen Sie zur Aufnahme der beiden Eingangswerte einen genügend großen ganzzahligen Java-Datentyp
Legen Sie Ihr Programm so aus, daß die beiden benötigten Eingangswerte über die Kommandozeile beim Aufruf übergeben werden (Aufrufbeispiel: java ggT 5 7).
Im Programm kann auf die beiden Werte als String im Array argv (sofern die Signatur der main-Operation public static void main (String argv[]) lautet) zugegriffen werden.
Der Erste wird als argv[0] und der zweite entsprechend mit argv[1] adressiert.
Zur Umwandlung in einen Zahltyp sollten Sie auf die parse Funktion der Java-API (sie ist für alle Primitivtypen die Zahlen repräsentieren definiert) zurückgreifen. Sollten Sie long als Datentyp gewählt haben, so ergibt sich eine Zuweisung wie folgt:
long a;
a = Long.parseLong(argv[0]);
Bedenken Sie daß evtl. die beiden Eingangswerte vertauscht werden müssen, um dem Kriterium a>=b zu genügen

Service provided by Mario Jeckle
Generated: 2004-06-07T12:31:40+01:00
Feedback SiteMap
This page's original location: http://www.jeckle.de/vorlesung/SEI/p3.html
RDF description for this page