PSET 3 Tideman CS50 lock_pairs无法正确锁定 [英] PSET 3 Tideman CS50 lock_pairs doesn't lock correctly

问题描述

我是这个网站的新手，所以我可能无法正确询问我的问题，对此我感到抱歉，但是我已经在PSET 3 Tideman上苦苦挣扎了一段时间.目前，我正在使用lock_pairs，但我不知道该怎么办.感谢您的帮助！这些是我提示check50的提示:

i am new to this site so i might not ask my question correctly which i am sorry for but i have been struggling with PSET 3 Tideman for quite a while. Currently i am on lock_pairs and i dont know what to do. Would appreciate your help! These are my prompts for check50:

:) 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
    lock_pairs did not correctly lock all non-cyclical pairs

void lock_pairs(void)
{
    int winner;
    int win_count[MAX];
    int temp_win = 0;
    for (int i = 0; i < pair_count; i++)
    {
        locked[ pairs[i].winner ][ pairs[i].loser ] = true;
        win_count[ pairs[i].winner ]++;
        if (win_count [ pairs[i].winner ] > temp_win )
        {
            winner = pairs[i].winner;
        }
    }
    for ( int p = 0; p < pair_count; p++)
    {
        if (win_count[ pairs[p].winner ] == win_count[winner] && pairs[p].winner != winner )
        {
            for (int i = pair_count - 1; i < -1 ; i--)
            {
                locked[ pairs[i].winner ][ pairs[i].loser ] = false;
                win_count [ pairs[i].winner ]--;
                if (pairs[i].winner == winner ) 
                {
                    win_count[winner]--;
                    for (int j = 0; j < pair_count; j++)
                    {
                        if (win_count[ pairs[j].winner ] > win_count[winner])
                        {
                            winner = pairs[j].winner;
                        }
                        if (win_count[ pairs[j].winner] == win_count[winner] && pairs[j].winner != winner)
                        {
                            break;
                        }
                        
                        
                    }
                }
                else 
                {
                    locked[ pairs[i].winner ][ pairs[i].loser ] = true;
                }
            }
        }
    }
    return;
}

推荐答案

您可能误解了 lock_pairs 背后所需的逻辑，因为您的函数过于复杂.这就是您要做的-

You may have misunderstood the logic required behind lock_pairs, because your function is overly complicated. This is what you're asked to do-

• 逐对检查每对，并在必要时将它们锁定

如何知道是否有必要?很简单，您确保将其锁定不构成圆圈

How to know, if it is necessary? Simple, you make sure locking them does not constitute a circle

什么是构成圆圈"?吝啬的?课程本身对此作了很好的解释.更多信息就在

What does "constitute a circle" mean? This is explained very well by the course itself. More info right there

但基本上，

在以上投票的情况下，这将如何工作?好吧，两人最大的胜利余数是爱丽丝击败鲍勃，因为有7名选民比鲍勃更喜欢爱丽丝(没有其他正面交锋的比赛，胜者超过7名选民).因此，爱丽丝-鲍勃(Alice-Bob)箭头首先被锁定到图形中.获胜的下一个最大保证金是查理6-3击败爱丽丝，因此箭号紧随其后.

How would this work in the case of the votes above? Well, the biggest margin of victory for a pair is Alice beating Bob, since 7 voters prefer Alice over Bob (no other head-to-head matchup has a winner preferred by more than 7 voters). So the Alice-Bob arrow is locked into the graph first. The next biggest margin of victory is Charlie’s 6-3 victory over Alice, so that arrow is locked in next.

接下来是鲍勃5-4击败查理.但是请注意:如果我们现在要添加一个从鲍勃到查理的箭头，我们将创建一个循环！由于图表不允许循环，因此我们应跳过此边缘，而不要将其完全添加到图表中.如果要考虑的箭头更多，我们将寻找下一个箭头，但这是最后一个箭头，因此图形已完成.

Next up is Bob’s 5-4 victory over Charlie. But notice: if we were to add an arrow from Bob to Charlie now, we would create a cycle! Since the graph can’t allow cycles, we should skip this edge, and not add it to the graph at all. If there were more arrows to consider, we would look to those next, but that was the last arrow, so the graph is complete.

此分步过程如下所示，最终图形在右侧.

This step-by-step process is shown below, with the final graph at right.

现在真正的交易了，如何将其放入代码中?

Now the real deal, how do you put this in code?

像这样-

// Recursive function to check if entry makes a circle
bool makes_circle(int cycle_start, int loser)
{
    if (loser == cycle_start)
    {
        // If the current loser is the cycle start
        // The entry makes a circle
        return true;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[loser][i])
        {
            if (makes_circle(cycle_start, i))
            {
                // Forward progress through the circle
                return true;
            }
        }
    }
    return false;
}

从本质上说，要检查锁定获胜者->失败者是否会绕圈，您步行从失败者开始退回您锁定的条目，并转到该失败者拥有的所有候选人赢了.如果您一路走到赢家，如果我见过一个圆圈，那就是一个圆圈.

Essentially, to check if locking in a winner->loser makes a circle, you walk back the entries you have locked starting from the loser and going towards all the candidates this loser has won against. If you reach the winner somewhere along the way, that's a circle if I've ever seen one.

但是请注意， circle_start ，以免引起混淆.记住原始圈的起点(这是 lock_pairs 的主循环中的 winner )的唯一用途.在整个递归中，此常数是恒定的.再次记住，我们的目标是遍历所有输掉了(也被锁定)的候选人 ，并确保所有这些都不是 circle_start(又称我们将要锁定的优胜者).

Note that circle_start though, lest it gets confusing. That's only there to remember the original circle start (which is the winner in the main loop in lock_pairs). This is constant throughout the entire recursion. Remember, once again, our goal is to iterate through all the candidates loser has won against (and also have been locked) and make sure none of these are circle_start (aka the winner that we are about to lock in).

因此，该函数完成了所有繁重的工作，您的 lock_pairs 函数将非常简单-

So, that function right there does all the heavy lifting, your lock_pairs function is gonna be extremely simple-

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs()
{
    for (int i = 0; i < pair_count; i++)
    {
        if (!makes_circle(pairs[i].winner, pairs[i].loser))
        {
            // Lock the pair unless it makes a circle
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
}

这篇关于PSET 3 Tideman CS50 lock_pairs无法正确锁定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！