Mehrheitswahl

Öffnen Sie VS CodeVisual Studio Code, der kostenlose Code-Editor von Microsoft, in dem Sie im Kurs programmieren. Glossar → entsprechend Ihrem Setup.

Öffnen Sie Ihr TerminalfensterFenster, in dem Sie dem Computer Befehle als Text eintippen statt zu klicken. In VS Code liegt es im unteren Bereich des Fensters. Glossar → und führen Sie dann cdWechselt das Verzeichnis: cd me geht in den Ordner me, cd .. eine Ebene nach oben, cd allein ins Homeverzeichnis. Glossar → aus. Die EingabeaufforderungDas Zeichen am Anfang der Zeile im Terminal, etwa $ oder me/ $. Es zeigt, dass das Terminal auf Ihren nächsten Befehl wartet. Steht davor ein Ordnername wie me/, befinden Sie sich gerade in diesem Ordner. Glossar → Ihres Terminalfensters sollte wie folgt aussehen:

$

Führen Sie dann

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 wgetLädt eine Datei aus dem Internet in das aktuelle Verzeichnis herunter, im Kurs zum Beispiel das Aufgabenmaterial einer Übung. Glossar → 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.

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.

// Max number of candidates
#define MAX 9

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

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

Die globale Variable candidate_count enthält die Zahl der Kandidaten.

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

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

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

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.

// 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, nicht mit ==.

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, 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)$):

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