Algorithmen und Programmierung II

Übungsblatt 10 - Musterlösung


Aufgabe 1
    void insertIterativ(String w) {
        Spelling current = this;
        loop: for (;;) {
            if (current.next == null || current.next.word.compareTo(w) > 0) {
                current.next = new Spelling(w, current.next);
            } else if (current.next.word.equals(w)) {
                ; /* ignore */
            } else {
                current = current.next;
                continue loop;
            }
            return;
        }
    }

Aufgabe 2

a) Java iterativ 
    static float kbJ(int[] a) {
        float result = 0;
        for (int i = a.length - 1; i >= 0; i--)
            result = 1 / (a[i] + result);
        return result;
    }
b) Haskell rekursiv
    kbH :: [Integer] -> Float
    kbH [] = 0
    kbH (x:xs) = 1 / (fromInteger x + kbH xs)
c) Haskell endrekursiv
    kbHe :: Float -> [Integer] -> Float
    kbHe acc [] = acc
    kbHe acc xs = kbHe (1 / (fromInteger (last xs) + acc)) (init xs)
d)

1. Schritt: Java endrekursiv, entwickelt aus c)
    static float kbJendrek(int[] a, int last, float acc) {
        if (last < 0) return acc;                         // Pattern kbHe acc []
        return kbJendrek(a, last-1, 1 / (a[last] + acc)); // Pattern kbHe acc xs
    }
2. Schritt: Entrekursivierung von kbJendrek nach Abschnitt 2.4.1
    static float kbJ2(int[] a, int last, float acc) {
        loop: for(;;) {                 // nach Schema:
            if (last < 0) return acc;   //   return G(a)
            acc = 1 / (a[last] + acc);  //   a = F(a)
            last--;                     //   a = F(a)
            continue loop;
        }
    }
3. Schritt: syntaktisch optimiert
    static float kbJ3(int[] a, int last, float acc) {
        for(; last >= 0; last--)
            acc = 1 / (a[last] + acc);
        return acc;
    }
e)  Die zweite Version unter d) entspricht der Struktur des Transformationsschemas. Bei der dritten Version (kbJ3) wurde der Quelltext etwas "aufgeräumt". Diese dritte Variante ist mit der unter a) entwickelten Version praktisch identisch. Einziger Unterschied sind die Hilfsparameter last und acc, die aus der schematischen Transformation des funktionalen in den imperativen Code stammen (Liste vs. Feld). Im nächsten Schritt würde man eine Einbettung durchführen, acc als lokale Variable einführen und den Startwert von last aus der Länge des Feldes a gewinnen, so dass man genau die unter a) entwickelten Version erhält.

f) Java iterativ
    static float sqrt2J(float eps) {
        float res = 0, 
              old = Float.MAX_VALUE;
        while (Math.abs(old - res) > eps) { // while( C(z) )
            old = res;                      //   z = F(z)
            res = 1 / (2 + res);            //   z = F(z)
        }
        return res + 1;
    }
g) Haskell rekursiv, entwickelt aus f)

Nach Abschnitt 2.4.3 überführt die Schleife
    while( C(z) ) { z=F(z); }
einen Anfangszustand init in den Endzustand
    while c f init
Den relevanten Zustand bilden hier der Parameter eps der Java-Methode und die beiden lokalen float-Variablen res und old. Der Anfangszustand ergibt sich aus der Initialisierung der Variablen als Tupel (eps, 0, Float.MAX_VALUE), wobei der dritte Wert um mindestens eps vom zweiten abweichen muss, damit der Algorithmus korrekt funktioniert. In Haskell wird daher alternativ (eps, 0, eps+1) verwendet.

Die Funktionen c und f ergeben sich aus der Java-Version wie folgt:  
    c (eps, res, old) = abs (old-res) > eps
    f (eps, res, old) = (eps, 1/(2+res), res)
Unter Verwendung der while-Funktion aus Abschnitt 2.4.3 ergibt sich die gesuchte Haskell-Funktion wie folgt. Ergebnis ist die um 1 erhöhte zweite Komponente des Zustands-Tupels:
    sqrt2H :: Float -> Float
    sqrt2H eps = res + 1
        where (_, res, _) = while c f (eps, 0, eps+1)
              c (eps, res, old) = abs (old-res) > eps
              f (eps, res, old) = (eps, 1/(2+res), res)
              
    while :: (t->Bool) -> (t->t) -> t -> t
    while cond func init    
        | cond init = while cond func (func init)     
        | otherwise = init