|
Mit dieser Übungsaufgabe sollen Sie Ihren sicheren Umgang mit den in der Vorlesung vermittelten Konstrollstrukturenan einem einfachen Beispiel demonstrieren.
Implementieren Sie den Euklidischen Algorithmus zur Ermittung des größten gemeinsamen Teilers zweier natürlicher Zahlen in einem Java-Programm.
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.
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.
java ggT 5 7
).argv
(sofern die Signatur der main-Operation public static void main (String argv[])
lautet)
zugegriffen werden.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]);
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