(2022年) CS50 week3

其實之前就已經修完 CS50 了，不過因應 2022 年將課堂作業的系統
從 c9.io 換到 github codespace + vscode 整合
打算來重溫一下裡面的作業，並暖身一下 C 語言的手感

由於已經有許多前輩分享課程與作業的心得
加上官網教材的投影片、重點筆記、教學影片都非常完整
故不再做詳細的紀錄，專注在作業 (Lab, Problem sets) 上面

https://cs50.harvard.edu/x/2022/weeks/3/

---

Lab3： Sort

解答：

sort1 uses: bubble sort
How do you know? : used least times is best case, but other case is long time

sort2 uses: merge sort
How do you know? : in any case, used least times

sort3 uses: selection sort
How do you know? : in any case, used largest times

(點擊展開) 操作記錄

– Time Complexity Table –

type	Best	Worst.	Average
selection sort	Ω(N²)	θ(N²)	O(N²)
bubble sort	Ω(N)	θ(N²)	O(N²)
merge sort	Ω(N ㏒ᴺ)	θ(N ㏒ᴺ)	O(N ㏒ᴺ)

– Compares –-

random (avg case)

type	5000	10000	50000
sort1	0.064s	0.259s	7.227s
sort2	0.005s	0.007s	0.020s
sort3	0.031s	0.192s	2.881s

reversed (worst case)

type	5000	10000	50000
sort1	0.068s	0.211s	5.503s
sort2	0.005s	0.007s	0.021s
sort3	0.030s	0.114s	2.847s

sorted (best case)

type	5000	10000	50000
sort1	0.009s	0.013s	0.013s
sort2	0.006s	0.006s	0.006s
sort3	0.031s	0.114s	2.898s

– Records –-

random5000
time ./sort1 random5000.txt => 0m0.064s
time ./sort2 random5000.txt => 0m0.005s
time ./sort3 random5000.txt => 0m0.031s

random10000
time ./sort1 random10000.txt => 0m0.259s
time ./sort2 random10000.txt => 0m0.007s
time ./sort3 random10000.txt => 0m0.192s

random50000
time ./sort1 random50000.txt => 0m7.227s
time ./sort2 random50000.txt => 0m0.020s
time ./sort3 random50000.txt => 0m2.881s

---

reversed5000
time ./sort1 reversed5000.txt => 0m0.068s
time ./sort2 reversed5000.txt => 0m0.005s
time ./sort3 reversed5000.txt => 0m0.030s

reversed10000
time ./sort1 reversed10000.txt => 0m0.211s
time ./sort2 reversed10000.txt => 0m0.007s
time ./sort3 reversed10000.txt => 0m0.114s

reversed50000
time ./sort1 reversed50000.txt => 0m5.503s
time ./sort2 reversed50000.txt => 0m0.021s
time ./sort3 reversed50000.txt => 0m2.847s

---

sorted5000
time ./sort1 sorted5000.txt => 0m0.009s
time ./sort2 sorted5000.txt => 0m0.006s
time ./sort3 sorted5000.txt => 0m0.031s

sorted10000
time ./sort1 sorted10000.txt => 0m0.013s
time ./sort2 sorted10000.txt => 0m0.006s
time ./sort3 sorted10000.txt => 0m0.114s

sorted50000
time ./sort1 sorted50000.txt => 0m0.013s
time ./sort2 sorted50000.txt => 0m0.016s
time ./sort3 sorted50000.txt => 0m2.898s

---

作業： Plurality

(點擊展開) 符合 style50 風格的程式碼

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max number of candidates
#define MAX 9

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

// Array of candidates
candidate candidates[MAX];

// Number of candidates
int candidate_count;

// Function prototypes
bool vote(string name);
void print_winner(void);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: plurality [candidate ...]\n");
        return 1;
    }

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

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

    // Loop over all voters
    for (int i = 0; i < voter_count; i++)
    {
        string name = get_string("Vote: ");

        // Check for invalid vote
        if (!vote(name))
        {
            printf("Invalid vote.\n");
        }
    }

    // Display winner of election
    print_winner();
}

// Update vote totals given a new vote
bool vote(string name)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0)
        {
            valid_name = true;
            candidates[i].votes++;
        }
    }

    return valid_name;
}

// Print the winner (or winners) of the election
void print_winner(void)
{
    int max_votes = 0;

    // search max votes in all candidates
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes > max_votes)
        {
            max_votes = candidates[i].votes;
        }
    }

    // print candidates that have max_votes
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes == max_votes)
        {
            printf("%s\n", candidates[i].name);
        }
    }

    return ;
}

–

(點擊展開) 個人覺得比較好讀的程式碼風格

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max number of candidates
#define MAX 9

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

// Array of candidates
candidate candidates[MAX];

// Number of candidates
int candidate_count;

// Function prototypes
bool vote(string name);
void print_winner(void);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2) {
        printf("Usage: plurality [candidate ...]\n");
        return 1;
    }

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

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

    // Loop over all voters
    for (int i = 0; i < voter_count; i++) {
        string name = get_string("Vote: ");
        // Check for invalid vote
        if (!vote(name))
            printf("Invalid vote.\n");
    }

    // Display winner of election
    print_winner();
}

// Update vote totals given a new vote
bool vote(string name)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++) {
        if (strcmp(candidates[i].name, name) == 0) {
            valid_name = true;
            candidates[i].votes++;
        }
    }

    return valid_name;
}

// Print the winner (or winners) of the election
void print_winner(void)
{
    int max_votes = 0;

    // search max votes in all candidates
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes > max_votes)
            max_votes = candidates[i].votes;
    }

    // print candidates that have max_votes
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes == max_votes)
            printf("%s\n", candidates[i].name);
    }

    return ;
}

–

執行

驗證

---

作業： Runoff

(點擊展開) 符合 style50 風格的程式碼

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

// Candidates have name, vote count, eliminated status
typedef struct
{
    string name;
    int votes;
    bool eliminated;
}
candidate;

// Array of candidates
candidate candidates[MAX_CANDIDATES];

// Numbers of voters and candidates
int voter_count;
int candidate_count;

// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: runoff [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX_CANDIDATES)
    {
        printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i].name = argv[i + 1];
        candidates[i].votes = 0;
        candidates[i].eliminated = false;
    }

    voter_count = get_int("Number of voters: ");
    if (voter_count > MAX_VOTERS)
    {
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
        return 3;
    }

    // Keep querying for votes
    for (int i = 0; i < voter_count; i++)
    {

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            // Record vote, unless it's invalid
            if (!vote(i, j, name))
            {
                printf("Invalid vote.\n");
                return 4;
            }
        }

        printf("\n");
    }

    // Keep holding runoffs until winner exists
    while (true)
    {
        // Calculate votes given remaining candidates
        tabulate();

        // Check if election has been won
        bool won = print_winner();
        if (won)
        {
            break;
        }

        // Eliminate last-place candidates
        int min = find_min();
        bool tie = is_tie(min);

        // If tie, everyone wins
        if (tie)
        {
            for (int i = 0; i < candidate_count; i++)
            {
                if (!candidates[i].eliminated)
                {
                    printf("%s\n", candidates[i].name);
                }
            }
            break;
        }

        // Eliminate anyone with minimum number of votes
        eliminate(min);

        // Reset vote counts back to zero
        for (int i = 0; i < candidate_count; i++)
        {
            candidates[i].votes = 0;
        }
    }
    return 0;
}

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0)
        {
            valid_name = true;
            // Record the voter and rank with candidate_index
            preferences[voter][rank] = i;
        }
    }

    return valid_name;
}

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // counting by each votes
    for (int i = 0; i < voter_count; i++)
    {
        // counting by each rank
        for (int j = 0; j < candidate_count; j++)
        {
            int candidate_index = preferences[i][j];
            // if candidate is not eliminated, counting votes
            if (candidates[candidate_index].eliminated == false)
            {
                candidates[candidate_index].votes++;
                break;
            }
        }
    }

    return;
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // have to be majority (more than 50%)
    int majority = (voter_count / 2) + 1;
    bool has_winner = false;

    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes >= majority)
        {
            has_winner = true;
            printf("%s\n", candidates[i].name);
        }
    }

    return has_winner;
}

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min_votes = voter_count;

    // find minimum votes
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes < min_votes && candidates[i].eliminated == false)
        {
            min_votes = candidates[i].votes;
        }
    }

    return min_votes;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    int max_votes = 0;
    int max_votes_candidates_count = 0;
    int uneliminated_candidates_count = 0;
    string max_votes_candidates[candidate_count];

    bool have_tie = false;

    // find maximum votes
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes > max_votes && candidates[i].eliminated == false)
        {
            max_votes = candidates[i].votes;
        }
    }

    // count have max_votes candidates name
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated == false)
        {
            uneliminated_candidates_count ++;

            if (candidates[i].votes == max_votes)
            {
                max_votes_candidates[i] = candidates[i].name;
                max_votes_candidates_count++;
            }
        }
    }

    // condition have_tie
    if (max_votes_candidates_count > 1 && max_votes_candidates_count == uneliminated_candidates_count)
    {
        have_tie = true;
    }

    return have_tie;
}

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes == min)
        {
            candidates[i].eliminated = true;
        }
    }
    return;
}

–

(點擊展開) 個人覺得比較好讀的程式碼風格

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

// Candidates have name, vote count, eliminated status
typedef struct {
    string name;
    int votes;
    bool eliminated;
} candidate;

// Array of candidates
candidate candidates[MAX_CANDIDATES];

// Numbers of voters and candidates
int voter_count;
int candidate_count;

// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2) {
        printf("Usage: runoff [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX_CANDIDATES) {
        printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
        return 2;
    }

    for (int i = 0; i < candidate_count; i++) {
        candidates[i].name = argv[i + 1];
        candidates[i].votes = 0;
        candidates[i].eliminated = false;
    }

    voter_count = get_int("Number of voters: ");
    if (voter_count > MAX_VOTERS) {
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
        return 3;
    }

    // Keep querying for votes
    for (int i = 0; i < voter_count; i++) {

        // Query for each rank
        for (int j = 0; j < candidate_count; j++) {
            string name = get_string("Rank %i: ", j + 1);
            // Record vote, unless it's invalid
            if (!vote(i, j, name)) {
                printf("Invalid vote.\n");
                return 4;
            }
        }

        printf("\n");
    }

    // Keep holding runoffs until winner exists
    while (true)
    {
        // Calculate votes given remaining candidates
        tabulate();

        // Check if election has been won
        bool won = print_winner();
        if (won)
            break;

        // Eliminate last-place candidates
        int min = find_min();
        bool tie = is_tie(min);

        // If tie, everyone wins
        if (tie) {
            for (int i = 0; i < candidate_count; i++) {
                if (!candidates[i].eliminated)
                    printf("%s\n", candidates[i].name);
            }
            break;
        }

        // Eliminate anyone with minimum number of votes
        eliminate(min);

        // Reset vote counts back to zero
        for (int i = 0; i < candidate_count; i++)
            candidates[i].votes = 0;
    }
    return 0;
}

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    bool valid_name = false;
    for (int i = 0; i < candidate_count; i++) {
        if (strcmp(candidates[i].name, name) == 0) {
            valid_name = true;
            // Record the voter and rank with candidate_index
            preferences[voter][rank] = i;
        }
    }

    return valid_name;
}

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // counting by each votes
    for (int i = 0; i < voter_count; i++) {
        // counting by each rank
        for (int j = 0; j < candidate_count; j++) {
            int candidate_index = preferences[i][j];
            // if candidate is not eliminated, counting votes
            if (candidates[candidate_index].eliminated == false) {
                candidates[candidate_index].votes++;
                break;
            }
        }
    }

    return;
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // have to be majority (more than 50%)
    int majority = (voter_count / 2) + 1;
    bool has_winner = false;

    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes >= majority) {
            has_winner = true;
            printf("%s\n", candidates[i].name);
        }
    }

    return has_winner;
}

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min_votes = voter_count;

    // find minimum votes
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes < min_votes && candidates[i].eliminated == false)
            min_votes = candidates[i].votes;
    }

    return min_votes;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    int max_votes = 0;
    int max_votes_candidates_count = 0;
    int uneliminated_candidates_count = 0;
    string max_votes_candidates[candidate_count];

    bool have_tie = false;

    // find maximum votes
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes > max_votes && candidates[i].eliminated == false)
            max_votes = candidates[i].votes;
    }

    // count have max_votes candidates name
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].eliminated == false) {
            uneliminated_candidates_count ++;

            if (candidates[i].votes == max_votes) {
                max_votes_candidates[i] = candidates[i].name;
                max_votes_candidates_count++;
            }
        }
    }

    // condition have_tie
    if (max_votes_candidates_count > 1 && max_votes_candidates_count == uneliminated_candidates_count)
        have_tie = true;

    return have_tie;
}

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes == min)
            candidates[i].eliminated = true;
    }
    return;
}

–

執行

驗證

---

作業： Tideman

(點擊展開) 符合 style50 風格的程式碼

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// Each pair has a winner, loser
typedef struct
{
    int winner;
    int loser;
}
pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];
// e.g. if have 3 candidates, all pairs will be `3 * (3-1) / 2` = 3
// it will map on record_preferences() and add_pairs()

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);

void sort(int array[], int start, int end);
void merge(int array[], int start, int middle, int end);
bool has_cycle(int winner, int loser);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    // 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] = argv[i + 1];
    }

    // Clear graph of locked in pairs
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

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

    // Query for votes
    for (int i = 0; i < voter_count; i++)
    {
        // candiates = [1: Alice, 2: Bob, 3: Charlie]

        // ranks[i] is voter's ith preference
        int ranks[candidate_count];
        // e.g. ranks[3]

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }
        // e.g. a ballot content is 1st: Alice, 2nd: Charlie, 3rd: Bob
        // => ranks = [1, 3, 2]

        record_preferences(ranks);

        printf("\n");
    }
    // if we have 5 ballots
    // after all ballots run record updated,
    // each ballot content:

    //     Alice
    //     Charlie
    //     Bob

    //     Alice
    //     Charlie
    //     Bob

    //     Bob
    //     Charlie
    //     Alice

    //     Bob
    //     Charlie
    //     Alice

    //     Charlie
    //     Alice
    //     Bob

    // preferences will be:
    //     preferences[0](alice)    == [0, 3, 2]
    //     preferences[1](Bob)      == [2, 0, 2]
    //     preferences[2](Charlie)  == [3, 3, 0]


    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    for (int c_index = 0; c_index < candidate_count; c_index++)
    {
        // if name match, insert candidates to ranks
        if (strcmp(name, candidates[c_index]) == 0)
        {
            ranks[rank] = c_index;
            return true;
        }
    }

    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    int a_candiate_index = 0;
    int b_candiate_index = 0;
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            // if only 3 candiates, it loop will be:
            // i: 0, j: 1 (rank0 v.s rank1)
            // i: 0, j: 2 (rank0 v.s rank2)
            // i: 1, j: 2 (rank1 v.s rank2)

            // if
            //    candiates = [1: Alice, 2: Bob, 3: Charlie]
            //    ranks = [0, 2, 1]
            //
            // it means:
            //    Alice > Charlie
            //    Alice > Bob
            //    Charlie > Bob
            //
            // so preferences will be:
            //    preferences[0](alice)   == [0, 1, 1]
            //    preferences[1](Bob)     == [0, 0, 0]
            //    preferences[2](Charlie) == [0, 1, 0]


            // find candiate_index in compare a, b
            a_candiate_index = ranks[i];
            b_candiate_index = ranks[j];
            // printf("i: %i, j: %i\n", i, j);
            // printf("a_candiate: %i - %s\n b_candiate: %i - %s\n", a_candiate_index, candidates[a_candiate_index], b_candiate_index, candidates[b_candiate_index]);

            // record who win this compare
            preferences[a_candiate_index][b_candiate_index]++;
        }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // like record_preferences(), we need couting each pair's winner and loser
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            // if only 3 candiates, it loop will be:
            // i: 0, j: 1
            // i: 0, j: 2
            // i: 1, j: 2
            // => pair_count will be 3

            // i is a_candidate_index
            // j is b_candidate_index
            int comparison_1 = preferences[i][j];
            int comparison_2 = preferences[j][i];

            // if candiates = [1: Alice, 2: Bob, 3: Charlie]
            // if a preferences is:
            //     preferences[0](alice)    == [0, 3, 2]
            //     preferences[1](Bob)      == [2, 0, 2]
            //     preferences[2](Charlie)  == [3, 3, 0]

            // we will insert each pairs winner and loser
            // e.g. in first loop: i == 0(alice), b == 1(Bob)
            // comparison_1 = preferences[0][1] => is 3
            // comparison_2 = preferences[1][0] => is 2
            // so we can figure out winner is Alice, loser is Bob in this pair

            if (comparison_1 > comparison_2)
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (comparison_1 < comparison_2)
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
        }
    }

    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    // if candiates = [1: Alice, 2: Bob, 3: Charlie]
    // if a preferences is:
    //     preferences[0](alice)    == [0, 3, 2]
    //     preferences[1](Bob)      == [2, 0, 2]
    //     preferences[2](Charlie)  == [3, 3, 0]

    // if pairs is:
    //     pairs[0](1st) => winner: 0(Alice),   loser: 1(Bob)
    //     pairs[1](2nd) => winner: 2(Charlie), loser: 0(Alice)
    //     pairs[2](3rd) => winner: 2(Charlie), loser: 1(Bob)

    // result will be [1, 1, 1]

    int strength_array[pair_count];
    int winner;
    int loser;

    for (int i = 0; i < pair_count; i++)
    {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        strength_array[i] = preferences[winner][loser] - preferences[loser][winner];
    }

    // desc sort
    sort(strength_array, 0, pair_count - 1);
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int winner;
    int loser;
    for (int i = 0; i < pair_count; i++)
    {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        if (!has_cycle(winner, loser))
        {
            locked[winner][loser] = true;
        }
    }

    return;
}

// Print the winner of the election
void print_winner(void)
{
    int i = 0;
    int j = 0;
    bool edge;
    while (i < candidate_count)
    {
        edge = locked[j][i];
        if (j == candidate_count && !edge)
        {
            printf("%s\n", candidates[i]);
            break;
        }
        else if (!edge)
        {
            j++;
        }
        else
        {
            i++;
            j = 0;
        }
    }
}

void sort(int array[], int start, int end)
{
    if (end > start)
    {
        int middle = (start + end) / 2;

        sort(array, start, middle);
        sort(array, middle + 1, end);

        merge(array, start, middle, end);
    }
}

void merge(int array[], int start, int middle, int end)
{
    int i = start;
    int j = middle + 1;
    int k = 0;

    typedef struct
    {
        int winner;
        int loser;
    } pair_temp;

    pair_temp pairs_temp[pair_count];

    while (i <= middle && j <= end)
    {
        if (array[i] >= array[j])
        {
            pairs_temp[k].winner = pairs[i].winner;
            pairs_temp[k].loser = pairs[i].loser;
            i++;
            k++;
        }
        else
        {
            pairs_temp[k].winner = pairs[j].winner;
            pairs_temp[k].loser = pairs[j].loser;
            j++;
            k++;
        }
    }

    while (i <= middle)
    {
        pairs_temp[k].winner = pairs[i].winner;
        pairs_temp[k].loser = pairs[i].loser;
        i++;
        k++;
    }

    while (j <= end)
    {
        pairs_temp[k].winner = pairs[j].winner;
        pairs_temp[k].loser = pairs[j].loser;
        j++;
        k++;
    }
    for (i = start; i <= end; i++)
    {
        pairs[i].winner = pairs_temp[i - start].winner;
        pairs[i].loser = pairs_temp[i - start].loser;
    }
}

bool has_cycle(int winner, int loser)
{
    if (locked[loser][winner] == true)
    {
        return true;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[i][winner] == true)
        {
            return has_cycle(i, loser);
        }
    }
    return false;
}

–

(點擊展開) 個人覺得比較好讀的程式碼風格

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// Each pair has a winner, loser
typedef struct {
    int winner;
    int loser;
} pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];
// e.g. if have 3 candidates, all pairs will be `3 * (3-1) / 2` = 3
// it will map on record_preferences() and add_pairs()

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);

void sort(int array[], int start, int end);
void merge(int array[], int start, int middle, int end);
bool has_cycle(int winner, int loser);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2) {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    // 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] = argv[i + 1];

    // Clear graph of locked in pairs
    for (int i = 0; i < candidate_count; i++) {
        for (int j = 0; j < candidate_count; j++)
            locked[i][j] = false;
    }

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

    // Query for votes
    for (int i = 0; i < voter_count; i++) {
        /* sample: candiates = [1: Alice, 2: Bob, 3: Charlie] */

        // ranks[i] is voter's ith preference
        int ranks[candidate_count];
        /* e.g. ranks[3] */

        // Query for each rank
        for (int j = 0; j < candidate_count; j++) {
            string name = get_string("Rank %i: ", j + 1);

            if (!vote(j, name, ranks)) {
                printf("Invalid vote.\n");
                return 3;
            }
        }
        /* 
            e.g. a ballot content is 1st: Alice, 2nd: Charlie, 3rd: Bob
            => ranks = [1, 3, 2]
         */        
        record_preferences(ranks);

        printf("\n");
    }
    
    /* 
        if we have 5 ballots
        after all ballots run record updated,
        each ballot content:

            Alice
            Charlie
            Bob

            Alice
            Charlie
            Bob

            Bob
            Charlie
            Alice

            Bob
            Charlie
            Alice

            Charlie
            Alice
            Bob

        preferences will be:
            preferences[0](alice)    == [0, 3, 2]
            preferences[1](Bob)      == [2, 0, 2]
            preferences[2](Charlie)  == [3, 3, 0]    
     */

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    for (int c_index = 0; c_index < candidate_count; c_index++) {
        // if name match, insert candidates to ranks
        if (strcmp(name, candidates[c_index]) == 0) {
            ranks[rank] = c_index;
            return true;
        }
    }

    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    int a_candiate_index = 0;
    int b_candiate_index = 0;
    for (int i = 0; i < candidate_count; i++) {
        for (int j = i + 1; j < candidate_count; j++) {
            /* 
                if only 3 candiates, it loop will be:
                i: 0, j: 1 (rank0 v.s rank1)
                i: 0, j: 2 (rank0 v.s rank2)
                i: 1, j: 2 (rank1 v.s rank2)

                if
                candiates = [1: Alice, 2: Bob, 3: Charlie]
                ranks = [0, 2, 1]
                
                it means:
                Alice > Charlie
                Alice > Bob
                Charlie > Bob
                
                so preferences will be:
                preferences[0](alice)   == [0, 1, 1]
                preferences[1](Bob)     == [0, 0, 0]
                preferences[2](Charlie) == [0, 1, 0]            
             */

            // find candiate_index in compare a, b
            a_candiate_index = ranks[i];
            b_candiate_index = ranks[j];

            // record who win this compare
            preferences[a_candiate_index][b_candiate_index]++;
        }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // like record_preferences(), we need couting each pair's winner and loser
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            /* 
                if only 3 candiates, it loop will be:
                i: 0, j: 1
                i: 0, j: 2
                i: 1, j: 2
                => pair_count will be 3
             */

            // i is a_candidate_index
            // j is b_candidate_index
            int comparison_1 = preferences[i][j];
            int comparison_2 = preferences[j][i];

            /* 
                if candiates = [1: Alice, 2: Bob, 3: Charlie]
                if a preferences is:
                    preferences[0](alice)    == [0, 3, 2]
                    preferences[1](Bob)      == [2, 0, 2]
                    preferences[2](Charlie)  == [3, 3, 0]

                we will insert each pairs winner and loser
                e.g. in first loop: i == 0(alice), b == 1(Bob)
                comparison_1 = preferences[0][1] => is 3
                comparison_2 = preferences[1][0] => is 2
                so we can figure out winner is Alice, loser is Bob in this pair
             */

            if (comparison_1 > comparison_2) {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (comparison_1 < comparison_2) {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
        }
    }

    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    /* 
        if candiates = [1: Alice, 2: Bob, 3: Charlie]
        if a preferences is:
            preferences[0](alice)    == [0, 3, 2]
            preferences[1](Bob)      == [2, 0, 2]
            preferences[2](Charlie)  == [3, 3, 0]

        if pairs is:
            pairs[0](1st) => winner: 0(Alice),   loser: 1(Bob)
            pairs[1](2nd) => winner: 2(Charlie), loser: 0(Alice)
            pairs[2](3rd) => winner: 2(Charlie), loser: 1(Bob)

        result will be [1, 1, 1]
     */

    int strength_array[pair_count];
    int winner;
    int loser;

    for (int i = 0; i < pair_count; i++) {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        strength_array[i] = preferences[winner][loser] - preferences[loser][winner];
    }

    // desc sort
    sort(strength_array, 0, pair_count - 1);
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    int winner;
    int loser;
    for (int i = 0; i < pair_count; i++) {
        winner = pairs[i].winner;
        loser = pairs[i].loser;
        if (!has_cycle(winner, loser))
            locked[winner][loser] = true;
    }

    return;
}

// Print the winner of the election
void print_winner(void)
{
    int i = 0;
    int j = 0;
    bool edge;
    while (i < candidate_count) {
        edge = locked[j][i];
        if (j == candidate_count && !edge) {
            printf("%s\n", candidates[i]);
            break;
        }
        else if (!edge) {
            j++;
        }
        else {
            i++;
            j = 0;
        }
    }
}

void sort(int array[], int start, int end)
{
    if (end > start) {
        int middle = (start + end) / 2;

        sort(array, start, middle);
        sort(array, middle + 1, end);

        merge(array, start, middle, end);
    }
}

void merge(int array[], int start, int middle, int end)
{
    int i = start;
    int j = middle + 1;
    int k = 0;

    typedef struct {
        int winner;
        int loser;
    } pair_temp;

    pair_temp pairs_temp[pair_count];

    while (i <= middle && j <= end) {
        if (array[i] >= array[j]) {
            pairs_temp[k].winner = pairs[i].winner;
            pairs_temp[k].loser = pairs[i].loser;
            i++;
            k++;
        }
        else {
            pairs_temp[k].winner = pairs[j].winner;
            pairs_temp[k].loser = pairs[j].loser;
            j++;
            k++;
        }
    }

    while (i <= middle) {
        pairs_temp[k].winner = pairs[i].winner;
        pairs_temp[k].loser = pairs[i].loser;
        i++;
        k++;
    }

    while (j <= end) {
        pairs_temp[k].winner = pairs[j].winner;
        pairs_temp[k].loser = pairs[j].loser;
        j++;
        k++;
    }

    for (i = start; i <= end; i++) {
        pairs[i].winner = pairs_temp[i - start].winner;
        pairs[i].loser = pairs_temp[i - start].loser;
    }
}

bool has_cycle(int winner, int loser)
{
    if (locked[loser][winner] == true)
        return true;

    for (int i = 0; i < candidate_count; i++) {
        if (locked[i][winner] == true)
            return has_cycle(i, loser);
    }
    return false;
}

–

執行

驗證