Übungsblatt 4 - Musterlösung

Algorithmen und Programmierung II

Übungsblatt 4 - Musterlösung

Aufgabe 1

a)

    /** liefert die n-te Fibonacci-Zahl, n >= 0 */
    static int fibrec(int n) {
        return n < 2 ? n : fibrec(n-1) + fibrec(n-2);
    }

    /** liefert die n-te Fibonacci-Zahl, n >= 0 */
    static int fibit(int n) {
        int fib  = 0;
        int prev = 1;
        for (; n>0; n--) {
            fib  = fib + prev;
            prev = fib - prev;
        }
        return fib;
    }

Aufgabe 2

a)

In eine gegebene Fläche a passen solche rechwinkligen Dreiecke, für die das Produkt der Katheten x und y die Bedingung x*y<=2*a erfüllt. Im Algorithmus werden diese wie folgt gefunden: Während eine Kathetenlänge x festgehalten wird (beginnend mit x=1), werden alle Kathetenlängen y gefunden, die die Bedingung erfüllen. Geht man zum nächsten x über, so betrachtet man nur y-Werte mit y>=x, da andernfalls kongruente Dreiecke mitgezählt würden. Der Algorithmus besteht aus zwei geschachtelten Schleifen, die beide bei x*y>2*a abgebrochen werden.

b)

    static int dreieck(double a) {
        int anzahl = 0, x = 1, y = 1;
        while(x*y <= 2*a) {
            do {
                System.out.print(x); System.out.print(" "); 
                System.out.println(y);
                anzahl++;
                y++; 
            } while(x*y <= 2*a);
            x++;
            y = x;
        }
        return anzahl;
    }

Aufgabe 3

Java	SIMPLE
a) while-Schleife mit break
while (Condition1) { Statements1 if (Condition2) break; Statements2 }	if !Condition1 GOTO cont; while: Statements1 if Condition2 GOTO cont; Statements2 if Condition1 GOTO while; cont: ;
b) return in void-Methode
void op() { Statements1 if (Condition1) return; Statements2 }	void op() { Statements1 if Condition1 GOTO cont; Statements2 cont: ; }
c) case-Anweisung
switch(exp) { case cexp1: Statements1 break; case cexp2: Statements2 break; default: Statements3 }	if (exp==cexp1) GOTO c1; if (exp==cexp2) GOTO c2; GOTO def; c1: Statements1 GOTO cont; c2: Statements2 GOTO cont; def: Statements3 cont: ;