CS50 tideman - :( lock_pairs跳过了最后一个形成循环的配对

Question

CS50 tideman - :( lock_pairs跳过了最后一个形成循环的配对

7

我刚开始使用stackoverflow，并且对编程也很陌生。我正在为CS50课程解决tideman问题。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;
}

- KarinMG

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fabio Corrêa · Accepted Answer

关于你的代码/逻辑，有几点观察：

在circle_check中，当你执行link = n时，你改变了函数参数的值。最好不要在函数中更改传入的参数。此外，在这种特定情况下，你可以直接使用circle_check(winner, n)。
你的circle_check函数，按照它目前的形式，总是返回false。这是因为当你从函数本身调用它时，你实际上没有使用它的返回值。假设递归调用返回true：在“第一个”函数调用中，该行可以替换为：

else
{
  link = n;
  true;
}

而且，正如你所想象的那样，这对函数没有任何作用，它会正常执行并返回 false。

相反，如果在函数调用前添加 return，则可以解决此问题。

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

您的函数没有考虑到在 locked[i][j] 矩阵的同一行上多次检查链接的情况。让我来举个例子：

假设您有一个 5x5 的锁定矩阵，并且在第 4 行上，您当前拥有以下 true（T）和 false（F）的排列：

[ F T T X F ]

当您的函数线性搜索该行时，它将停留在 locked[4][1]，也就是第一个 true 上，并进行递归调用以查找链接。如果找到了，则会返回 true，您的 lock_pairs 就不会将 true 添加到 locked 矩阵中。但是，如果没有找到呢？那么，它不会去检查 locked[4][2] 是否存在链接，而只会返回 false，并将该对锁定在 lock_pairs 中。

您可以通过在递归调用后添加一个检查来解决这个问题，以查看是否在那里返回了 true 或 false。如果返回 true，则表示存在链接，您不应将该对添加到 locked 中。另一方面，如果返回 false，则表示没有链接，您可以继续在线性搜索中查找。

else 语句可能如下所示：

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