CS50 tideman - :( lock_pairs пропускает последнюю пару, если создает цикл

Question

Я новичок в stackoverflow и новичок в программировании. Я работаю над проблемой tideman для курса 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

Несколько замечаний о вашем коде / logi c:

1. Вы изменяете значение аргумента вашей функции в circle_check, когда вы делаете link = n. Хорошая практика - не изменять то, что передается в качестве аргумента функции. Кроме того, в этом конкретном случае c вы можете выполнить circle_check(winner, n) напрямую.

2. Ваша функция circle_check, как она представлена, всегда возвращает false . Это происходит потому, что когда вы вызываете его из себя, вы фактически не используете его return ни для чего. Предположим, что рекурсивный вызов возвращает true : при «первом» вызове функции строку можно заменить на:

else
{
  link = n;
  true;
}

И, как вы можете себе представить , который ничего не делает, и функция продолжает выполнение в обычном режиме, возвращая false.

Если вместо этого вы добавите return перед вызовом функции, вы решите эту проблему.

Но то есть еще третий момент, который вам нужно учитывать:

Ваша функция не учитывает многократные проверки ссылок в одной строке матрицы locked[i][j]. Позвольте мне продемонстрировать:

Представьте, что у вас есть заблокированная матрица 5x5, а в строке 4 у вас в настоящее время есть такое расположение истинного (T) и ложного (F):

[FTTXF ]

Когда ваша функция linear выполняет поиск по строке, она останавливается на заблокированном [4] [1], первом значении true, и выполняет рекурсивный вызов для поиска ссылки. Если он найдет, он вернет true , а ваш lock_pairs не будет добавлять true в матрицу locked. Но что, если он не найдет? Затем вместо перехода к locked[4][2], чтобы проверить ссылки там, он просто вернет false, и пара будет заблокирована на lock_pairs.

Вы можете решить эту проблему, например, добавив проверку после рекурсивного вызова, чтобы увидеть, было ли там возвращено значение true или false. Если возвращается истина, это означает, что есть ссылка, и вам НЕ следует добавлять пару в locked. С другой стороны, если вы получите false, это означает, что ссылки нет и вы можете продолжить линейный поиск в строке.

Оператор else может выглядеть примерно так:

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