Übungen zu Algorithmen und Datenstrukturen 1 - Übung 1

1. Lokales Minima und Maxima

a) Lösungsidee

Es wurden zwei Algorithmen kreiert, welche die Anz. der lokalen Minima (countLocalMin) bzw. Maxima (countLocalMax) zurückgeben. Es wurde davon ausgegangen, dass der erste und letzte Wert keine lokalen Minima bzw. Maxima sein können (da in der Aufgabenstellung von "beiden Nachbarn" die Rede ist).

b) Ablaufdiagramm

flowchart

c) Jana

int countLocalMin (↓f[1:n]) {
    int c = 0;
    for (i = 2 .. n-1) {
        if (f[i-1] > f[i] < f[i+1]) {
            c++;
        }
    }
    return c;
}

int countLocalMax (↓f[1:n]) {
    int c = 0;
    for (i=2 .. n-1) {
        if (f[i-1] < f[i] > f[i+1]) {
            c++;
        }
    }
    return c;
}

d) Welche Darstellungsform?

Jana, weil

2. Verschlüsselung

a)Lösungsidee

Die Verschlüsselung aller 4er-Blöcke wird als erstes in einer for-Schleife gemacht . Dabei werden gleich die Anzahl der 4er-Blöcke gezählt. Anschließend wird mit if-statements zwischen den drei Fällen der Block-Anzahl unterschieden. In allen drei Fällen werden dabei die zu vertauschenden Blocks in 8er-Blocks, also Blocks mit der Länge 8, eingeteilt (Ausnahme im dritten Fall, wenn die Blöcke links und rechts der Mitte vertauscht werden). Das bringt, dass die for-Schleifen zur Vertauschung der 4er-Blöcke nur so oft durchlaufen werden, wie 4er-Blöcke vertauscht werden müssen. Der Algorithmus wurde ausführlich im Jana-Source dokumentiert. 
Da im HTML 4.0 Standard das Jana-Symbol für Ein-/Ausgabeparameter nicht existiert, wurde ↑↓ verwendet.

b) Jana

scramble (↑↓char[n] text ↓int n) {
    int blocks = 0;        // number of 4-length-blocks
    if (n >= 4) {
        for (i = 0 .. (n-(n % 4))/4 - 1) {       // process every 4-length-block, ignore last chars
            blocks++;
            text[i*4] ↔ text[i*4+2];             // swap 1. and 3. letter of block
            text[i*4+1] ↔ text[i*4+3];           // swap 2. and 4. letter of block
        }
        if (blocks <= 1) {
            // not enough 4-length-blocks - nothing is done
        } else if (blocks % 2 == 0){             // even blocks
            for (i1 = 0 .. blocks / 2 - 1)       // process 8-length-blocks
                for (i = i1*8 .. i1*8+3)         // swap two 4-length-blocks
                    text[i] ↔ text[i+4];
        } else if (((blocks - 1)/2) % 2 = 0) {
            // uneven blocks, number of blocks to the left and right of middle block even
            for (i1 = 0 .. (blocks - 1)/4 - 1)   // process first half of 8-length-blocks
                for (i = i1*8 .. i1*8+3)         // swap two 4-length-blocks
                    text[i] ↔ text[i+4];
            for (i1 = (blocks - 1)/4 - 1 .. (blocks - 1)/2)    // process second half of 8-length-blocks
                for (i = i1*8+4 .. i1*8+7)       // swap two 4-length-blocks (idx+4 because of middle block)
                    text[i] ↔ text[i+4];
        } else {    // uneven blocks, number of blocks to the left and right of middle block uneven
            for (i1 = 0 .. (blocks - 3)/4 - 1)   // process 8-length-blocks before 3 middle 4-length-blocks
                for (i = i1*8 .. i1*8+3)         // swap two 4-length-blocks
                    text[i] ↔ text[i+4];
            for (i1 = (blocks - 3)/4 .. (blocks - 3)/2 - 1)
                // process 8-length-blocks after the 3 middle 4-length-blocks
                for (i = i1*8+12 .. i1*8+15)     // swap two 4-length-blocks (idx+12 because of 3 middle blocks)
                    text[i] ↔ text[i+4];
            for (i = (blocks-1)/2 .. (blocks-1)/2+3)    // swap blocks left and right to middle 4-length-block
                text[i-4] ↔ text[i+4];
        }
    } else {
        // not enough letters - nothing is done
    }
}