# Integrierte Stichwahl Quelle: https://dev.inf.zone/exercises/05/runoff/ ## Aufgabe **Auf einen Blick** - **Was:** Sie vervollständigen `runoff.c`, ein Programm, das eine Wahl nach dem Verfahren der integrierten Stichwahl auswertet. - **Aufruf:** `./runoff Alice Bob Charlie` – die Kandidaten als Kommandozeilenargumente (höchstens 9). - **Eingabe:** zuerst die Zahl der Wählenden, dann für jede Person *alle* Kandidaten in der Reihenfolge ihrer Präferenz (`Rank 1:`, `Rank 2:`, …). - **Ausgabe:** der Name des Siegers – bei Gleichstand aller verbliebenen Kandidaten die Namen aller verbliebenen Kandidaten, jeder in einer eigenen Zeile. - **Ungültige Stimme:** Steht ein Name nicht auf dem Stimmzettel, gibt das Programm `Invalid vote.` aus und bricht die ganze Wahl ab (das erledigt `main`). - **Ihre Arbeit:** die sechs Funktionen `vote`, `tabulate`, `print_winner`, `find_min`, `is_tie` und `eliminate`. Alles andere in `runoff.c` bleibt unverändert. ### So funktioniert die integrierte Stichwahl Jede Person gibt eine Rangfolge ab, etwa 1. Alice, 2. Bob, 3. Charlie. Ausgewertet wird in Runden: 1. **Zählen:** Jeder Stimmzettel zählt für den Kandidaten, der darauf am weitesten oben steht und noch nicht ausgeschieden ist. 2. **Sieg:** Hat ein Kandidat mehr als die Hälfte aller Stimmen, hat er gewonnen. 3. **Gleichstand:** Haben alle verbliebenen Kandidaten gleich viele Stimmen, gewinnen alle gemeinsam. 4. **Ausscheiden:** Andernfalls scheiden alle Kandidaten mit der geringsten Stimmenzahl aus. Weiter mit Schritt 1. **Beispiel** mit 9 Stimmzetteln: | Anzahl | 1. Präferenz | 2. Präferenz | 3. Präferenz | | ------ | ------------ | ------------ | ------------ | | 2 | Alice | Bob | Charlie | | 3 | Bob | Alice | Charlie | | 2 | Charlie | Alice | Bob | | 2 | Charlie | Bob | Alice | - **Runde 1:** Alice 2, Bob 3, Charlie 4. Niemand hat mehr als die Hälfte (also mindestens 5 von 9). Alice hat die wenigsten Stimmen und scheidet aus. - **Runde 2:** Die beiden Stimmzettel von Alice zählen jetzt für ihre 2. Präferenz, Bob: Bob 5, Charlie 4. Bob gewinnt. Warum man überhaupt so wählt, steht am Ende der Seite unter „Zum Weiterlesen“. ## Demo [Terminal-Aufzeichnung ansehen](https://asciinema.org/a/4rhSKgaZQsY93RLj0xgu7nwKB) ## Aufgabenmaterial Für diese Aufgabe werden Sie ein von uns zur Verfügung gestelltes Codegerüst vervollständigen. **Aufgabenmaterial herunterladen** Öffnen Sie VS Code entsprechend Ihrem [Setup](https://dev.inf.zone/extras/setup/). Öffnen Sie Ihr Terminalfenster und führen Sie dann `cd` aus. Die Eingabeaufforderung Ihres Terminalfensters sollte wie folgt aussehen: ```bash $ ``` Führen Sie dann ```bash wget https://dev.inf.zone/download/exercises/05/runoff.zip ``` aus, um eine ZIP-Datei namens `runoff.zip` in den aktuellen Ordner herunterzuladen. Achten Sie darauf, dass Sie das Leerzeichen zwischen `wget` und der folgenden URL nicht übersehen, und auch kein anderes Zeichen! Führen Sie jetzt ```bash unzip runoff.zip ``` aus, um das ZIP-Archiv in einen Ordner namens `runoff` zu extrahieren. Sie brauchen die ZIP-Datei nicht mehr, also können Sie ```bash rm runoff.zip ``` ausführen. Antworten Sie mit "y", gefolgt von der Eingabetaste, um die heruntergeladene ZIP-Datei zu entfernen. Führen Sie dann ```bash cd runoff ``` aus, um in dieses Verzeichnis zu wechseln. Ihre Eingabeaufforderung sollte nun wie folgt aussehen: ```bash runoff/ $ ``` Wenn alles funktioniert hat, sollten Sie nach dem Ausführen von ```bash ls ``` eine Datei mit dem Namen `runoff.c` sehen. Wenn Sie `code runoff.c` ausführen, sollte sich die Datei öffnen. In diese Datei werden Sie Ihren Code für diese Aufgabe einfügen. Wenn diese Datei nicht angezeigt wird, verfolgen Sie Ihre Schritte zurück und schauen Sie, ob Sie herausfinden können, wo Sie einen Fehler gemacht haben! **Überblick über `runoff.c`** Wenn Sie die Funktionalität eines bestehenden Codes erweitern wollen, sollten Sie ihn zunächst in seinem jetzigen Zustand verstehen. Sehen wir uns zuerst den Anfang von `runoff.c` an. Dort sind zwei Konstanten definiert: `MAX_CANDIDATES` für die maximale Anzahl der Kandidaten bei der Wahl und `MAX_VOTERS` für die maximale Anzahl der Wähler bei der Wahl. ```c // Max voters and candidates #define MAX_VOTERS 100 #define MAX_CANDIDATES 9 ``` Die Konstante `MAX_CANDIDATES` wird verwendet, um die Größe eines Arrays, `candidates`, festzulegen. Dieses Array enthält alle Kandidaten der Wahl. ```c // Array of candidates candidate candidates[MAX_CANDIDATES]; ``` `candidates` ist ein Array des Typs `candidate`. In `runoff.c` ist ein `candidate` eine eigens definierte `struct`. Jeder `candidate` besteht aus einem `string` für den `name`, einem `int`, in dem die Anzahl der `votes` gespeichert wird, und einem `bool`-Wert namens `eliminated`, der angibt, ob der Kandidat bereits aufgrund geringer Stimmenzahl von der Wahl ausgeschlossen wurde. ```c // Candidates have name, vote count, eliminated status typedef struct { string name; int votes; bool eliminated; } candidate; ``` Dies hilft uns, das zweidimensionale Array `preferences` besser zu verstehen. ```c // preferences[i][j] is jth preference for voter i int preferences[MAX_VOTERS][MAX_CANDIDATES]; ``` Das Array `preferences[i]` enthält alle Präferenzen des Wählers Nummer `i`. Jedes Element dieses Arrays repräsentiert also gewissermaßen den Stimmzettel eines Wählers. Deshalb ist dieses Array auch so groß wie die Konstante `MAX_VOTERS`, mit der die maximale Anzahl der Wähler definiert wurde. Der Integer von `preferences[i][j]` speichert dann den Index des Kandidaten aus dem Array `candidates`, der die `j`-te Präferenz des Wählers `i` ist. Während man also über `preferences[i]` auf die Stimmzettel der Wähler zugreifen kann, enthält `preferences[i][j]` gewissermaßen den Inhalt des jeweiligen Stimmzettels. Wenn an der ersten Stelle, also unter `preferences[i][0]`, etwa eine `2` gespeichert ist, bedeutet dies, dass die erste Präferenz des Wählers `i`, der Kandidat ist, der im Array `candidates` an dritter Stelle, dem Index `2`, gespeichert ist. Dieses Array entspricht daher der Größe der `MAX_CANDIDATES`-Konstante. Das Programm hat außerdem zwei globale Variablen: `voter_count` und `candidate_count`. ```c // Numbers of voters and candidates int voter_count; int candidate_count; ``` Nun zur `main`-Funktion. Hier beginnt nach der Bestimmung der Anzahl der Kandidaten und der Anzahl der Wähler die Schleife zur Wahl. Jeder Wähler bekommt nun die Möglichkeit, seine Stimme abzugeben. Während der Wähler seine Präferenzen eingibt, wird die Funktion `vote` aufgerufen, um alle Präferenzen zu erfassen. Wird der Stimmzettel zu irgendeinem Zeitpunkt als ungültig angesehen, wird das **Programm beendet** (also die gesamte Wahl abgebrochen). Sobald alle Stimmen eingegangen sind, beginnt eine weitere Schleife: In dieser Schleife wird der Sieger der Stichwahl ermittelt und der letztplatzierte Kandidat gestrichen, bis ein Sieger feststeht. Der erste Aufruf ist hierbei eine Funktion namens `tabulate`, die alle Präferenzen der Wähler betrachtet und die aktuellen Stimmensummen berechnet, indem sie den Spitzenkandidaten jedes Wählers betrachtet, der noch nicht ausgeschlossen wurde. Danach sollte die Funktion `print_winner` den Gewinner ausgeben, wenn es einen gibt; wenn es einen gibt, wird das Programm beendet. Andernfalls muss das Programm die geringste Anzahl der Stimmen ermitteln, die jeder Kandidat, der noch zur Wahl steht, erhalten hat (durch einen Aufruf von `find_min`). Wenn sich herausstellt, dass **alle** Kandidaten die gleiche Anzahl an Stimmen erhalten haben (wie durch die Funktion `is_tie` ermittelt), wird die Wahl als unentschieden erklärt; andernfalls wird der Kandidat (oder die Kandidaten) auf dem letzten Platz durch einen Aufruf der Funktion `eliminate` von der Wahl ausgeschlossen. Wenn Sie etwas weiter unten in der Datei nachsehen, werden Sie feststellen, dass die Implementierung der Funktionen - `vote`, `tabulate`, `print_winner`, `find_min`, `is_tie` und `eliminate` - Ihnen überlassen ist! **Zusätzlicher Hinweis: Sie sollten nichts in `runoff.c` ändern, außer den Implementierungen der genannten Funktionen (und dem Hinzufügen zusätzlicher Header-Dateien). Überdenken Sie stattdessen Ihren Lösungsansatz, falls dieser nur mit einer Änderung an einer anderen Stelle im Code funktioniert.** ## Spezifikation check50 prüft jede der sechs Funktionen einzeln, auch ihre Rückgabewerte: - **`vote(voter, rank, name)`:** Stimmt `name` genau mit dem Namen eines Kandidaten überein (Groß- und Kleinschreibung zählt), speichern Sie dessen Index im Array `candidates` in `preferences[voter][rank]` und geben `true` zurück, sonst `false`. `rank` zählt ab 0: `0` ist die erste Präferenz. Sie können davon ausgehen, dass keine zwei Kandidaten denselben Namen haben. - **`tabulate()`:** erhöht für jeden Stimmzettel die `votes` des Kandidaten, der darauf am weitesten oben steht und noch nicht ausgeschieden ist (Regel 1). - **`print_winner()`:** Hat ein Kandidat mehr als die Hälfte der Stimmen, gibt sie seinen Namen mit Zeilenumbruch aus und liefert `true`. Sonst gibt sie nichts aus und liefert `false`, auch wenn jemand genau die Hälfte hat. - **`find_min()`:** liefert die kleinste Stimmenzahl unter den Kandidaten, die noch nicht ausgeschieden sind. - **`is_tie(min)`:** liefert `true`, wenn alle noch nicht ausgeschiedenen Kandidaten genau `min` Stimmen haben, sonst `false`. - **`eliminate(min)`:** setzt bei jedem noch nicht ausgeschiedenen Kandidaten mit genau `min` Stimmen `eliminated` auf `true`. ## Hilfestellung Klicken Sie auf die folgenden Tipps, um einige Ratschläge zur Implementierung der jeweiligen Funktion zu erhalten! **Implementierung der `vote`-Funktion** - Erinnern Sie sich, dass `candidate_count` die Gesamtzahl der Kandidaten für die Wahl speichert. - Erinnern Sie sich daran, dass Sie [`strcmp`](https://manual.cs50.io/3/strcmp) verwenden können, um zwei Zeichenketten zu vergleichen. - Erinnern Sie sich, dass `preferences[i][j]` den Index des Kandidaten speichert, der die `j`-te Präferenz des `i`-ten Wählers ist. **Implementierung der `tabulate`-Funktion** - Erinnern Sie sich, dass `voter_count` die Gesamtzahl der Wähler in der Wahl speichert und dass wir für jeden Wähler in unserer Wahl einen Stimmzettel auswerten müssen. - Erinnern Sie sich daran, dass für einen Wähler `i` der Kandidat seiner ersten Wahl durch `preferences[i][0]` repräsentiert wird, der Kandidat seiner zweiten Wahl durch `preferences[i][1]`, usw. - Erinnern Sie sich daran, dass die `candidate` `struct` einen Member namens `eliminated` hat, der `true` ist, wenn der Kandidat von der Wahl ausgeschlossen wurde. - Erinnern Sie sich, dass die `candidate` `struct` einen Member namens `votes` hat, den Sie jeweils für den bevorzugten Kandidaten jedes Wählers aktualisieren müssen. - Denken Sie daran, dass sobald eine Stimme für den ersten nicht ausgeschlossenen Kandidaten eines Wählers gezählt wurde, die Auswertung des Stimmzettels dieses Wählers in diesem Durchgang beendet werden sollte. Sie können eine Schleife vorzeitig verlassen, indem Sie `break` innerhalb einer Bedingung verwenden. **Implementierung der `print_winner`-Funktion** - Erinnern Sie sich, dass `voter_count` die Gesamtzahl der Wähler in der Wahl speichert. Wie kann man also die Anzahl der Stimmen berechnen, die man braucht, um die Wahl zu gewinnen? **Implementierung der `find_min`-Funktion** - Sie werden wahrscheinlich über alle Kandidaten iterieren, um denjenigen zu finden, der noch im Rennen ist und die wenigsten Stimmen hat. Welche Inhalte der `candidate`-`struct` sind demnach von Bedeutung? **Implementierung der `is_tie`-Funktion** - Erinnern Sie sich daran, dass ein Unentschieden vorliegt, wenn jeder Kandidat, der noch in der Wahl ist, die gleiche Anzahl von Stimmen hat. Beachten Sie auch, dass die Funktion `is_tie` ein Argument `min` entgegennimmt, das die geringste Anzahl von Stimmen repräsentiert, die ein Kandidat derzeit hat. Wie könnten Sie `min` verwenden, um festzustellen, ob die Wahl unentschieden ist (oder umgekehrt, ob sie nicht unentschieden ist)? ## Testen Stellen Sie beim Testen Ihres Codes sicher, dass dieser mit folgenden Szenarien umgehen kann: - einer Wahl mit einer beliebigen Anzahl von Kandidaten (bis `MAX_CANDIDATES`, also `9`) - der Stimmabgabe für einen Kandidaten nach Namen - ungültigen Stimmen für Kandidaten, die nicht auf dem Stimmzettel stehen (das Programm sollte sich in diesem Fall beenden) - der Ausgabe des Gewinners der Wahl, wenn es nur einen gibt - einer Stimmengleichheit zwischen allen verbleibenden Kandidaten, so dass niemand ausgeschlossen wird und alle verbleibenden Kandidaten als Sieger ausgegeben werden ### Korrektheit Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen: ```bash check50 -l inf-zone/exercises/2026/runoff ``` ### Style Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit `style50` zu analysieren: ```bash style50 runoff.c ``` ## Abgeben Geben Sie im Ordner `runoff` ab: ```bash inf upload runoff ``` Danach sehen Sie, welche Tests Ihr Programm besteht und ob die Übung für die Bonuspunkte zählt. Wie Sie `inf` installieren und sich anmelden, steht unter [Abgeben mit `inf`](https://dev.inf.zone/faq/uebung-solutions/#inf-installieren). ## Zum Weiterlesen: Warum überhaupt Stichwahl? Für die Lösung der Aufgabe nicht nötig. Sie kennen bereits die Mehrheitswahl, bei der ein sehr einfacher Algorithmus zur Ermittlung des Wahlsiegers verwendet wird: Jeder Wähler hat eine Stimme und der Kandidat mit den meisten Stimmen gewinnt. Die Mehrheitswahl hat aber auch Nachteile. Was passiert zum Beispiel bei einer Wahl mit drei Kandidaten, wenn folgende Stimmzettel abgegeben werden? ![Fünf Stimmzettel, Gleichstand zwischen Alice und Bob](https://dev.inf.zone/exercises/05/runoff/./fptp_ballot_1.png) Eine Mehrheitswahl würde hier zu einem Gleichstand zwischen Alice und Bob führen, da jeder zwei Stimmen hat. Aber ist das das richtige Ergebnis? Es gibt noch eine andere Art von Wahlsystem, das so genannte Präferenzwahlsystem (auch bekannt als "ranked-choice"). Bei der Präferenzwahl können die Wähler für mehr als einen Kandidaten stimmen. Anstatt nur für ihren Spitzenkandidaten zu stimmen, können sie die Kandidaten in der Reihenfolge ihrer Präferenzen anordnen. Die Stimmzettel könnten also folgendermaßen aussehen: ![Fünf Stimmzettel, mit geordneten Präferenzen](https://dev.inf.zone/exercises/05/runoff/./ranked_ballot_1.png) In diesem Fall hat jeder Wähler nicht nur seinen Erstpräferenzkandidaten, sondern auch seine Zweit- und Drittpräferenz angegeben. Nun könnte es bei einer zuvor unentschiedenen Wahl einen Sieger geben. Ursprünglich gab es einen Gleichstand zwischen Alice und Bob; Charlie hat die wenigsten Stimmen und scheidet aus. Der Wähler, der Charlie gewählt hat, hat jedoch Alice gegenüber Bob bevorzugt, so dass Alice zum Sieger erklärt werden könnte. Durch die Angabe einer Stimmpräferenz kann ein weiterer potenzieller Nachteil der Mehrheitswahl behoben werden. Werfen Sie einen Blick auf die folgenden Stimmzettel – es sind dieselben wie im Beispiel oben: ![Neun Stimmzettel, mit geordneten Präferenzen](https://dev.inf.zone/exercises/05/runoff/./ranked_ballot_3.png) Wer sollte diese Wahl gewinnen? Bei einer Mehrheitswahl, bei der jeder Wähler nur seine erste Präferenz wählt, gewinnt Charlie die Wahl mit vier Stimmen gegenüber drei für Bob und zwei für Alice. Eine Mehrheit der Wähler (5 von 9) wäre jedoch mit Alice oder Bob anstelle von Charlie glücklicher. Ein Wahlsystem, das die Rangfolge der Präferenzen berücksichtigt, kann einen Sieger ermitteln, der die Präferenzen der Wähler besser widerspiegelt. Bei der integrierten Stichwahl gewinnt hier Bob. Eine Möglichkeit für ein solches Präferenzwahlsystem ist die integrierte Stichwahl (in Englisch _Instant-Runoff-Voting_). Dass nach jeder Runde der Letztplatzierte ausscheidet, hat einen einfachen Hintergrund: Im Prinzip wird damit simuliert, was passiert wäre, wenn der am wenigsten beliebte Kandidat gar nicht erst zur Wahl angetreten wäre. Das Verfahren ist etwas komplizierter als eine Mehrheitswahl, hat aber den Vorteil, dass der Sieger der Wahl die Präferenzen der Wähler genauer repräsentiert.