CS50 潮人 - :( lock_pairs skips final pair if it creates cycle

Question

我是 stackoverflow 的新手，也是编程的新手。
我正在研究 CS50 类(class)的潮汐人问题。 https://cs50.harvard.edu/x/2020/psets/3/tideman/
当我运行 check50 时，除了一个之外，所有东西都检查出来了:
:( lock_pairs 跳过最后一对，如果它创建循环
lock_pairs 没有正确锁定所有非循环对
这两个确实通过了测试:
:) lock_pairs 在没有循环时锁定所有对
:) lock_pairs 跳过中间对，如果它创建一个循环
我找不到问题。我在这里缺少什么？
这是我的代码:

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

    // Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // for every pair we need to check for a circle
    for (int i = 0; i < pair_count; i++)
    {
        if (!circle_check(pairs[i].winner, pairs[i].loser))
        {
            //there's no circle: lock in pair
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}


// check pair for circles between winner and loser. Loser is first link
bool circle_check(int winner, int link)
{
    // check if the loser already has connections
    for (int n = 0; n < candidate_count; n++)
    {
        if (locked[link][n] == true)
        {
            // there's a link. if this ends in the winner, there's a circle
            if (n == winner)
            {
                return true;
            }
            else
            {
                // there may still be a circle, check next connection
                link = n;
                circle_check(winner, link);
            }
        }
    }
    return false;
}

Answer 1

关于您的代码/逻辑的一些观察:

您正在更改 circle_check 中函数参数的值当您这样做时link = n .最好不要更改作为函数参数传入的内容。另外，在这种特定情况下，您可以执行 circle_check(winner, n)直接地。

您的 circle_check功能，正如它所呈现的那样，总是 返回假。发生这种情况是因为当你从它自身调用它时，你实际上并没有使用它的 return 来做任何事情。假设递归调用返回 真 :在“第一个”函数调用中，该行可以替换为:

else
{
  link = n;
  true;
}

而且，正如您可以想象的那样，它什么也不做，函数继续正常执行，返回 false。
如果您改为添加 return在函数调用之前，你解决了这个问题。
但是还有第三点，您需要考虑:

您的函数不考虑对 locked[i][j] 同一行上的链接的多次检查。矩阵。请允许我演示:

想象一下，您有一个 5x5 锁定矩阵，在第 4 行，您当前具有 true (T) 和 false (F) 的这种处置:
[ F T T X F ]
当您的函数 linear 搜索该行时，它会在 lock[4][1](第一个为真)处停止，并进行递归调用以查找链接。如果确实找到，它将返回 真和您的 lock_pairs不会为 locked 添加 true矩阵。但是，如果找不到呢？然后，而不是去locked[4][2]检查那里的链接，它只会返回 false并且这对将被锁定在 lock_pairs .
例如，您可以通过在递归调用后添加检查来解决此问题，以查看它在那里返回的是真还是假。如果返回 true，则表示存在链接，您不应将该对添加到 locked .另一方面，如果您得到 false，则表示没有链接，您可以继续在线上进行线性搜索。else语句可能类似于:

else
{
  if (circle_check(winner,n)) // this way it only stops the search if a link was found
  {
    return true;
  }
}