Algorithmen und Programmierung II

Aufgabe 1 (5 P.)

Gegeben seien folgende Java-Deklarationen:

    int i;
    char c;
    float f;
    byte b;
    boolean bool;
    short s;
    double d;
    long l;

Sind folgende Zuweisungen in Java zulässig und wenn ja, was bewirken sie? Begründe die Antwort.

1. f = b;
2. s = i;
3. i = s;
4. bool = i;
5. c = b;
6. c = (char) b;
7. d = s;
8. f = (float) (d * 1.2);
9. f = d;
10. s = (short) f;

Aufgabe 2 (3 P.)

Können Java-Zuweisungen primitiver Datentypen, die explizite Typumwandlungen beinhalten und ohne Beanstandungen übersetzt werden, Laufzeitfehler (Exceptions) verursachen? Begründe die Antwort.

Aufgabe 3 (4 P.)

Wenn man x⁸ 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=xⁿ 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.2 erfolgen. Teste Dein Programm.

Aufgabe 4 (5 P.)

Die Fibonacci-Zahlen sind eine Folge natürlicher Zahlen, bei der jede Zahl die Summe der beiden vorangegangenen ist.  Die Folge beginnt mit 1, 1, 2, 3, 5, 8, 13 und setzt sich so weiter fort.

1. Entwerfe einen Algorithmus zur Berechnung der Fibonacci-Zahlen.
2. Implementiere den Algorithmus als (nicht abbrechendes) Java-Programm.