Mehrheitswahl

Ö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:

$

Geben Sie dann

wget https://inf.zone/download/exercises/03/plurality.zip

ein und führen Sie den Befehl mit der Eingabetaste 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

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

rm plurality.zip

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

Führen Sie dann

cd plurality

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

plurality/ $

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

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!

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 der Datei an. Die Zeile #define MAX 9 bedeutet, dass MAX eine Konstante ist (gleich 9), die im gesamten Programm verwendet werden kann. Hier steht sie für die maximale Anzahl von Kandidaten, die eine Wahl haben kann.

// Max number of candidates
#define MAX 9

Diese Konstante wird in plurality.c verwendet, um ein globales Array zu definieren - also ein Array, auf das jede Funktion zugreifen kann.

// Array of candidates
candidate candidates[MAX];

Aber was ist in diesem Fall ein candidate? In plurality.c ist ein candidate eine struct. Jeder candidate hat zwei Member: einen string namens name, der den Namen des Kandidaten enthält, und einen int namens votes, in dem die Anzahl der Stimmen gespeichert werden, die der Kandidat hat.

// Candidates have name and vote count
typedef struct
{
    string name;
    int votes;
}
candidate;

Werfen wir nun einen Blick auf die main-Funktion. Finden Sie die Stelle, an der das Programm eine globale Variable candidate_count setzt, die die Anzahl der Kandidaten bei der Wahl angibt?

// Number of candidates
int candidate_count;

Was ist mit der Stelle, an der die Befehlszeilenargumente in das Array candidates kopiert werden?

// 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;
}

Und wo wird der Benutzer aufgefordert, die Anzahl der Wähler einzugeben?

int voter_count = get_int("Number of voters: ");

Danach lässt das Programm jeden Wähler eine Stimme eingeben und ruft die Funktion vote für den jeweils gewählten Kandidaten auf. Schließlich ruft main die Funktion print_winner auf, um den (oder die) Gewinner der Wahl auszugeben.

Wenn Sie weiter unten in der Datei nachsehen, werden Sie feststellen, dass die Funktionen vote und print_winner leer geblieben sind.

// 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;
}

Dieser Teil soll von Ihnen selbst vervollständigt werden!

Zusätzlicher Hinweis: Sie sollten nichts in plurality.c ändern, außer den Implementierungen der Funktionen vote und print_winner. Überdenken Sie stattdessen Ihren Lösungsansatz, falls dieser nur mit einer Änderung an einer anderen Stelle im Code funktioniert.

Was gibt es bei der vote-Funktion zu beachten?

• Die Signatur von vote, bool vote(string name), zeigt, dass diese genau ein Argument entgegennimmt, einen string namens name, das den Namen des Kandidaten enthält, für den gestimmt wurde.
• vote sollte einen bool zurückgeben, wobei true bedeutet, dass eine Stimme erfolgreich abgegeben wurde (d.h. der übergebene Name stimmt mit dem Namen eines Kandidaten überein) und false, dass dies nicht der Fall war.

Eine Möglichkeit, dieses Problem anzugehen, ist die folgende:

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ückgegeben
      2. Wenn nein, weiter prüfen
2. Gab es keine Übereinstimmung nach der Prüfung aller Kandidaten, wird false zurückgegeben

Schreiben Sie diese Schritte als Pseudocode in die Datei und implementieren Sie sie dann der Reihe nach.

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

Die Implementation in Code überlassen wir allerdings Ihnen!

Ein paar Hilfestellungen zur Vervollständigen der print_winner-Funktion:

• Die Funktion sollte den Namen des Kandidaten ausgeben, der bei der Wahl die meisten Stimmen erhalten hat, gefolgt von einem Zeilenumbruch.
• Die Wahl kann unentschieden ausgehen, wenn mehrere Kandidaten jeweils die Höchstzahl der Stimmen erhalten haben. In diesem Fall sollten Sie die Namen dieser Kandidaten jeweils in einer eigenen Zeile ausgeben.

Vielleicht denken Sie zur Lösung des Problems zuerst an einen Sortieralgorithmus: Die Kandidaten nach ihrer Stimmenzahl sortieren und dann den Spitzenkandidaten (oder die Spitzenkandidaten) ausgeben. Bedenken Sie jedoch, dass das Sortieren komplex sein kann: Selbst Merge Sort, einer der schnellsten Sortieralgorithmen, läuft in $O(N \space log(N))$.

Bedenken Sie, dass Sie zur Lösung dieses Problems im Grunde nur zwei Informationen benötigen:

1. Die Höchstzahl der Stimmen unter den Kandidaten.
2. Der Kandidat (oder die Kandidaten) mit dieser Anzahl an Stimmen.

Eine gute Lösung würde daher höchstens zwei Suchvorgänge (jeweils $O(N)$) erfordern.

Schreiben wir einen Pseudocode, um die beiden benötigten Suchvorgänge festzuhalten:

// 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 aber Ihnen!