CS50 Runoff作业C代码check50未通过，求错误定位帮助

我的CS50第三套作业Runoff的C代码本地测试运行正常，但使用check50检测时未能通过部分测试项，具体问题：

• tabulate函数在多候选人被淘汰、处理多轮偏好时无法生成正确票数
• find_min函数未正确忽略已淘汰候选人

尝试调试但未解决问题，希望得到帮助找出错误原因。

代码 #

#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 candidate_rank = 0;

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

        if (candidate_rank < candidate_count)
        {
            candidate_rank++;
        }
    }
    return 0;
}

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

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    for (int i = 0; i < voter_count; i++)
    {
        int preference = preferences[i][candidate_rank];
        if (!candidates[preference].eliminated)
        {
            candidates[preference].votes++;
        }
    }
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    int votes = 0;
    for (int i = 0; i < candidate_count; i++)
    {
        votes += candidates[i].votes;
    }

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

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int votes[candidate_count];
    for (int i = 0; i < candidate_count; i++)
    {
        votes[i] = candidates[i].votes;
    }

    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count - 1; j++)
        {
            if (votes[j] > votes[j + 1])
            {
                int x = votes[j];
                votes[j] = votes[j + 1];
                votes[j + 1] = x;
            }
        }
    }
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated)
        {
            return votes[i];
        }
    }
    return 0;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    int votes;
    bool tied;
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated)
        {
            votes = candidates[i].votes;
        }
    }
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated)
        {
            if (votes == candidates[i].votes)
            {
                tied = true;
            }
            else
            {
                tied = false;
                i = candidate_count;
            }
        }
    }
    if (!tied)
    {
        return false;
    }
    else
    {
        return true;
    }
}

// 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)
        {
            candidates[i].eliminated = true;
        }
    }
}

check50检测结果 #

√ runoff.c 文件存在
√ 代码可编译
√ 给定候选人姓名时vote返回true
√ 给定无效姓名时vote返回false
√ vote正确设置第一位选民的第一偏好
√ vote正确设置第二位选民的第三偏好
√ vote正确设置选民的所有偏好
√ 所有候选人未淘汰时tabulate统计票数正确
√ 一位候选人淘汰时tabulate统计票数正确
× 多候选人被淘汰时tabulate统计票数错误
    tabulate函数未生成正确票数
× tabulate处理多轮偏好时出错
    tabulate函数未生成正确票数
√ 有人获得多数票时print_winner输出姓名
√ 有人获得多数票时print_winner返回true
√ 无人获得多数票时print_winner返回false
√ 领先者获恰好50%票数时print_winner返回false
√ find_min返回候选人的最低票数
√ 所有候选人平局时find_min返回最低票数
× find_min未忽略已淘汰候选人
    find_min未识别正确的最低票数
√ 选举平局时is_tie返回true
√ 选举非平局时is_tie返回false
√ 仅部分候选人平局时is_tie返回false
√ 部分候选人淘汰后检测平局时is_tie工作正常
√ eliminate淘汰最后一名候选人
√ eliminate淘汰平局的多名最后一名候选人
√ 部分候选人已淘汰时eliminate正常工作

错误分析与修复建议 #

1. tabulate函数核心错误 #

你用全局变量candidate_rank统一处理所有选民的偏好顺位，完全不符合 runoff 选举规则。正确逻辑是：对每个选民，从第一顺位（rank 0）开始遍历其偏好列表，找到第一个未被淘汰的候选人，为该候选人增加一票，而非所有选民共用同一个顺位。

修复后的tabulate函数：

void tabulate(void)
{
    for (int i = 0; i < voter_count; i++)
    {
        // 对每个选民，从第一偏好开始找未淘汰的候选人
        for (int j = 0; j < candidate_count; j++)
        {
            int pref_idx = preferences[i][j];
            if (!candidates[pref_idx].eliminated)
            {
                candidates[pref_idx].votes++;
                break; // 找到有效偏好后，处理下一个选民
            }
        }
    }
}

同时删除全局变量candidate_rank，以及main函数中更新该变量的代码段。

2. find_min函数错误 #

你先将所有候选人票数排序，再遍历候选人找未淘汰者返回对应票数，但排序后的votes数组与原candidates数组索引已不对应，导致返回错误最小值。

正确逻辑：遍历所有未被淘汰的候选人，记录其中最小票数。

修复后的find_min函数：

int find_min(void)
{
    int min_votes = voter_count; // 初始化为最大可能票数
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated && candidates[i].votes < min_votes)
        {
            min_votes = candidates[i].votes;
        }
    }
    return min_votes;
}

3. is_tie函数潜在问题 #

原代码中votes和tied未初始化，极端情况（所有候选人被淘汰）会导致未定义行为。修复后：

bool is_tie(int min)
{
    bool tied = true;
    int first_votes = -1;
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated)
        {
            if (first_votes == -1)
            {
                first_votes = candidates[i].votes;
            }
            else if (candidates[i].votes != first_votes)
            {
                tied = false;
                break;
            }
        }
    }
    return tied;
}

内容的提问来源于stack exchange，提问作者Aadi