Sounds a bit more complicated than a plurality vote, doesn’t it? But it arguably has the benefit of being an election system where the winner of the election more accurately represents the preferences of the voters.
Understanding
程序开头设置了最大选举人数和选票数 接着定义了一个二维数组 preferences[i][j],分别代表第 i 个候选人,第 j 位选民对他的投票情况 然后构建了候选人结构体,有名字,选票,是否被淘汰三个属性 程序还有两个全局变量,用于选民与候选人的计数
while (true) tabulate(); from perference[i][j] for caculate candidates[i].vote bool won = print_winner(); true->break int min = find_min(); bool tie = is_tie(min); true->print existed candidates->break eliminate(min); last candidate.eliminate = true for candidate[i].vote = 0
接下来是声明函数与主函数 首先选民循环输入偏好候选人,项目代码已经给出。
代码思路
记录合法的投票
对二维数组进行操作,循环遍历给定的候选人 name,第 t 次即第 t 名
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Record preference if vote is valid boolvote(int voter, int rank, string name) { // TODO ido for (int t = 0;t < voter;t++) { if (strcmp(name,candidates[i])) { preference[voter][rank] = t; returntrue; } } returnfalse; }
for (int i = 0;i < voter_count;i++) { for (int j = 0;j < candidate_count;j++) if (!candidates[j].eliminated) { if (preferences[i][0] == j) { candidates[j].votes++; }
} elseif (candidates[j].eliminated) { int index = j + 1; while (candidates[index].eliminated) { index++; } candidates[index].votes++; }
以上代码只能处理有一人被淘汰的情况…… coding…… 我趣!!!原来这么简单,只要按顺序读取到第一个存在的候选人给他加一票就 OK 了,根本不用考虑被淘汰的情况,加完票之后立刻退出就行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// Tabulate votes for non-eliminated candidates voidtabulate(void) { // TODO ido for (int i = 0; i < voter_count; i++) { for (int j = 0; j < candidate_count; j++) { if (!candidates[preferences[i][j]].eliminated) { candidates[preferences[i][j]].votes++; break; } // else if (candidates[preferences[i][j]].eliminated) } }
return; }
输出赢家
利用点号读取候选人票数,只有第一名需要进行票数是否大于 50%的判断 选择排序,设置一个 max = candidate[1].vote,当有新的 candidates[i].vote > max 时,将 max 的值更新,max_candidate[ranking] =candidates[i]的索引 对第 i 个的 vote/2 判断是否大于半数,是则输出 name 并 break
末位检测/淘汰
循环找到 min <= candidate[1].vote…并 return 在 eliminate 函数进行 true 操作
平局检测
int 最小票数 min -》平局检测 is-tie(min) if (max = candidate[i])-》true -》printf 所有未被淘汰候选人 false-》eliminate(min)-》最小候选人.eliminate = true 设置一个临时变量,用 for 循环数一下有几个人的票数等于 min 的,如果所有未淘汰的人数和等于 min 的人数相等即平局。
// Populate array of candidates candidate_count = argc - 1; if (candidate_count > MAX_CANDIDATES) { printf("Maximum number of candidates is %i\n", MAX_CANDIDATES); return2; } 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); return3; }
// 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"); return4; } }
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; } } return0; }
PS
这题折腾了足足 4 天才趁着周三没课最终完成,看着检查点从全红变全绿的过程就像玩 soul like 游戏一样,最终通过的时候直接芜湖~起飞! 做完这题感觉整个人都升华了,又是 markdown 又是写注释又是打草稿的,周三一天用了六个小时,倒是没怎么问 ddb。