Labor 2: Algorithmen denken — auf Papier und in Code

Ziel: Sich daran gewöhnen, einen Algorithmus auf Papier zu denken — bevor man Code schreibt.

Aufgabenstellung:

Wähle eine dieser Alltagsaufgaben:

• 🥞 Pfannkuchen backen
• 📚 Ein bestimmtes Buch in der Bibliothek finden
• 🦷 Zähne putzen (gründlich, alle Schritte)
• ☕ Tee mit Milch und Zucker zubereiten
• 🚇 Mit der U-Bahn von zu Hause zur HTW fahren

Schreibe den Pseudocode dafür — 5 bis 10 Schritte. Achte auf:

• Endlich: hat ein klares Ende
• Eindeutig: jeder Schritt ist klar (kein „mach's einfach schön")
• Ausführbar: ein Roboter könnte es nachmachen

Diskussion mit Sitznachbar:

Tausch deinen Pseudocode mit jemandem aus. Versucht, den jeweils anderen Algorithmus „im Kopf auszuführen". Funktioniert er? Welche Schritte sind unklar?

Aus VL3: Du arbeitest an der Kasse. Ein Kunde soll Wechselgeld zurückbekommen — mit so wenigen Münzen wie möglich.

Problem:

• Eingabe: Betrag in Cent (z.B. 287 für 2,87 €)
• Ausgabe: Liste der zurückgegebenen Münzen
• Verfügbare Münzen: 200, 100, 50, 20, 10, 5, 2, 1 Cent

Schritt 1 — Pseudocode:

Schreibe selbst den Pseudocode auf, bevor du den Code anschaust. Tipp: die Strategie heißt Greedy — „nimm immer das Größte zuerst".

Schritt 2 — Implementieren:

Setze deinen Pseudocode in Code um. Bevorzugt C, aber wenn du eine andere Sprache flüssiger sprichst — auch gut.

Teste mit:

• 183 Cent → erwartet: 1 € + 50 ct + 20 ct + 10 ct + 2 ct + 1 ct (6 Münzen)
• 500 Cent → erwartet: 2 € + 2 € + 1 € (3 Münzen)
• 97 Cent → erwartet: 50 ct + 20 ct + 20 ct + 5 ct + 2 ct (5 Münzen)

#include <stdio.h>

void wechselgeld(int cent) {
    int muenzen[] = {200, 100, 50, 20, 10, 5, 2, 1};

    for (int i = 0; i < 8; i++) {
        while (cent >= muenzen[i]) {
            printf("%d Cent\n", muenzen[i]);
            cent -= muenzen[i];
        }
    }
}

int main() {
    int betrag;
    printf("Betrag in Cent: ");
    scanf("%d", &betrag);
    wechselgeld(betrag);
    return 0;
}

Aus VL3: die berühmte Aufgabe vom kleinen Gauß. Berechne die Summe 1 + 2 + 3 + … + N.

Aufgabe:

Implementiere zwei Versionen, die dasselbe Ergebnis liefern, aber unterschiedlich vorgehen:

1. Version A — Schleife: addiere jede Zahl einzeln
2. Version B — Gauß-Formel: n * (n+1) / 2

Schritt 1 — beide Versionen schreiben

Schreibe beide Funktionen. Beide sollen für n=100 dasselbe Ergebnis liefern (5050).

Schritt 2 — Laufzeit messen

Nutze clock() aus <time.h>, um die Dauer zu messen — bei n = 1.000.000.000 (eine Milliarde).

#include <time.h>

clock_t start = clock();
// ... Algorithmus läuft ...
clock_t ende = clock();
double sek = (double)(ende - start) / CLOCKS_PER_SEC;
printf("Dauer: %.6f Sekunden\n", sek);

Schritt 3 — Reflexion

Schreibe in 1-2 Sätzen auf:

• Welcher Algorithmus war schneller?
• Warum?
• Was hat das mit der „Wahl der Programmiersprache" zu tun?

#include <stdio.h>
#include <time.h>

long long summe_schleife(long long n) {
    long long summe = 0;
    for (long long i = 1; i <= n; i++) {
        summe += i;
    }
    return summe;
}

long long summe_gauss(long long n) {
    return n * (n + 1) / 2;
}

int main() {
    long long N = 1000000000LL;  // 1 Milliarde

    clock_t s1 = clock();
    long long r1 = summe_schleife(N);
    double t1 = (double)(clock() - s1) / CLOCKS_PER_SEC;

    clock_t s2 = clock();
    long long r2 = summe_gauss(N);
    double t2 = (double)(clock() - s2) / CLOCKS_PER_SEC;

    printf("Schleife: %lld in %.6f s\n", r1, t1);
    printf("Gauß:     %lld in %.6f s\n", r2, t2);
    return 0;
}

Aus VL3: ein Wort ist ein Palindrom, wenn es vorwärts und rückwärts gleich gelesen wird (ANNA, OTTO, RACECAR).

Aufgabe:

• Eingabe: ein Wort als String
• Ausgabe: 1 wenn Palindrom, 0 sonst

Schritt 1 — Pseudocode

Schreibe den Algorithmus auf Papier. Tipp aus VL3: vergleiche das erste mit dem letzten, dann das zweite mit dem vorletzten, …

Schritt 2 — Implementieren

Teste mit: ANNA, OTTO, HALLO, RACECAR, HTW.

#include <stdio.h>
#include <string.h>

int ist_palindrom(char wort[]) {
    int n = strlen(wort);
    int links = 0;
    int rechts = n - 1;

    while (links < rechts) {
        if (wort[links] != wort[rechts]) {
            return 0;          // sofort abbrechen
        }
        links++;
        rechts--;
    }
    return 1;                  // alle Paare passten
}

int main() {
    char *tests[] = {"ANNA", "OTTO", "HALLO", "RACECAR", "HTW"};
    for (int i = 0; i < 5; i++) {
        printf("%-10s: %s\n", tests[i],
               ist_palindrom(tests[i]) ? "Palindrom ✓" : "kein Palindrom");
    }
    return 0;
}

Aus VL2: verschiedene Datentypen, verschiedene Format-Specifier. Hier die typischen Stolperfallen.

Aufgabe — Untersuche, was passiert:

Schreibe ein Programm casting.c, das folgende Berechnungen ausgibt:

1. 30 / 7 als %d (int)
2. 30.0 / 7 als %f (double)
3. (double)30 / 7 als %f
4. 30 / 7 als %f ← Achtung!

Vorhersage vor dem Tippen:

Schreibe für jede Zeile vorher auf, was du erwartest. Dann probier's aus. Wer hat recht?

#include <stdio.h>

int main() {
    printf("30 / 7 (als %%d):    %d\n", 30 / 7);
    printf("30.0 / 7 (als %%f):  %f\n", 30.0 / 7);
    printf("(double)30 / 7:     %f\n", (double)30 / 7);
    printf("30 / 7 (als %%f):    %f  ← undefined behavior!\n", 30 / 7);
    return 0;
}

30 / 7 (als %d):    4
30.0 / 7 (als %f):  4.285714
(double)30 / 7:     4.285714
30 / 7 (als %f):    0.000000  ← oder Müll, je nach Compiler

Ziel: aus einer Alltagsbeschreibung den passenden Algorithmus erkennen — die Brille der Algorithmen-Welt aufsetzen.

Welcher Algorithmus passt?

Zu jedem Szenario: welcher Algorithmus aus VL3 passt? (Münzwechsel/Greedy · Gauß-Formel · Palindrom-Check · keiner)

1. An der Supermarkt-Kasse berechnest du, wie viel Wechselgeld du dem Kunden gibst — mit so wenig Münzen wie möglich. → ?
2. Dein Lehrer fragt: „Was ist 1 + 2 + 3 + … + 1000?" — du brauchst eine Sekunde. → ?
3. Du prüfst, ob das Wort „LAGERREGAL" rückwärts gleich ist. → ?
4. Du suchst die billigste Route in Google Maps von A nach B. → ?
5. Beim Zähneputzen folgst du immer derselben Reihenfolge: erst oben links, dann oben rechts, dann unten. → ?

Bonus-Frage:

Für Szenario 4 (Google Maps): das ist ein Graph-Algorithmus — dazu kommen wir später. Aber kannst du raten, was die Knoten und Kanten in Google Maps sind?