Algorithmen und Programmierung II

Übungsblatt 2 - Musterlösung


Aufgabe 1

a)
 
static float ln2a(int n) {
    float result = 0;
    for (int i = 1; i <= n; i++)
        result += (i % 2 == 0) ? -1.f/i : 1.f/i;
    return result;
}

b)
static float ln2b(int n) {
    float sum_pos = 0, sum_neg = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0)
            sum_neg += 1.f/i;
        else
            sum_pos += 1.f/i;
    }
    return sum_pos - sum_neg;
}
c)

Der von ln2b berechnete Näherungswert ist minimal besser als der von ln2a. Dies überrascht, da der unter a) aufsummierte Werte etwas kleiner ist, als die beiden unter b) separat berechneten Werte. Es werden zunehmend kleine Glieder zur Teilsumme addiert, so dass deren Auslöschung droht. Bei der Addition eines weiteren Gliedes unter a) sollten geringfügig weniger Rundungsfehler entstehen, als unter b).


Aufgabe 2

a)

Diagramm

Abkürzungen im Syntaxdiagramm:

AE
 AssignmentExpression
Li
 Literal
AOp AssignmentOperator
Pr
 Primary
BE BinaryExpression
RepSt
 RepetitiveStatement
BOp BinaryOperator
St
 Statement
CompSt CompositeStatement
StE
 StatementExpression
DoSt DoStatement
UE
 UnaryExpression
E Expression
V
 Variable
ESt ExpressionStatement
WhileSt
 WhileStatement
Id Identifier



b)

a=0, b > 0
 Der Algorithmus terminiert nicht, weil die Abbruchbedingung für die erste while-Schleife nie erreicht wird. Es wird wiederholt 0 von b abgezogen, b wird nie kleiner als a.
a > 0, b = 0
 Die zweite while-Schleife terminiert nicht, analog zum ersten Fall.
a = 0, b = 0
 Der Algorithmus terminiert mit dem Ergebnis 0. Dies ist zwar nach Definition kein Teiler, aber bei dieser Eingabe vertretbar.
a < 0 und/oder b < 0
 Der Algorithmus terminiert bei einigen Parameter-Kombinationen mit einem falschen Ergebnis (negative Zahl mit großem Betrag), bei anderen nie. Durch das negative Vorzeichen wird der Betrag der einen Zahl wiederholt zur anderen addiert. Durch den immer größer werdenden Wert kommt es irgendwann zum Überlauf und je nach Parameter-Kombination kann irgendwann "durch Zufall" die Abbruchbedingung der Schleife erreicht werden.


Aufgabe 3
static void perfect() {
    for (int n = 6; ; n++) {
        int summe = 0;
        for (int teiler = 1; teiler <= n/2; teiler++) {
            if (n % teiler == 0)
                summe += teiler;
        }
        if (n == summe) 
            System.out.println(n);
    }
}