Integrierte Stichwahl

Öffnen Sie VS Code entsprechend Ihrem Setup.

Öffnen Sie Ihr Terminalfenster und führen Sie dann cd aus. Die Eingabeaufforderung Ihres Terminalfensters sollte wie folgt aussehen:

$

Führen Sie dann

wget https://inf.zone/download/exercises/03/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

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

rm runoff.zip

ausführen. Antworten Sie mit “y”, gefolgt von der Eingabetaste, um die heruntergeladene ZIP-Datei zu entfernen.

Führen Sie dann

cd runoff

aus, um in dieses Verzeichnis zu wechseln. Ihre Eingabeaufforderung sollte nun wie folgt aussehen:

runoff/ $

Wenn alles funktioniert hat, sollten Sie nach dem Ausführen von

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!

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.

// 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.

// 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.

// 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.

// 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.

// 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.

• Die Funktion nimmt drei Argumente entgegen: voter, rank und name.
• Wenn name mit dem Namen eines gültigen Kandidaten übereinstimmt, muss das globale Präferenzen-Array aktualisiert werden, um zu speichern, dass der Wähler voter diesen Kandidaten als seine rank-Präferenz hat. Denken Sie daran, dass 0 die erste Präferenz ist, 1 die zweite Präferenz, usw. Sie können davon ausgehen, dass keine zwei Kandidaten den gleichen Namen haben.
• Wenn die Präferenz erfolgreich gespeichert wurde, sollte die Funktion true zurückgeben. Andernfalls sollte die Funktion false zurückgeben. Dies sollte beispielsweise der Fall sein, wenn name nicht der Name eines der Kandidaten ist.

Beachten Sie beim Schreiben Ihres Codes zudem folgende Hinweise:

• Erinnern Sie sich, dass candidate_count die Gesamtzahl der Kandidaten für die Wahl speichert.
• Erinnern Sie sich daran, dass Sie 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.

• Die Funktion sollte die Anzahl der votes aktualisieren, die jeder Kandidat in dieser Phase der Stichwahl hat.
• In jeder Phase der Stichwahl stimmt jeder Wähler für den von ihm bevorzugten Kandidaten, der noch nicht ausgeschieden ist.

Beachten Sie beim Schreiben Ihres Codes zudem folgende Hinweise:

• 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, das true ist, wenn der Kandidat von der Wahl ausgeschlossen wurde.
• Erinnern Sie sich, dass die candidate struct einen Member namens votes hat, das 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.

• Wenn ein Kandidat mehr als die Hälfte der Stimmen hat, sollte sein Name ausgegeben werden und die Funktion sollte true zurückgeben.
• Wenn noch niemand die Wahl gewonnen hat, sollte die Funktion false zurückgeben.

Beachten Sie beim Schreiben Ihres Codes diesen Hinweis:

• 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?

• Die Funktion sollte die geringste Stimmenzahl unter allen Kandidaten zurückgeben, die noch nicht von der Wahl ausgeschlossen wurden.

Beachten Sie beim Schreiben Ihres Codes diesen Hinweis:

• 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?

• Die Funktion nimmt ein Argument min entgegen, das die aktuell geringste Anzahl an Stimmen unter allen Kandidaten der Wahl angibt.
• Die Funktion sollte true zurückgeben, wenn jeder Kandidat, der noch im Rennen ist, die gleiche Anzahl an Stimmen hat, und sollte andernfalls false zurückgeben.

Beachten Sie beim Schreiben Ihres Codes diesen Hinweis:

• 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)?

• Die Funktion nimmt ein Argument min entgegen, das die geringste Anzahl an Stimmen unter allen noch verbleibenden Kandidaten der Wahl repräsentiert.
• Die Funktion sollte alle Kandidaten als ausgeschlossen kennzeichnen, deren Anzahl an Stimmen dem Wert von min entspricht.