# Mehrheitswahl Quelle: https://dev.inf.zone/exercises/05/plurality/ ## Aufgabe **Auf einen Blick** - **Was:** Sie vervollständigen `plurality.c`, ein Programm, das eine Mehrheitswahl auswertet. - **Aufruf:** `./plurality Alice Bob Charlie` – die Kandidaten als Kommandozeilenargumente (höchstens 9). - **Eingabe:** zuerst die Zahl der Wählenden, dann für jede Person *einen* Namen (`Vote:`). - **Ausgabe:** der Name des Siegers – bei Gleichstand die Namen aller Kandidaten mit der höchsten Stimmenzahl, jeder in einer eigenen Zeile. - **Ungültige Stimme:** Steht der Name nicht auf dem Stimmzettel, gibt das Programm `Invalid vote.` aus; die Stimme zählt nicht, weiter geht es mit der nächsten Person. - **Ihre Arbeit:** die zwei Funktionen `vote` und `print_winner`. Alles andere in `plurality.c` bleibt unverändert. ### So funktioniert die Mehrheitswahl Jede Person gibt genau eine Stimme ab. Ausgewertet wird so: 1. **Zählen:** Jeder Stimmzettel zählt für den Kandidaten, dessen Name darauf steht. Ein Name, der nicht zur Wahl steht, ist ungültig und zählt für niemanden. 2. **Sieg:** Es gewinnt, wer die meisten Stimmen hat. Mehr als die Hälfte der Stimmen ist dafür nicht nötig. 3. **Gleichstand:** Haben mehrere Kandidaten die höchste Stimmenzahl, gewinnen alle gemeinsam. **Beispiel** mit 9 Stimmzetteln: | Anzahl | Stimme | | ------ | ------- | | 2 | Alice | | 3 | Bob | | 4 | Charlie | Charlie gewinnt mit 4 von 9 Stimmen, obwohl er nicht mehr als die Hälfte hat. Bei Alice 3, Bob 3, Charlie 3 gewännen alle drei gemeinsam. Wo die Mehrheitswahl an ihre Grenzen stößt, steht am Ende der Seite unter „Zum Weiterlesen“. ## Demo [Terminal-Aufzeichnung ansehen](https://asciinema.org/a/o2EXEqiz7iqfDB31wYxBOWjs8) ## 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/plurality.zip ``` aus, um eine ZIP-Datei namens `plurality.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 plurality.zip ``` aus, um das ZIP-Archiv in einen Ordner namens `plurality` zu extrahieren. Sie brauchen die ZIP-Datei nicht mehr, also können Sie ```bash rm plurality.zip ``` ausführen. Antworten Sie mit "y", gefolgt von der Eingabetaste, um die heruntergeladene ZIP-Datei zu entfernen. Führen Sie dann ```bash cd plurality ``` aus, um in dieses Verzeichnis zu wechseln. Ihre Eingabeaufforderung sollte nun wie folgt aussehen: ```bash plurality/ $ ``` Wenn alles funktioniert hat, sollten Sie nach dem Ausführen von ```bash ls ``` eine Datei mit dem Namen `plurality.c` sehen. Wenn Sie `code plurality.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 `plurality.c`** Wenn Sie die Funktionalität eines bestehenden Codes erweitern wollen, sollten Sie ihn zunächst in seinem jetzigen Zustand verstehen. Am Anfang der Datei legt `#define MAX 9` die Konstante `MAX` fest: die höchste Zahl an Kandidaten. Mit ihr wird das globale Array `candidates` angelegt, auf das jede Funktion zugreifen kann. ```c // Max number of candidates #define MAX 9 ``` ```c // Array of candidates candidate candidates[MAX]; ``` Ein `candidate` ist eine `struct` mit zwei Membern: `name` (ein `string`) und `votes` (ein `int`, die Zahl der Stimmen). ```c // Candidates have name and vote count typedef struct { string name; int votes; } candidate; ``` Die globale Variable `candidate_count` enthält die Zahl der Kandidaten. ```c // Number of candidates int candidate_count; ``` `main` kopiert die Kommandozeilenargumente in das Array `candidates` und setzt alle Stimmenzahlen auf `0`. Ohne Argument endet das Programm mit einer Usage-Meldung (Rückgabewert `1`), bei mehr als 9 Kandidaten mit `Maximum number of candidates is 9` (Rückgabewert `2`). ```c // Populate array of candidates candidate_count = argc - 1; if (candidate_count > MAX) { printf("Maximum number of candidates is %i\n", MAX); return 2; } for (int i = 0; i < candidate_count; i++) { candidates[i].name = argv[i + 1]; candidates[i].votes = 0; } ``` Dann fragt `main` nach der Zahl der Wählenden (`Number of voters: `), liest für jede Person einen Namen ein (`Vote: `) und ruft damit `vote` auf. Gibt `vote` den Wert `false` zurück, gibt `main` `Invalid vote.` aus. Zum Schluss ruft `main` die Funktion `print_winner` auf. Weiter unten stehen die beiden Funktionen, die Sie ausfüllen: ```c // Update vote totals given a new vote bool vote(string name) { // TODO return false; } // Print the winner (or winners) of the election void print_winner(void) { // TODO return; } ``` ## Spezifikation Ändern Sie in `plurality.c` nur die Funktionen `vote` und `print_winner` (zusätzliche Header-Dateien dürfen Sie einbinden). Wenn Ihr Ansatz nur mit einer Änderung an anderer Stelle funktioniert, überdenken Sie ihn. - **`vote(name)`:** Stimmt `name` genau mit dem Namen eines Kandidaten überein, erhöhen Sie dessen `votes` um 1 und geben `true` zurück. Sonst ändert sich nichts, und die Funktion gibt `false` zurück. Groß- und Kleinschreibung zählt: `alice` ist keine Stimme für `Alice`. Sie können davon ausgehen, dass keine zwei Kandidaten denselben Namen haben. - **`print_winner()`:** gibt den Namen des Kandidaten mit den meisten Stimmen aus, gefolgt von einem Zeilenumbruch. Haben mehrere Kandidaten die höchste Stimmenzahl, gibt sie jeden dieser Namen in einer eigenen Zeile aus. So sieht ein Lauf mit Gleichstand und einer ungültigen Stimme aus: ```text $ ./plurality Alice Bob Charlie Number of voters: 5 Vote: Alice Vote: Bob Vote: Alice Vote: Dave Invalid vote. Vote: Bob Alice Bob ``` ## Hilfestellung Klicken Sie auf die folgenden Tipps, um einige Ratschläge zu erhalten. Versuchen Sie aber zunächst, selbst so weit wie möglich zu kommen. **Implementierung der `vote`-Funktion** Eine Möglichkeit, dieses Problem anzugehen: 1. Iterieren über jeden Kandidaten 1. Prüfen, ob der Name des Kandidaten mit der Eingabe `name` übereinstimmt 1. Wenn ja, Stimmen dieses Kandidaten erhöhen und `true` zurückgeben 2. Wenn nein, weiter prüfen 2. Gab es nach der Prüfung aller Kandidaten keine Übereinstimmung, `false` zurückgeben Schreiben Sie diese Schritte als Pseudocode in die Datei und implementieren Sie sie dann der Reihe nach. ```c // Update vote totals given a new vote bool vote(string name) { // Iterate over each candidate // Check if candidate's name matches given name // If yes, increment candidate's votes and return true // If no match, return false } ``` Zwei Zeichenketten vergleichen Sie mit [`strcmp`](https://manual.cs50.io/3/strcmp), nicht mit `==`. **Implementierung der `print_winner`-Funktion** Vielleicht denken Sie zuerst an einen Sortieralgorithmus: die Kandidaten nach ihrer Stimmenzahl sortieren und dann den Spitzenkandidaten (oder die Spitzenkandidaten) ausgeben. Sortieren ist aber aufwendig: Selbst [Merge Sort](https://dev.inf.zone/lectures/3-algorithmen/short-3-6-merge-sort/), einer der schnellsten Sortieralgorithmen, läuft in \(O(N \log N)\). Eigentlich brauchen Sie nur zwei Informationen: 1. die höchste Stimmenzahl unter den Kandidaten, 2. den Kandidaten (oder die Kandidaten) mit dieser Stimmenzahl. Eine gute Lösung kommt daher mit zwei Durchläufen über das Array aus (jeweils \(O(N)\)): ```c // Print the winner (or winners) of the election void print_winner(void) { // Find the maximum number of votes // Print the candidate (or candidates) with maximum votes } ``` Den konkreten Code überlassen wir Ihnen! ## Testen Stellen Sie beim Testen Ihres Codes sicher, dass dieser mit folgenden Szenarien umgehen kann: - einer Wahl mit einer beliebigen Anzahl von Kandidaten (bis zum `MAX` von `9`) - der Stimmabgabe für einen Kandidaten nach Namen - ungültigen Stimmen für Kandidaten, die nicht auf dem Stimmzettel stehen (das Programm gibt `Invalid vote.` aus und macht mit der nächsten Person weiter) - der Ausgabe des Gewinners der Wahl, wenn es nur einen gibt - der Ausgabe der Gewinner der Wahl (jeweils in einer eigenen Zeile), wenn es mehrere gibt ### 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/plurality ``` ### Style Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit `style50` zu analysieren: ```bash style50 plurality.c ``` ## Abgeben Geben Sie im Ordner `plurality` ab: ```bash inf upload plurality ``` 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: Wahlverfahren Für die Lösung der Aufgabe nicht nötig. Wahlen gibt es in allen Formen und Größenordnungen. Im Vereinigten Königreich wird der [Premierminister](https://www.parliament.uk/education/about-your-parliament/general-elections/) offiziell vom Monarchen ernannt, der in der Regel den Führer der politischen Partei wählt, die die meisten Sitze im Unterhaus gewinnt. In den Vereinigten Staaten gibt es ein mehrstufiges [Electoral College](https://www.archives.gov/federal-register/electoral-college/about.html), in dem die Bürger darüber abstimmen, wie die einzelnen Bundesstaaten die Wahlmänner verteilen sollen, die dann den Präsidenten wählen. Die Mehrheitswahl (auch „Pluralitätswahl“, englisch *plurality*, *first-past-the-post* oder *winner take all*) ist wohl die einfachste Art, eine Wahl abzuhalten. Sie hat aber einen Haken: Im Beispiel oben gewinnt Charlie mit 4 von 9 Stimmen, obwohl die Mehrheit (5 von 9) jemand anderen gewählt hat. Die [integrierte Stichwahl](https://dev.inf.zone/exercises/05/runoff/) berücksichtigt deshalb auch die weiteren Präferenzen der Wählenden – im Beispiel dort (dieselben ersten Präferenzen) gewinnt Bob, weil die zwei Stimmen für Alice an ihre 2. Präferenz Bob gehen.