PSET3-Tideman-锁定对

2024-05-16 • 问答

我正在寻找一些帮助，以检查我在此问题集上的逻辑。锁定功能选择：从最强对开始，按顺序（从最强到最弱胜利）浏览候选对（pair []），并将每对“锁定”到候选图，只要锁定该对不会产生循环在图中。 “锁定”表示将“真”值填充到二维数组（布尔锁定[] []）中。当候选人A赢得候选人B程序时，应该锁定[A] [B] = true;。我的代码“锁定了第一对（pairs [0]）。然后转到下一对（pairs [1]），并检查该对的输家（pairs [1] .loser）是否与前一对的输家不同。（pairs [0] .winner）。如果不是，它将锁定当前对（pairs [1]）。依此类推。程序检查所有以前的获胜者，并将它们与当前的失败者进行比较。从check50我得到如下信息： :( lock_pairs在没有循环时锁定所有对 lock_pairs没有锁定所有对 :)如果创建周期，lock_pairs将跳过最后一对 :( lock_pairs如果创建周期则跳过中间对 lock_pairs没有正确锁定所有非周期性对我只是不知道这里出了什么问题。

Mu代码：

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

我认为您正在使这一过程变得比您需要的复杂。对于lock_pairs，您要做的就是locked[pairs[i].winner][pairs[i].loser] = true; 当且仅当关系不成圈时。

“构成一个圆圈”到底是什么意思？课程本身对此作了很好的解释。更多信息right there

所以，最好有一个递归函数来检查一个关系是否成一个圆，就像-

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

PSET3-Tideman-锁定对

liangying142 回答：PSET3-Tideman-锁定对

大家都在问