CS50-Week3

文章发布时间:

最后更新时间:

文章总字数:
2.3k

预计阅读时间:
10 分钟

Lab3 Algorithm

主要是通过排序程序的用时来判断排序的方法，lab 不难[Flag]。

  • Babble sort 最优和最差分别是正序和倒叙的数组
  • Merge sort 的时间复杂度是$O(nlogn)$各项都非常优秀突出
  • Selection sort 的时间复杂度和 Babble sort 一样为$O(n^2)$所以区分不明显，通过判断正倒序用时来区分

Problem Sets

PS：Plurality 对我来说非常有挑战性，我盯着 Usage 和代码看了至少半个小时，才明白看 Understanding 的好处。本来我都不打算做 lab 后面的 problem set 了，现在看来还是太飘了。
除文末的源代码以外的代码均为 coding 过程中的代码，可能会和最终代码不同。

Plurality

需要我们写一个 0~8 以内整数的排序

如果用冒泡来写的话，大概是这样的代码，可以正确运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>

int main()
{
    int arr[10] = {3, 1, 8, 3, 0, 23, 78, 22, 55, 77};
    int t = 0;
    int size = sizeof(arr) / sizeof(int);

    for (int j = 0; j < size; j++)
    {
        for (int i = 0; i < size - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                t = arr[i + 1];
                arr[i + 1] = arr[i];
                arr[i] = t;
            }
        }
    }
    for (int n=0;n<size;n++)
    {
        printf("%i ",arr[n]);
    }

    return 0;
}

正确答案跑出来就很爽

回到正题，我们需要补全两个功能，确认投票者支持的候选人是否存在；将得分最高的候选人打印出来

检验很简单，利用 string 库提供的 strcmp 函数与 0 比较，返回真即可。

strcmp()是 C 语言中的一个函数，它用于比较两个字符串。如果两个字符串完全相同，strcmp()会返回 0。如果第一个字符串在字典中位于第二个字符串之前，strcmp()会返回一个负数。如果第一个字符串在字典中位于第二个字符串之后，strcmp()会返回一个正数。

打印第一名的功能需要思考，我最先想到的是将得分进行排序，同时将 name 一起更新，

然后发现根本写不出来

问了问 ddb；

解决方案：

利用一次循环，选择排序的实现最为简单：先定义一个 max=0，if 第 i 人的分数大于 max，把这个人的分数赋给 max。

输出多名同分者的方法同样简单：新建一个循环，if 第 i 位的分数和 max 相同，则打印这个人的 name。

easy to understand，ddb   o7(敬礼)

选做 #1 加时赛 Runoff

background

美国选举好复杂。。。
总结：如果第一名选票大于 50%即获胜，若低于 50%，则淘汰最后一名，将被淘汰者视为第一候选人的 vote 将顺延投给该 voter 的第二候选人，重复这个过程，直到第一名的票数大于 50%，忽略一些极端情况。

Sounds a bit more complicated than a plurality vote, doesn’t it? But it arguably has the benefit of being an election system where the winner of the election more accurately represents the preferences of the voters.

Understanding

程序开头设置了最大选举人数和选票数
接着定义了一个二维数组 preferences[i][j]，分别代表第 i 个候选人，第 j 位选民对他的投票情况
然后构建了候选人结构体，有名字，选票，是否被淘汰三个属性
程序还有两个全局变量，用于选民与候选人的计数

拥有变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int perferences[i][j]  选票【票数】【候选人】一个最大100张选票，每票有9个候选人的二维数组，
candidates[9]	候选人型数组
candidates.name	候选人的名称
candidates.votes	此人票数
candidates.elimanated	此人是否被淘汰
int voter_count	选民数量
int candidate_count	候选人数量

bool vote(int voter, int rank, string name); 0.传入i，j，name；进行选票合法性判断
void tabulate(void)1.计算幸存者的票数
bool print_winner(void)2.胜利检查（若有，则退出）
int find_min(void)3. 找最小票数
bool is_tie(int min)4. 平局检定（若有，则退出）
void eliminate(int min);5. 删去1st位置最小票数者
6. 将候选人票数重设为0 已给出

while (true)
tabulate(); from perference[i][j] for caculate candidates[i].vote
bool won = print_winner(); true->break
int min = find_min();   bool tie = is_tie(min); true->print existed candidates->break
eliminate(min);  last candidate.eliminate = true
for candidate[i].vote = 0

接下来是声明函数与主函数
首先选民循环输入偏好候选人，项目代码已经给出。

代码思路

记录合法的投票

对二维数组进行操作，循环遍历给定的候选人 name，第 t 次即第 t 名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    // TODO ido
    for (int t = 0;t < voter;t++)
    {
        if (strcmp(name,candidates[i]))
        {
            preference[voter][rank] = t;
            return true;
        }
    }
    return false;
}

strcmp()忘记和 0 比较，导致 vote 完全没计数
./runoff Alice Bob

candidate[0].name candidate[1].name
voter0 Alice 0 Bob 1
voter1 Bob 1 Alice 0
展示投票过程

没看懂想干嘛这函数 那就去 understanding 里好好想啊八嘎亚路！！
是想将候选人按得票数进行排序，每投一次票就排一次，然后检测赢家是否出现
将每个未被淘汰的候选人在第一位的票数进行排序。如果选票上的第一名已被淘汰，则将该票上的第二名视为第一。
两次遍历 i = voter_count,j = candidate_count，计算第 1，2，3，4……位候选人出现在 preference[i][1]的次数，每次将 candidates[i].elimenate = false 的 candidates[i].vote + 1，eliminate = true 的对 preference[i][ranking]进行 vote+1，用 while 循环，直到有 eliminate = false 的出现，ranking++计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 for (int i = 0;i < voter_count;i++)
 {
     for (int j = 0;j < candidate_count;j++)
if (!candidates[j].eliminated)
         {
             if (preferences[i][0] == j)
             {
                 candidates[j].votes++;
             }


         }
         else if (candidates[j].eliminated)
         {
             int index = j + 1;
             while (candidates[index].eliminated)
             {
                 index++;
             }
             candidates[index].votes++;
         }

以上代码只能处理有一人被淘汰的情况……
coding……
我趣!!!原来这么简单，只要按顺序读取到第一个存在的候选人给他加一票就 OK 了，根本不用考虑被淘汰的情况，加完票之后立刻退出就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // TODO ido
    for (int i = 0; i < voter_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            if (!candidates[preferences[i][j]].eliminated)
            {
                candidates[preferences[i][j]].votes++;
                break;
            }
            // else if (candidates[preferences[i][j]].eliminated)
        }
    }

    return;
}
输出赢家

利用点号读取候选人票数，只有第一名需要进行票数是否大于 50%的判断
选择排序，设置一个 max = candidate[1].vote，当有新的 candidates[i].vote > max 时，将 max 的值更新，max_candidate[ranking] =candidates[i]的索引
对第 i 个的 vote/2 判断是否大于半数，是则输出 name 并 break

末位检测/淘汰

循环找到 min <= candidate[1].vote…并 return
在 eliminate 函数进行 true 操作

平局检测

int 最小票数 min -》平局检测 is-tie（min） if (max = candidate[i])-》true -》printf 所有未被淘汰候选人
false-》eliminate（min）-》最小候选人.eliminate = true
设置一个临时变量，用 for 循环数一下有几个人的票数等于 min 的，如果所有未淘汰的人数和等于 min 的人数相等即平局。

就 tabulate 难倒我了，其他的都不难，基本一次编译就能过

源代码

【已编辑】
我只保留了main的部分，故意不小心的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

// Candidates have name, vote count, eliminated status
typedef struct
{
    string name;
    int votes;
    bool eliminated;
} candidate;

// Array of candidates
candidate candidates[MAX_CANDIDATES];

// Numbers of voters and candidates
int voter_count;
int candidate_count;

// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

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

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

    voter_count = get_int("Number of voters: ");
    if (voter_count > MAX_VOTERS)
    {
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
        return 3;
    }

    // Keep querying for votes
    for (int i = 0; i < voter_count; i++)
    {

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            // Record vote, unless it's invalid
            if (!vote(i, j, name))
            {
                printf("Invalid vote.\n");
                return 4;
            }
        }

        printf("\n");
    }

    // Keep holding runoffs until winner exists
    while (true)
    {
        // Calculate votes given remaining candidates
        tabulate();

        // Check if election has been won
        bool won = print_winner();
        if (won)
        {
            break;
        }

        // Eliminate last-place candidates
        int min = find_min();
        bool tie = is_tie(min);

        // If tie, everyone wins
        if (tie)
        {
            for (int i = 0; i < candidate_count; i++)
            {
                if (!candidates[i].eliminated)
                {
                    printf("%s\n", candidates[i].name);
                }
            }
            break;
        }

        // Eliminate anyone with minimum number of votes
        eliminate(min);

        // Reset vote counts back to zero
        for (int i = 0; i < candidate_count; i++)
        {
            candidates[i].votes = 0;
        }
    }
    return 0;
}

PS

这题折腾了足足 4 天才趁着周三没课最终完成，看着检查点从全红变全绿的过程就像玩 soul like 游戏一样，最终通过的时候直接芜湖~起飞！
做完这题感觉整个人都升华了，又是 markdown 又是写注释又是打草稿的，周三一天用了六个小时，倒是没怎么问 ddb。
2080413368.jpg

决定奖励自己一块键盘。
下周见~

≡