Übungsblatt 5 - Musterlösung

Algorithmen und Programmierung II

Übungsblatt 5 - Musterlösung

Aufgabe 1

a)

	i	j	k	q:	b	i	Ausgabe
	0	0	0
i=0;
j=1;		1
k=2;			2
q(true,k);					true
int i=j;						2
p(j);
i++;			3
show(i,j,k);							3 1 3
show(i,j,k);							2 3 3
q(false, i);					false
int i=j;						0
p(i);
i++;						1
show(i,j,k)							1 1 3
show(i,j,k)							1 0 3

	i	j	k	q:	b	j	i	p:	i	Ausgabe
	0	0	0
i=0;
j=1;		1
k=2;			2
q(true,k);					true	0
int i=j;							0
p(j);									0
i++;									1
show(i,j,k);										1 1 2
<return>						1
show(i,j,k);										0 1 2
<return>			1
q(false, i);					false	0
int i=j;							0
p(i);									0
i++;									1
show(i,j,k)										1 1 1
<return>							1
show(i,j,k)										1 0 1
<return>

Aufgabe 2

a)

int (int, int, int(int, int))

b)

Der Rumpf besteht aus einer return-Anweisung. Zu überprüfen ist, ob der zurückgelieferte Wert vom Typ int ist. Der Ausdruck hinter return ist ein bedingter Ausdruck. Desser erster Teilausdruck "x==0" ist vom Typ boolean (Ergebnis eines Vergleichsoperators). Der zweite Teilausdruck "n" besteht aus dem Parameter n der Methode a und ist vom Typ int. Der letzte Teilausdruck "f(x, a(n,x-1,f))" stellt den Aufruf der als Parameter f übergebenen Methode dar. f hat den Typ int(int,int). Als erster Parameter wird x vom Typ int übergeben. Der Methodenaufruf von a bildet den zweiten Parameter. Die Typen der aktuellen Parameter von a sind korrekt (x vom Typ int, x-1 vom Typ int und f vom Methodentyp int(int,int)). Der Rückgabewert von a ist vom Typ int und damit korrekter zweiter Parameter von f. Der Rückgabewert von f hat Typ int. Mit diesen zweiten und dritten Parametern hat auch der bedingte Ausdruck den Typ int und passt zum Typ des Rückgabewerts von a.

c)

a bewirkt eine Faltungsoperation auf der Zahlen 1, 2, ..., x mit der Operation f und dem neutralen Element n bezüglich f. Sei folgende Methode mult definiert:

static int mult(int a, int b) { return a*b; }

Dann setzt sich die Auswertung des Aufrufs von a(1, 4, mult) wie folgt zusammen:

a(1, 4, mult) =
mult(4, a(1, 3, mult))                          = 4*(3*(2*(1*1))) = 4! = 24
        mult(3, a(1, 2, mult))                  = 3*(2*(1*1))
                mult(2, a(1, 1, mult))          = 2*(1*1)
                        mult(1, a(1, 0, mult))  = 1*1
                                1

d)

a in Haskell (monomorph):

a :: Int -> Int -> (Int -> Int -> Int) -> Int
a n 0 f = n
a n x f = f x (a n (x-1) f)

Als Funktionsparameter f könnten z.B. die folgende Funktion übergeben werden:

f :: Int -> Int -> Int
f = (*)

Typ von a in Haskell (polymorph):

a :: Num t => b -> t -> (t -> b -> b) -> b

Das zweite Argument muss einen numerischen Typ haben, da es mit 0 verglichen wird und in dem arithmetischen Ausdruck "x-1" verwendet wird.

Funktionsparameter:

f :: Num t => t -> b -> b

Aufgabe 3

a)

class Complex {

    float re, im;
    final static Complex I = new Complex(0, 1);

    Complex(float r, float i) {
        re = r;
        im = i;
    }
    void add(Complex c) {
        re += c.re;
        im += c.im;
    }
    void sub(Complex c) {
        re -= c.re;
        im -= c.im;
    }
    void mul(Complex c) {
        float new_re = re*c.re - im*c.im;
        im = re*c.im + im*c.re;
        re = new_re;
    }
    void div(Complex c) {
        float new_re = (re*c.re + im*c.im) / (c.re*c.re + c.im*c.im);
        im = (im*c.re - re*c.im) / (c.re*c.re + c.im*c.im);
        re = new_re;
    }
    float abs() {
        return (float) Math.sqrt(re*re + im*im);
    }
    boolean equ(Complex c) {
        return re == c.re && im == c.im;
    }
}

class Cmplx {
    
    final float re, im;
    final static Cmplx I = new Cmplx(0, 1);

    Cmplx(float r, float i) {
        re = r;
        im = i;
    }
    Cmplx add(Cmplx c) {
        return new Cmplx(re + c.re, im + c.im);
    }
    Cmplx sub(Cmplx c) {
        return new Cmplx(re - c.re, im - c.im);
    }
}

c)

Die erste Variante kommt dem Gedanken der Objektorientierung näher: die Operationen modifizieren das Objekt. Die zweite Variante entspricht eher der mathematischen Sichtweise: Die Verknüpfung von zwei Operanden liefert ein Ergebnis, hier in Form eines neuen Objekts. Die Operanden bleiben dabei unverändert und stehen auch noch nach Ausführung der Operation zur Verfügung. Gibt es in einem Programm mehrere Verweise auf ein Complex-Objekt, so zeigen nach Ausführung einer Methode alle Verweise auf das modifizierte Objekt. Bei Verwendung von Cmplx würden die Verweise auf das unverändert alte Objekt zeigen. Wegen ihrer Nähe zu den herkömmlichen numerischen Typen würde man bei komplexen Zahlen vielleicht eher das letzte Verhalten bevorzugen.

Da die Objekte bei Variante b) unverändert bleiben, würde es sich auch anbieten, die Operationen als statische Methoden anzulegen, etwa static Cmplx add(Cmplx a, Cmplx b).