Algorithmen und Programmierung II

 


SS 2002 Dr. Hannes Federrath
Übung 1 Natalie Ardet
Abgabe bis zum 02.05.02

Die Lösung der Aufgaben und die Abgabe der Lösungen erfolgt in Zweiergruppen!

Hinweis: Benutze die Ressourcen der ALP2 Webseite.

Aufgabe 0 

Bevor Ihr mit der Lösung der Aufgaben anfängt, testet gegebenenfalls Eure Java-Arbeitsumgebung.
Führt z.B. folgendes JAVA Programm aus:

public class SayHello {
    public static void main(String[] args) {
    Mouth mouth = new Mouth();
    mouth.say("Hello World");
    }
}

class Mouth {
    public void say(String what) {
        System.out.println(what);
    }
}

Bei erfolgreicher Ausführung wird die Zeichenkette "Hello World" ausgegeben. 

Aufgabe 1 (4 P.)

Folgendes Java-Programm berechnet die Fakultät einer ganzen Zahl:


public class FakultaetBerechner{

  public static void main(String[] argv) { 

    if (argv.length == 1) {  // Pruefe ob die Kommandozeile genau ein Argument hat 

      int n = Integer.parseInt(argv[0]);  // Erstes Kommandozeilenargument einlesen
      Fakultaet meineFakultaet = new Fakultaet(n); // Fakultaet von n erzeugen
      int ergebnis = meineFakultaet.gibWert();   // Fakultaet abfragen        
      System.out.println(ergebnis);        // Fakultaet ausgeben       

    } 
     else {
 
       System.out.println("Aufruf: java FakultaetBerechner <n>"); 

    } 
  } 
}


class Fakultaet {
  /** Berechnet fuer n>=0 die Fakultaet n! von n */   
  private int n;

  public Fakultaet(int m) {
     n = m;     
  } 

  public int gibWert() { 
    int wert = 1;
    for (int i=1; i<=n; ++i) {  
      wert *= i;                // Abkuerzung fuer: wert = wert * i; 
    }  
    return wert;
  }
} 

Ändere die Klasse  Fakultaet derart, daß die Fakultät rekursiv berechnet wird. 

Hinweis: Man spricht von Rekursion wenn sich eine Methode selbst aufruft. Der rekursive Algorithmus zur Berechnung der Fakultät beruht darauf, daß n! gleich n*(n-1)! ist.

Aufgabe 2 (8+2 = 10 P.)

  1. Entwickle ein Java-Programm, das die Summe
    1 - 1/2 + 1/3 - 1/4 + ... + 1/9999 - 1/10000
    auf die folgenden vier Arten berechnet:
    1. Addition der Terme strikt von links nach rechts,
    2. Addition der Terme strikt von rechts nach links,
    3. getrennte Addition der positiven und negativen Terme, von links nach rechts, und
    4. getrennte Addition der positiven und negativen Terme, von rechts nach links.
  2. Führe das Programm aus. Warum ergeben die Berechnungsmethoden unterschiedliche Resultate? Welche ist vorzuziehen und warum?

Aufgabe 3 (4 P.)

Wenn man x8 berechnen will, ist es geschickter,

x *= x;
x *= x;
x *= x;

zu programmieren und somit mit drei Multiplikationen auszukommen als etwa mit

p = 1;
for (int i=0; i<8; ++i) {
  p *= x;
}

acht Multiplikationen zu benötigen. Diese Beobachtung führt zu einem Algorithmus für die schnelle Exponentiation (im englischen heißt der Algorithmus square-multiply), der p=xn für x>0 und natürliche n berechnet:

Setze p auf 1.
Solange n ungleich 0 ist:
    Falls n ungerade ist, multipliziere p mit x.
    Halbiere n. (Der Rest wird ignoriert.)
    Quadriere x.

Implementiere den Algorithmus als Java-Programm, das mit x und n parametrisiert ist. Der Zugriff auf die Argumente soll dabei über die Kommandozeilenparameter wie in Aufgabe 1 erfolgen. Die Kommandozeilenargumente werden wie folgt eingelesen:

   double x = (new Double(argv[0])).doubleValue();
   int n = Integer.parseInt(argv[1]);


17.06.2002