CS50 的 Tideman 问题（不理解 sort_pairs 函数）

Question

我目前正在尝试解决cs50课程中的潮汐问题，并试图从逻辑上理解它的每一步。简而言之，它是计算选举获胜者的代码。它不是让最多的选票获胜，而是通过要求每个选民将他们对所有候选人的偏好从最喜欢到最不喜欢的顺序排列来解决投票问题。从那里代码可以得出更准确和公平的结果。我将在下面链接作业/提示链接。

https://cs50.harvard.edu/x/2023/psets/3/tideman/

我被困在排序对功能上。正确的实现位于我的代码中，并且是我所得到的。

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;
}

为了再次获得正确的上下文，您可以看到上面的链接，稍后我将发布我的完整代码。

我的问题是为什么使用preferences[pairs[j].winner][pairs[j].loser]，而不是简单地使用preferences[i][j]，我脑海中的i和j将覆盖二维首选项数组，并能够按其中找到的每个 int 的大小对它们进行排序。看到那里使用的对结构，我的心有点崩溃。我在这里不明白什么？

如果您需要更多背景信息，请告诉我。完整代码如下，对不起这本书。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// 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];

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX)
    {
        printf("Maximum number of candidates is %i\n", MAX);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i] = argv[i + 1];
    }

    // Clear graph of locked in pairs
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

    pair_count = 0;
    int voter_count = get_int("Number of voters: ");

    // 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;
            }
        }

        record_preferences(ranks);

        printf("\n");
    }

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(name, candidates[i]) == 0)
        {
            ranks[rank] = i;
            return 1;
        }
    }
    return 0;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    for (int i = 0; i < candidate_count; i ++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            preferences[ranks[i]][ranks[j]]++;
        }
    }
    return;
}

// 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[j][i] > preferences[i][j])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
        }
    }
    return;
}

// 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;
             }
        }
    }
}

我已经尝试在纸上推理出所有内容，这是我第二次完成这项作业，希望能从逻辑上理解每一步。

Answer 1

我已将代码转换为指令，看看是否有帮助。

/**
  * The function should sort the pairs array in decreasing order of strength of victory, where strength of victory is defined to be the number of voters who prefer the preferred candidate. If multiple pairs have the same strength of victory, you may assume that the order does not matter.
  */
void sort_pairs(void)
{
    merge_sort(0, pair_count - 1);
    return;
}

merge_sort

功能：

1. 描述：

• merge_sort

  函数实现合并排序算法，以根据特定的比较标准对数组对进行有效排序。

2. 参数：

• start_index

  ：要排序的子数组的起始索引。

• end_index

  ：要排序的子数组的结束索引。

3. 算法：

• 验证子数组具有有效长度 (

  start_index < end_index

  )。
• 计算中间索引 (

  middle

  ) 将子数组分为两半。
• 在子数组的左半部分递归调用

  merge_sort

  （

  start_index

  到

  middle

  ）。
• 在子数组的右半部分递归调用

  merge_sort

  （

  middle + 1

  到

  end_index

  ）。
• 使用

  merge

  函数合并已排序的左半部分和右半部分。

merge

功能：

1. 描述：

• merge

  函数根据特定的比较标准将两个已排序的子数组合并为一个已排序的子数组。

2. 参数：

• start_index

  ：合并子数组的起始索引。

• middle

  ：中间索引将合并的子数组分为左右两半。

• end_index

  ：合并子数组的结束索引。

3. 算法：

• 计算左半部和右半部的尺寸（

  left_size

  和

  right_size

  ）。
• 创建子数组

  left

  和

  right

  来存储左半部分和右半部分。
• 将数据从原始数组 (

  pairs

  ) 复制到相应的子数组。
• 分别为左数组、右数组和合并数组的索引初始化循环变量

  i

  、

  j

  和

  k

  。
• 根据计算出的偏好差异比较左右子数组中的元素。比较标准：
  • 比较标准涉及计算左右子数组中对的偏好差异。
  • 决策逻辑优先考虑偏好差异较大的配对，表明对获胜候选人的偏好较高。
  • 元素根据此顺序合并到最终数组中，确保按偏好差异降序排列结果。
• 按排序顺序将元素合并到原始数组 (

  pairs

  ) 中。
• 通过将左子数组或右子数组中存在剩余元素的情况复制到合并数组来处理它们。