前言
CS50x 是哈佛大学推出的一门知名公开课，本课程是一门计算机科学的导论课程，适合于对计算机科学感兴趣的任何人学习，不需要任何基础。通过学习本课程有助于对计算机科学的体系建立一个基本的概念，其学习内容如下：
Tideman
上一篇我们讲了 Tideman 的运行机制，根据机制我们可以写出下列 main 函数，与 Runoff 投票机制类似：
#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]; 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); bool has_cycles(int loser, int winner); 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++) { // ranks[i] is voter's ith preference int ranks[candidate_count]; // 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; } } record_preferences(ranks); printf("\n"); } add_pairs(); sort_pairs(); lock_pairs(); print_winner(); return 0; } 复制代码
可以看到我们主要实现目标是这些抽象出来的函数：
首先使用 vote() 来匹配候选人姓名，更新排名数组：
// Update ranks given a new vote bool vote(int rank, string name, int ranks[]) { // TODO for (int i = 0; i < candidate_count; i++) { if (strcmp(candidates[i], name) == 0) { ranks[rank] = i; return true; } } return false; } 复制代码
比如说我们有这样的示例数据，可以看到每个人对候选人的偏好：
然后通过排名数组来算出偏好数组：
// Update preferences given one voter's ranks void record_preferences(int ranks[]) { // TODO for (int i = 0; i < candidate_count; i++) { for (int j = i + 1; j < candidate_count; j++) { preferences[ranks[i]][ranks[j]]++; } } return; } 复制代码
通过上面的数据可以得出：
也可以在每一个函数中添加一个这样的循环来测试数据是否正确：
// Test for preferences printf("\n"); for (int i = 0; i < candidate_count; i++) { for (int j = 0; j < candidate_count; j++) { printf("%i ", preferences[i][j]); } printf("\n"); } 复制代码
候选人两两对比：
void add_pairs(void) { // TODO for (int i = 0; i < candidate_count; i++) { pair new; for (int j = i + 1; j < candidate_count; j++) { if (preferences[i][j] > preferences[j][i]) { new.winner = i; new.loser = j; pairs[pair_count++] = new; } else if (preferences[i][j] < preferences[j][i]) { new.winner = j; new.loser = i; pairs[pair_count++] = new; } } } return; } 复制代码
然后基于胜利强度进行排序：
// Sort pairs in decreasing order by strength of victory void sort_pairs(void) { // TODO int strength[pair_count]; for (int i = 0; i < pair_count; i++) { pair p = pairs[i]; strength[i] = preferences[p.winner][p.loser] - preferences[p.loser][p.winner]; } // Selection sort for (int i = 0; i < pair_count; i++) { int max = i; for (int j = i + 1; j < pair_count; j++) { if (strength[j] > strength[max]) { max = j; } } pair tmp = pairs[max]; pairs[max] = pairs[i]; pairs[i] = tmp; } return; } 复制代码
得出结果：
最重要的一步是为有向图添加边，同时不能造成循环，所以我们需要实现定义一个递归函数：
bool has_cycles(int loser, int winner) { // Cyclic path exists if (loser == winner) { return true; } for (int i = 0; i < candidate_count; i++) { // Check path: loser -> i if (locked[loser][i]) { // Check path: i -> winner if (has_cycles(i, winner)) { return true; // If it returns true, loser -> i -> winner path exists // Add path: winner -> loser will create a cycle } } } return false; } // Lock pairs into the candidate graph in order, without creating cycles void lock_pairs(void) { // TODO for (int i = 0; i < pair_count; i++) { if (!has_cycles(pairs[i].loser, pairs[i].winner)) { locked[pairs[i].winner][pairs[i].loser] = true; } } return; } 复制代码
通过判断加上这条边后是否会造成死循环来确定是否要加上该边，所以递归函数要从 loser -> winner。
赢家是没有任何边指向它的，所以可以很轻松的判断出胜者：
// Print the winner of the election void print_winner(void) { // TODO for (int i = 0; i < candidate_count; i++) { bool isLoser = false; for (int j = 0; j < candidate_count; j++) { // j -> i if (locked[j][i]) { isLoser = true; break; } } if (!isLoser) { printf("%s\n", candidates[i]); break; } } return; }
测试数据
复制粘贴成 data.txt 文件，然后在命令行输入./tideman Alice Bob Charlie < data.txt 即可进行测试
6 Bob Charlie Alice Charlie Bob Alice Bob Alice Charlie Bob Charlie Alice Charlie Alice Bob Charlie Bob Alice
