时间戳

首页 > 解决方案 > PSET3 - Tideman - 锁定对

c - PSET3 - Tideman - 锁定对

问题描述

我正在寻找一些帮助来检查我对这个问题集的逻辑。锁定函数 should：从最强的对开始，按顺序（从最强到最弱的胜利）遍历候选对（pairs[]），并将每对“锁定”到候选图，只要锁定该对即可不在图中创建循环。“锁定”意味着用“真”值填充二维数组（布尔锁定[][]）。当候选人 A 与候选人 B 获胜时，程序应该 lock[A][B]=true;。我的代码“锁定第一对（pairs[0]）。然后转到下一对（pairs[1]）并检查这对的输家（pairs[1].loser）是否与前一对的赢家不同(pairs[0].winner)。如果不是，它会锁定当前对 (pairs[1])。依此类推。程序检查所有以前的获胜者，并将它们与当前的失败者进行比较。

穆代码：

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

        }
    }
    if ( counter != 0)
    {

    }
    else
    {
        locked[pairs[i].winner][pairs[i].loser] = true;
        printf("locked[%i][%i] = %d \n", pairs[i].winner, pairs[i].loser, locked[pairs[i].winner] 
[pairs[i].loser]);
    }

}
for (int a = 0; a< candidate_count; a++)
{
    for (int b = 0; b < candidate_count; b++)
    {
        printf("locked[%i][%i] = %d \n", a, b, locked[a][b]);
    }
}

return;

标签： cfunctioncs50locked

解决方案

我认为你让这比你需要的更复杂。您需要做的lock_pairs就是locked[pairs[i].winner][pairs[i].loser] = true; 当且仅当关系不形成圆圈时。

“构成一个圆”究竟是什么意思？课程本身很好地解释了这一点。更多信息就在那里

所以，最好有一个递归函数来检查一个关系是否形成一个圆圈，比如——

// Recursive function to check if entry makes a circle
bool makes_circle(int cycle_start, int loser)
{
    if (loser == cycle_start)
    {
        // If the current loser is the cycle start
        // The entry makes a circle
        return true;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[loser][i])
        {
            if (makes_circle(cycle_start, i))
            {
                // Forward progress through the circle
                return true;
            }
        }
    }
    return false;
}

请注意，cycle_start在整个递归过程中它是不变的——这是pairs[i].winner你的主要功能——这是你需要跟踪的

所以你lock_pairs现在看起来要简单得多-

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

推荐阅读