Путеводитель по проблеме Tideman в CS50 Week 3.

Цель: написать функции для определения победителя на выборах приливов и напечатать имя победителя. Прежде чем читать дальше, важно понять, как работает система голосования tideman, что объясняется в описании проблемы.

Функция голосование должна принимать аргументы ранг, имя и ранг. Если name совпадает с именем действительного кандидата, то массив ranks следует обновить, чтобы указать, что избиратель имеет кандидата в качестве своего ранга предпочтение (где 0 - первое предпочтение, 1 - второе предпочтение и т. д.) Функция должна возвращать истину, если ранг был успешно записан, и ложь в противном случае (если, например, имя равно не имя одного из кандидатов).

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

Функция add_pairs должна добавлять все пары кандидатов, в которых один кандидат предпочтительнее, чем массив пары. Пару кандидатов, которые связаны (один не является предпочтительным по сравнению с другим), не следует добавлять в массив.
Функция должна обновить глобальную переменную pair_count, указав количество пар кандидаты.

Функция sort_pairs должна сортировать массив пар в порядке убывания силы победы, где сила победы определяется как количество избирателей, которые отдают предпочтение предпочтительному кандидату. Если несколько пар имеют одинаковую силу победы, вы можете предположить, что порядок не имеет значения.

Функция lock_pairs должна создать заблокированный график, добавляя все ребра в порядке убывания силы победы, пока ребро не будет создавать цикл.

Функция print_winner должна распечатать имя кандидата, который является источником графика. Вы можете предположить, что будет не более одного источника.

Как и в случае множественного числа, функция main уже написана для нас, и наша цель - заполнить функции, вызываемые в main. Ниже показано правильное поведение программы, в которой в качестве аргументов командной строки используются имена кандидатов на выборах перед тем, как пользователю будет предложено указать количество избирателей, за которым следует рейтинг кандидатов каждым избирателем. Наконец, печатается победитель выборов.

./tideman Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

Charlie

голос

Функция голос вызывается один раз для каждого избирателя (i) и ранжирования (j) во вложенном цикле внутри main функция. Например, если есть три кандидата, функция будет вызываться трижды для каждого избирателя, чтобы проверить выбор каждого избирателя первым, вторым и третьим ранжирующими кандидатами. Как и во множественном числе, если возвращается false, значит «Недействительный голос». печатается, и программа завершается.

    // Query for votes
    for (int i = 0; i < voter_count; i++)
    {
        // ranks[i] is voter's ith preference
        int ranks[candidate_count];
        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);
            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }

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

Массив ranks - это одномерный массив, который определяет порядок ранжирования кандидатов для каждого избирателя. Целое число индекса кандидата (порядок, в котором они были определены в аргументах командной строки) - это то, что хранится в массиве rank. Например, если есть три кандидата Алиса, Боб и Чарли, тогда Алиса будет [0], Боб будет [1], а Чарли будет [2]. Если избиратель голосует за Боба с рангом 1, Чарли с рангом 2 и Алису с рангом 3, то полученный массив рангов будет для этого избирателя [1, 2, 0] .

Сама функция аналогична функции голосование в задаче множественности. Он должен перебирать каждого кандидата, каждый раз проверяя с помощью strcmp, совпадает ли имя кандидата с аргументом name. Если это так, добавьте индекс этого кандидата в текущую позицию массива ranks и верните true, поскольку name является допустимым. Если это условие не выполняется после проверки всех кандидатов по аргументу name, верните false.

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    // Loop through candidates
    for (int i = 0; i < candidate_count; i++)
    {
        // Check name is valid
        if (strcmp(candidates[i], name) == 0)
        {
            // Update ranks array with rank preference
            ranks[rank] = i;
            return true;
        }
    }
    return false;
}

record_preferences

Эта функция также вызывается один раз для каждого избирателя в том же цикле, что и функция голосование. Он принимает один аргумент - массив ranks, который был заполнен функцией голосование. Задача состоит в том, чтобы обновить массив предпочтений, который представляет собой двумерный массив, который указывает количество избирателей, которые предпочитают кандидата i кандидату j. Другими словами, если есть три кандидата, предпочтения представляет собой таблицу 3x3.

Код для этого короткий, но логика может быть сложной. Должен использоваться вложенный цикл, при этом как внутренний, так и внешний цикл повторяют цикл до количества кандидатов. Однако внутренний цикл должен начинаться с i + 1, поскольку мы хотим добавить в массив настройки только тогда, когда j идет после i. в массиве ranks. После включения этого условия количество предпочтений может быть увеличено на 1 в позиции, где кандидат в рангах [i] сравнивается с кандидатом в рангах. [j].

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // Assess voter ranks
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            // Update number of voters who prefer [i] to [j]
            // in ranks array
            // E.g. [0, 3, 2, 1, 4]
            preferences[ranks[i]][ranks[j]]++;
        }
    }
return;
}

add_pairs

Эта функция должна добавить каждую пару кандидатов, один из которых предпочтительнее другого, в массив пар. Это одномерный массив пар структур, которые имеют целочисленные значения как победителя, так и проигравшего. Глобальная переменная pair_count также должна увеличиваться для каждой добавляемой пары.

И снова это может быть достигнуто с помощью вложенного цикла до количества кандидатов, при этом внутренний цикл постепенно увеличивается от i + 1. Это сделано для предотвращения повторных проверок массива настроек. Снова возьмем пример с тремя кандидатами, кандидат [0] будет сравниваться с [1] и [2], затем кандидат [1] будет сравниваться только с кандидатом [2]. При этом каждая комбинация выполняется ровно один раз, так как кандидаты не должны сравниваться с самими собой.

Во внутреннем цикле каждую комбинацию можно проверить, чтобы определить, является ли кандидат i или кандидат j победителем, с помощью отдельных условных операторов. Чтобы проверить, является ли i победителем, мы проверяем, превышает ли количество людей, предпочитающих кандидата i кандидату j, количество людей. кто предпочитает j вместо i, меняя это значение, чтобы проверить, является ли j победителем. Если есть ничья, оба условия проходят, и цикл продолжается.

После определения победителя структура pair в позиции pair_count массива pair может быть обновлена ​​с указанием победителя и проигравшего. Напомним, что pair_count изначально равно нулю, как определено в функции main. Затем необходимо увеличить pair_count, что позволит вставить следующую пару в следующую позицию в массиве.

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
        }
    }
    return;
}

sort_pairs

После определения массива пар цель этой функции состоит в том, чтобы отсортировать их в порядке убывания силы победы, где сила победы определяется как количество избирателей, которые отдают предпочтение предпочтительному кандидату. С точки зрения нашей программы, он равен позиции [pair.winner] [pair.loser] в массиве настроек, что дает количество людей, которые предпочитают победителя. проигравшему.

Для этой функции можно использовать любой алгоритм сортировки, как описано в лекции на третьей неделе, однако я выбрал пузырьковую сортировку. Для этого я снова использовал, как вы уже догадались, вложенный цикл. Здесь важно отметить, что i увеличивается вниз. Это связано с тем, что каждый проход цикла требует сортировки меньшего количества элементов, поскольку те, что справа от i, уже будут отсортированы.

Для каждой смежной пары структур пар в массиве пар сравнивается сила победы. Если пара в позиции j + 1 имеет большую силу победы, чем пара в позиции j, то они меняются местами с помощью временной переменной.

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    for (int i = pair_count - 1; i >= 0 ; i--)
    {
        for (int j = 0; j <= i - 1; j++)
        {
            if ((preferences[pairs[j].winner][pairs[j].loser]) < (preferences[pairs[j + 1].winner][pairs[j + 1].loser]))
            {
                pair temp = pairs[j];
                pairs[j] = pairs[j + 1];
                pairs[j + 1] = temp;
            }
        }
    }
return;
}

lock_pairs

Цель этой функции - заполнить заблокированный 2D-массив, который состоит из логических значений и изначально установлен на все false. Пару можно «заблокировать» и установить значение истина, если блокировка этой пары не создает цикл возврата к победившему кандидату. Это показано графически на изображении ниже. В этом примере Алиса была предпочтительнее Боба, а Чарли предпочтительнее Алисы. Если бы Боб был предпочтительнее Чарли в одной из отсортированных пар, то был бы создан цикл и не было бы победителя выборов. Однако в этом случае Чарли может быть объявлен победителем, поскольку на него нет стрелок. Что касается массива, все значения - ложные, указывающие на него (подробнее об этом позже).

Важно, чтобы вы полностью понимали, что должна делать функция, прежде чем начинать работу с синтаксисом, так как на то, чтобы разобраться, может уйти немного времени. Лично я обнаружил, что это действительно понравилось после прочтения этого поста. Важно понимать, что единственная цель функции - заполнить заблокированный массив на основе информации, указанной в массиве пар, ни больше ни меньше.

Теперь о самом синтаксисе. Есть много способов приблизиться к этому, некоторые из которых используют рекурсию, а некоторые нет. Мой подход заключался в том, чтобы определить отдельную функцию цикла, которая принимает в качестве аргумента двух кандидатов и проверяет, создан ли цикл.

Это рекурсивная функция, поэтому сначала необходимо определить базовый вариант, который будет выходить из функции при создании цикла. Это происходит, когда функция вызывается для двух идентичных значений-кандидатов, то есть кандидат указывает на себя, тем самым создавая цикл.

Рекурсивный регистр просматривает каждого кандидата и выполняет две проверки. Возможно, это легче понять, зная, что при вызове этой функции end изначально будет проигравшим, а cycle_start будет победителем каждой пары проверяется. Во-первых, если есть стрелка, идущая от конца к другому кандидату, то есть вероятность цикла. В противном случае цикла не может быть, и функция возвращает false. Если первая проверка возвращает true, снова вызывается цикл, на этот раз с использованием текущего кандидата в качестве аргумента end. Этот процесс повторяется до тех пор, пока не будет возвращено false, означающее, что цепочка завершится и цикл отсутствует, или пока не будет запущен базовый случай, когда цепочка вернется к началу цикла, создавая цикл и вернув правда.

// Test for cycle by checking arrow coming into each candidate
bool cycle(int end, int cycle_start)
{
    // Return true if there is a cycle created (Recursion base case)
    if (end == cycle_start)
    {
        return true;
    }
    // Loop through candidates (Recursive case)
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[end][i])
        {
            if (cycle(i, cycle_start))
            {
                return true;
            }
        }
    }
    return false;
}

В функции lock_pairs я перебрал каждую пару и вызвал функцию цикла для каждого проигравшего и победителя. Если cycle возвращает false, то массив заблокированных может быть установлен на true для пары .

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // Loop through pairs
    for (int i = 0; i < pair_count; i++)
    {
        // If cycle function returns false, lock the pair
        if (!cycle(pairs[i].loser, pairs[i].winner))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}

Если это все еще не имеет смысла, я рекомендую сесть с листом бумаги и пройтись по нескольким примерам пар массивов. Это определенно была самая сложная проблема в CS50, и мне потребовалось время, чтобы сообразить.

print_winner

Последняя функция должна вывести победителя выборов, учитывая информацию, определенную в массиве заблокированных. С точки зрения массива победителем становится кандидат, в столбце которого нет значений true. Графически это означает, что на них нет стрелок.

Чтобы определить это, мы можем перебрать каждого кандидата, объявив целое число для подсчета количества ложных значений в столбце этого кандидата в заблокированном. Затем мы перебираем столбец каждого кандидата, повторяя false_count, если обнаружено значение false. Если false_count равно scheme_count, тогда весь столбец будет false, и этот кандидат может быть объявлен как источник диаграммы, а его имя напечатано.

// Print the winner of the election
void print_winner(void)
{
    // Winner is the candidate with no arrows pointing to them
    for (int i = 0; i < candidate_count; i++)
    {
        int false_count = 0;
        for (int j = 0; j < candidate_count; j++)
        {
            if (locked[j][i] == false)
            {
                false_count++;
                if (false_count == candidate_count)
                {
                    printf("%s\n", candidates[i]);
                }
            }
        }
    }
    return;
}

Заключение

Сложность, определенно, значительно возросла для этого PSet, поскольку мы впервые попробовали алгоритмы рекурсии и сортировки. Очень приятно наконец увидеть успешную проверку 50 для этого.