Rekursion in C: Tutorial zu COP3502C Assignment 3

Rekursion in C: Sitzordnung für den Kinobesuch – Tutorial zu COP3502C Assignment 3

Stell dir vor, du gehst mit Freunden ins Kino – aber nicht jeder darf neben jedem sitzen, und jeder muss Zugang zu Popcorn haben. Klingt nach einer typischen Programmieraufgabe, oder? Genau darum geht es im COP3502C Assignment 3 an der University of Central Florida. In diesem Tutorial lernst du, wie du mit Rekursion in C alle möglichen Sitzordnungen berechnest und die erste lexikografisch gültige findest. Wir nutzen dabei den Permutationsalgorithmus mit used-Hilfsarray, den du aus der Vorlesung kennst. Am 15. Mai 2026 ist der Abgabetermin – also lass uns direkt loslegen!

Die Problemstellung verstehen

Gegeben sind n Personen (3 ≤ n ≤ 10), jede mit einem Namen (max. 19 Zeichen) und der Angabe, ob sie Popcorn hat (1) oder nicht (0). Zusätzlich gibt es p Paare von Personen, die nicht nebeneinander sitzen dürfen. Ziel ist es, alle Sitzordnungen in einer Reihe zu finden, die folgende zwei Bedingungen erfüllen:

Popcorn-Regel: Jede Person muss entweder selbst Popcorn haben oder eine direkte Nachbarperson (links oder rechts) muss Popcorn haben.
Sitzverbot: Bestimmte Personenpaare dürfen nicht benachbart sein.

Du schreibst zwei Programme: Programm 1 gibt die Anzahl aller gültigen Sitzordnungen aus, Programm 2 die erste gültige Ordnung in lexikografischer Reihenfolge.

Warum Rekursion? Ein Trend-Vergleich

Rekursion ist wie das Navigieren durch eine KI-gestützte Playlist: Du startest mit einem leeren Platz und probierst systematisch alle verbleibenden Personen aus – ähnlich wie Spotifys Algorithmus Songs in einer Warteschlange anordnet, aber mit harten Regeln. Oder denk an ein E-Sports-Turnier (z.B. League of Legends Worlds 2026): Jedes Team (Person) hat eine feste Position, aber bestimmte Matches (Sitzverbote) sind tabu, und jeder Spieler braucht Zugang zu einem „Power-Up“ (Popcorn). Rekursion zählt alle möglichen Setzlisten durch – perfekt für kleine n ≤ 10.

Der Permutationsalgorithmus mit used-Hilfsarray

Der Algorithmus aus der Vorlesung arbeitet mit einem Array used[], das markiert, ob eine Person bereits platziert wurde. So stellst du sicher, dass jede Person genau einmal vorkommt. Der rekursive Aufbau:

Rekursionsbasis: Wenn alle n Plätze belegt sind, prüfe die Popcorn-Regel und die Sitzverbote.
Rekursionsschritt: Für jeden noch nicht verwendeten Namen: setze ihn auf den aktuellen Platz, markiere ihn als verwendet, rufe die Funktion für den nächsten Platz auf, und entferne die Markierung (Backtracking).

Da die Namen in der Eingabe bereits alphabetisch sortiert sind, durchläuft der Algorithmus die Permutationen automatisch in lexikografischer Reihenfolge – perfekt für Programm 2.

Popcorn-Regel prüfen

Für jede Person i in der Sitzordnung muss gelten: popcorn[i] == 1 ODER popcorn[i-1] == 1 ODER popcorn[i+1] == 1. Ränder beachten: Person 0 hat nur einen rechten Nachbarn, Person n-1 nur einen linken.

int isValidOrder(int order[], int n, int popcorn[], int constraints[][2], int numConstraints) {
    // Prüfe Popcorn-Regel
    for (int i = 0; i < n; i++) {
        int hasPopcorn = popcorn[order[i]];
        int leftPop = (i > 0) ? popcorn[order[i-1]] : 0;
        int rightPop = (i < n-1) ? popcorn[order[i+1]] : 0;
        if (!(hasPopcorn || leftPop || rightPop)) return 0;
    }
    // Prüfe Sitzverbote
    for (int c = 0; c < numConstraints; c++) {
        int a = constraints[c][0], b = constraints[c][1];
        for (int i = 0; i < n-1; i++) {
            if ((order[i] == a && order[i+1] == b) ||
                (order[i] == b && order[i+1] == a)) return 0;
        }
    }
    return 1;
}

Rekursive Permutation – Beispielcode

void permute(int current[], int used[], int pos, int n,
             int popcorn[], int constraints[][2], int numConstraints,
             int *count, int firstValid[], int findFirst) {
    if (pos == n) {
        if (isValidOrder(current, n, popcorn, constraints, numConstraints)) {
            (*count)++;
            if (findFirst && *count == 1) {
                for (int i = 0; i < n; i++) firstValid[i] = current[i];
            }
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = 1;
            current[pos] = i;
            permute(current, used, pos+1, n, popcorn, constraints, numConstraints, count, firstValid, findFirst);
            used[i] = 0;
            // Für Programm 2: frühzeitig abbrechen, wenn erste Lösung gefunden
            if (findFirst && *count > 0) return;
        }
    }
}

Integration in main1.c und main2.c

Lies zuerst die Eingabe: n, p, dann n Zeilen mit Name und Popcorn-Status, dann p Zeilen mit den Sitzverboten. Speichere Namen in einem String-Array und weise jedem Namen einen Index zu (0..n-1). Für die Sitzverbote speicherst du die Index-Paare. Rufe dann permute auf – für Programm 1 mit findFirst = 0, für Programm 2 mit findFirst = 1. Gib die Anzahl bzw. die Namen der ersten gültigen Ordnung aus.

Laufzeit und Optimierung

Der Algorithmus hat eine Laufzeit von O(n * n!), da alle n! Permutationen erzeugt und jede in O(n) geprüft wird. Für n ≤ 10 ist das völlig in Ordnung (10! = 3.628.800). Keine dynamische Speicherverwaltung nötig – Arrays mit fester Größe (z.B. int order[10]) reichen aus.

Häufige Fehler vermeiden

Popcorn-Regel falsch interpretiert: Jede Person muss Popcorn haben ODER der Linke ODER der Rechte. Nicht alle drei Bedingungen gleichzeitig.
Lexikografische Ordnung: Da die Namen bereits sortiert eingegeben werden, liefert der Algorithmus die erste gültige Permutation genau dann, wenn du die Schleife von i=0 bis n-1 laufen lässt und nach dem ersten Fund zurückkehrst.
Indizes verwechseln: Speichere die Popcorn-Informationen pro Person (Index), nicht pro Sitzplatz.

Beispiel aus der Aufgabenstellung

Nehmen wir das erste Sample: 5 Personen, Alia (Popcorn), Belinda (kein), Carlos (kein), Danica (kein), Edward (Popcorn). Sitzverbote: Alia-Carlos, Belinda-Edward. Dein Programm sollte 10 gültige Ordnungen zählen und als erste lexikografische „Alia Belinda Carlos Edward Danica“ ausgeben. Überprüfe: Alia und Edward haben Popcorn, jeder hat Zugang, und die Verbote sind eingehalten.

Trend-Kontext: Kinoerlebnis 2026

Stell dir vor, der Kinobesuch ist ein VR-Kino-Event mit Freunden, bei dem Avatare nebeneinander sitzen – Popcorn wird digital geteilt. Oder du organisierst ein Gaming-Turnier (z.B. Fortnite LAN-Party) und musst Spieler so setzen, dass Rivalen nicht nebeneinander sitzen und jeder Zugang zum „Healing-Item“ hat. Rekursion hilft dir, alle fairen Setzlisten zu finden – ein echtes Algorithmus-Superpower für Programmierer!

Fazit

Mit diesem Tutorial hast du das Rüstzeug, um COP3502C Assignment 3 zu meistern. Rekursion ist nicht nur für die Uni, sondern auch in der Praxis nützlich – zum Beispiel für Backtracking in KI-Spielen oder Routenplanung in Apps. Viel Erfolg beim Programmieren!