Java-Programmieren-Programmieren Sie die additiven und multiplikativen Euklidischer Algorithmus.

Question

Aufgabe:

A) additiver Euklidischer Algorithmus

(1) wenn a= 0: Ergebnis b

(2) (es ist nun a>0)

  wenn b >0

 (2a)  wenn a>b: setze a:= a - b

 (2b) sonst ( b>=a): setze b:= b - a

  (2c) wiederhole ab (2)

  (3) (es ist nun b= 0)

     Ergebnis ist a

Hinweis: Falls Sie sich wundern, dass nur einmal geprüft wird, ob a=0: Dies ligt daran, dass durch die darauf folgenden Schritte ein positives a stets positiv bleibt.

b) multiplikativer Euklidischer Algorithmus:

(1) wenn b> 0

(1a) setze t:= a mod b (t ist eine temporäre Variable)

(1b) setze a:= b

(1b)  setze b:= t

 (1c) wiederhole ab (1)

(2)  (es ist nun b = 0)

    Ergebnis ist a

Nun die eigentliche Aufgabenstellung: Schreiben Sie eine Klasse Mathe mit folgenden Methoden, die jeweils zwei nichtnegative(wovon Sie ausgehen kölnnen) ganze Zahlen a und b als Parameter haben:

a) ggtAdd führt den additiven Euklidischen Algorithmus iterativ durch und gibt ggT(a,b) zurück.

b) ggTMul führt den multiplikativen Euklidischen Algorithmus iterativ durch und gibt ggT(a,b) zurück.

c) ggTAddOut führt den additiven Euklidischen Algorithmus durch. Zu Beginn jeder Widerholung der Schleife(also vor Schritt (2a)) werden die Werte von a und b, von einem Leerzeichen getrennt, auf einer Zeile auf dem Bildschirm ausgegeben. Ebenso werden diese beiden Werte zum Schluss ausgegegben, also vor Schritt (3) bzw. im Fall a= 0 in Schritt (1). Die Methode gibt als Ergebnis zurück, wie oft die Schleife durchlaufen würde.

Hinweis: Sie müssen also eine zusätzliche Variable einführen, die die Wiederholung mitzählt.

Beispiel: Der Aufruf on ggzAddOut(24,78) produziert auf dem Bildschirm die Ausgabe

24 78

24 54

24 30

24 6

18 6

12 6

6 6

6 0

d) ggTMulOut führt analog zu ggTAddOut den multiplikativen Euklidischen Algorithmus iterativ durch, und gibt jeweils vor den Schritten (1a) und (2) die Zwischenwerte auf dem Bildschirm aus und liefert als Ergebnis die Zahl der Wiederholungen des Verfahrens.

e) ggT ruft ggTMul mit den Werten |a| und |b| auf und gibt das Ergebnis dieses Aufrufs zurück.

Was fällt Ihnen im Vergleich der Ausgaben der beiden Verfahren auf?

Answer 1

public class Mathe {
 
 // a)
 public static int ggTAdd(int a, int b) {
 // (1)
 if (a == 0) {    // wenn a = 0:
  return b;       // Ergebnis b
 }
 
 // (2) (es ist nun a>0)
 while (b > 0) {  // wenn b > 0:
 
  // (2a)
  if (a > b) {    // wenn a > b:
   a = a - b;     // setze a:= a - b
  }
 
  // (2b) sonst (b >= a):
  else {
   b = b - a;     // setze b:= b - a
  }
 
  // (2c) wiederhole ab (2)
 }
 
 // (3) (es ist nun b = 0)
 return a;        // Ergebnis ist a
 }
 
 // c)
 public static int ggTAddOut(int a, int b) {
 int schleifenZaehler = 0;
 
 if (a == 0) {
  System.out.println(a + " " + b);
  return schleifenZaehler;
 }
 
 while (b > 0) {
  schleifenZaehler++;
 
  System.out.println(a + " " + b);
  if (a > b) {
   a = a - b;
  }
 
  else {
   b = b - a;
  }
 }
 
 System.out.println(a + " " + b);
 return schleifenZaehler;
 }
 
 // b)
 public static int ggTMul(int a, int b) {
 int t;           // temporäre Variable t
 
 // (1)
 while (b > 0) {  // wenn b > 0
  // (1a)
  t = a % b;      // setze t:= a mod b (t ist eine temporäre Variable)
  // (1b)
  a = b;          // setze a:= b
  b = t;          // setze b:= t
 
  // (1c) wiederhole ab (1)
 }
 
 return a;
 }
 
 // d)
 public static int ggTMulOut(int a, int b) {
 int schleifenZaehler = 0;
 int t;
 
 while (b > 0) {
  schleifenZaehler++;
 
  System.out.println(a + " " + b);
  t = a % b;
  a = b;
  b = t;
 }
 
 System.out.println(a + " " + b);
 return schleifenZaehler;
 }
 
 // e)
 public static int ggT(int a, int b) {
  // Math.abs(x) gibt Betrag von x zurück
  return ggTMul(Math.abs(a), Math.abs(b));
 }
}

Testen in der Main-Methode:

 public static void main(String[] args) {
 System.out.println("ggTAddOut mit a = 24 und b = 78:");
 System.out.println("Anzahl Schleifendurchläufe: " + ggTAddOut(24,78));
 System.out.println("---------------");
 System.out.println("ggTMulOut mit a = 24 und b = 78:");
 System.out.println("Anzahl Schleifendurchläufe: " + ggTMulOut(24,78));
 System.out.println("---------------");
 System.out.println("Methode ggT mit negativen a und b:");
 System.out.println(ggT(-24,-78));
 }

Ausgabe:

ggTAddOut mit a = 24 und b = 78:
24 78
24 54
24 30
24 6
18 6
12 6
6 6
6 0
Anzahl Schleifendurchläufe: 7
---------------
ggTMulOut mit a = 24 und b = 78:
24 78
78 24
24 6
6 0
Anzahl Schleifendurchläufe: 3
---------------
Methode ggT mit negativen a und b:
6

Was fällt Ihnen im Vergleich der Ausgaben der beiden Verfahren auf?

ggTMul benötigt weniger Schleifendurchläufe als ggTAdd.