我有一个关于cs50中潮汐问题的问题

Question

我在pset3(cs50)中做tideman问题，但是我不能区分我的程序和函数look_pairs的正确程序之间的区别。

:) tideman.c exists
:) tideman compiles
:) vote returns true when given name of candidate
:) vote returns false when given name of invalid candidate
:) vote correctly sets rank for first preference
:) vote correctly sets rank for all preferences
:) record_preferences correctly sets preferences for first voter
:) record_preferences correctly sets preferences for all voters
:) add_pairs generates correct pair count when no ties
:) add_pairs generates correct pair count when ties exist
:) add_pairs fills pairs array with winning pairs
:) add_pairs does not fill pairs array with losing pairs
:) sort_pairs sorts pairs of candidates by margin of victory
:) lock_pairs locks all pairs when no cycles
:( lock_pairs skips final pair if it creates cycle
    lock_pairs did not correctly lock all non-cyclical pairs
:) lock_pairs skips middle pair if it creates a cycle
:) print_winner prints winner of election when one candidate wins over all others
:) print_winner prints winner of election when some pairs are tied

这是我的程序，我在正确的程序之间做了一点区别。我没有判断makeCycle（winner,I）的返回，而是返回这个函数，你可以在我的代码中看到区别。

bool makeCycle(int winner, int loser) 
{
        if (winner == loser) {
            return true;
        }
        for (int i = 0; i < candidate_count; i ++) {
            if (locked[loser][i]) {
                    return makeCycle(winner, i); 
            }
        }
        return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    for(int i = 0; i < candidate_count; i ++) {
        if (!makeCycle(pairs[i].winner, pairs[i].loser)) {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}

这是正确的版本，但我认为我的程序和正确的版本是一样的，我不知道为什么我的程序会造成这个错误。

bool makeCycle(int winner, int loser) 
{
        if (winner == loser) {
            return true;
        }
        for (int i = 0; i < candidate_count; i ++) {
            if (locked[loser][i]) {
                    if(makeCycle(winner, i)){
                        return true;
                    }
            }
        }
        return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    for(int i = 0; i < candidate_count; i ++) {
        if (!makeCycle(pairs[i].winner, pairs[i].loser)) {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}```

Answer 1

这两个版本并不相同。

这里：

if(makeCycle(winner, i)){
                        return true;
                    }

当MakeCycle(..)返回false时，函数不返回。而在第一个版本中：

return makeCycle(winner, i); 

函数总是返回调用的结果。

也许你被误导了

if (condition) return true; else return false;

与…相同的

return condition;

但是

if (condition) return true;

不等于

return condition;

第一个版本在第一次迭代中返回，其中locked[loser][i]为true。第二个版本仅在locked[loser][i]和makecycle(...)均为true时返回，否则继续循环。

Answer 2

在您的程序中

    for (int i = 0; i < candidate_count; i ++) {
        if (locked[loser][i]) {
                return makeCycle(winner, i); 
        }
    }

返回false的频率比

    for (int i = 0; i < candidate_count; i ++) {
        if (locked[loser][i]) {
                if (makeCycle(winner, i)) {
                    return true;
                }
        }
    }
    return false;

这是因为在第二个解决方案中，如果makecycle(winner，i)失败，它不会返回false；它继续到下一个locked[loser][i]。如果所有锁定的[loser][i]无法触发对MakeCycle（winner,i)的成功调用，则正确的解决方案仅返回false。您的解决方案将返回第一个makecycle（winner,i）返回的内容。