CS50 tideman - :( lock_pairs 如果创建循环则跳过最后一对

Question

我是 Whosebug 的新手，也是编程的新手。我正在研究 CS50 课程的潮人问题。 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

关于您的一些观察 code/logic：

当您执行 link = n 时，您正在更改 circle_check 中函数参数的值。最好不要更改函数中作为参数传入的内容。另外，在这种特定情况下，您可以直接执行 circle_check(winner, n)。
您的 circle_check 函数，正如它所呈现的那样，总是 return 为假。发生这种情况是因为当您从自身调用它时，您实际上并没有将它的 return 用于任何事情。假设递归调用 returns true: 在 'first' 函数调用中，该行可以替换为：

else
{
  link = n;
  true;
}

而且，如您所想，它什么都不做，函数继续正常执行，returning false。

如果您改为在函数调用前添加一个 return，则可以解决此问题。

但是还有第三点，你需要考虑：

您的函数不考虑在 locked[i][j] 矩阵的同一行上对 link 进行多次检查。请允许我演示一下：

假设您有一个 5x5 的锁定矩阵，并且在第 4 行，您当前具有真 (T) 和假 (F) 的这种配置：

[F T T X F]

当您的函数线性搜索该行时，它将在锁定 [4][1] 处停止，第一个为真，然后进行递归调用以查找 link。如果确实找到了，它将 return true 并且您的 lock_pairs 不会将 true 添加到 locked 矩阵。但是，如果找不到怎么办？然后，不是去 locked[4][2] 检查那里的 link，而是去 return false 并且这对将被锁定在 lock_pairs .

你可以解决这个问题，例如，在递归调用后添加一个检查，看看它是 returned true 还是 false。如果 true 是 returned，这意味着有一个 link，你不应该将这个对添加到 locked。另一方面，如果得到false，说明没有link，可以继续线性搜索就行了。

else 语句可能类似于：

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

CS50 tideman - :( lock_pairs 如果创建循环则跳过最后一对

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

c

cs50