所有文章
分类
学习 阅读 生活 网站
标签 关于

目录

Harvard CS50 学习笔记（三）

 收录于 学习 计算机
     约 5030 字   预计阅读 11 分钟  次阅读    条评论
摘要
Harvard CS50 学习笔记（三）。

3 Algorithms

3.1 Lecture

3.1 Introduction

3.2 Memory

3.3 Algorithms

3.4 Searching

3.5 Running Times

3.6 Big Oh Notation

  1. 大 $O$（复杂度上界，即小于等于）
    • $O(n^2)$
    • $O(n \log(n))$
    • $O(n)$
    • $O(log(n)$
    • $O(1)$
  2. 大 $Ω$ （复杂度下界，即大于等于）
    • $Ω(n^2)$
    • $Ω(n \log(n))$
    • $Ω(n)$
    • $Ω(log(n)$
    • $Ω(1)$
  3. 大 $Θ$（复杂度上界与下界相同，即等于）
    • $Θ(n^2)$
    • $Θ(n \log(n))$
    • $Θ(n)$
    • $Θ(log(n)$
    • $Θ(1)$

3.7 Common Running Times

3.8 Asymptotic Notation

3.9 Searching Lockers

1
2
3
4
5

// pseudocode
For i from 0 to n-1
    If number behind i'th door
        Return true
Return false
  • $O(n)$
  • $Ω(1)$
1
2
3
4
5
6
7
8
9

// pseudocode
If no doors
    Return false
If number behind middle door
    Return true
Else if number < middle door
    Search left half
Else if number > middle door
    Search right half
  • $O(\log(n))$
  • $Ω(1)$

3.12 Sorting then Searching vs. Just Searching

  • 看情况，根据资源（时间优先、内存优先），来决定用哪种搜索，不一定永远都是二分查找优于线性查找。

3.14 String Comparison

3.15 Storing Data in Arrays

3.16 Structs

1
2
3
4
5
6

typedef struct
{
    string name;
    string number;
}
person;

  • 自定义类型，Java中类的雏形。

  • 用 . 获取属性。

3.17 Implementing Structs

 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

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

typedef struct
{
    string name;
    string number;
}
person;

int main(void) {
people[0].name = "Carter":
people[0].number = "+1-617-495-1000";
people [1].name = "David":
people[1].number = "+1-949-468-2750":
for (int i = 0: i < 2: i++)
  {
    if (stremp(people[i].name, "David") == 0)
    {
      printf("Found %s\n", numbers(il):
      return 0;
     }
  }
  printf( "Not found\n") :
  return 1;
}
  • 用 . 获取属性。

3.18 Sorting

3.19 Selection Sort （选择排序）

1
2
3
4

// pseudocode
For i from 0 to n-1
    Find smallest item between i'th item and last item
    Swap smallest item with i'th item

选择排序（Selection sort）是一种简单直观的排序算法。 它的工作原理如下。 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。

3.20 Selection Sort Running Time

  • $O(n^2)$
  • $Ω(n^2)$
  • $Θ(n^2)$

3.21 Bubble Sort（冒泡排序）

1
2
3
4
5
6
7

// pseudocode
Repeat n-1 times
    For i from 0 to n-2
        If i'th and i+1'th elements out of order
            Swap them
  	If no swqps
  			Quit

冒泡排序（Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

3.22 Bubble Sort Running Time

  • $O(n^2)$
  • $Ω(n)$

3.23 Visualizing Sorting

3.24 Recursion（递归）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// pseudocode
Pick up phone book
Open to middle of phone book
Look at page
If person is on page
    Call person
Else if person is earlier in book
    Search left half of book
Else if person is later in book
    Search right half of book
Else
    Quit

3.25 Recursion Implementation

3.26 Merge Sort （归并排序）

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

1
2
3
4
5
6
7

// pseudocode
If only one number
    Quit
Else
    Sort left half of numbers
    Sort right half of numbers
    Merge sorted halves

3.27 Merge Sort Running Time

  • $O(n\log(n))$
  • $Ω(n \log(n))$
  • $Θ(n \log(n))$

3.28 Merge Sort vs. Bubble Sort and Selection Sort


3.2 Shorts

/images/Harvard_CS50/Lecture_3/linear_search/linear_search_1.png
linear_search_1
/images/Harvard_CS50/Lecture_3/linear_search/linear_search_2.png
linear_search_2
/images/Harvard_CS50/Lecture_3/linear_search/linear_search_3.png
linear_search_3
/images/Harvard_CS50/Lecture_3/binary_search/binary_search_1.png
binary_search_1
/images/Harvard_CS50/Lecture_3/binary_search/binary_search_2.png
binary_search_2
/images/Harvard_CS50/Lecture_3/binary_search/binary_search_3.png
binary_search_3
/images/Harvard_CS50/Lecture_3/binary_search/binary_search_4.png
binary_search_4

3.2.3 Bubble Sort

/images/Harvard_CS50/Lecture_3/bubble_sort/bubble_sort_1.png
bubble_sort_1
/images/Harvard_CS50/Lecture_3/bubble_sort/bubble_sort_2.png
bubble_sort_2
/images/Harvard_CS50/Lecture_3/bubble_sort/bubble_sort_3.png
bubble_sort_3

3.2.4 Selection Sort

/images/Harvard_CS50/Lecture_3/selection_sort/selection_sort_1.png
selection_sort_1
/images/Harvard_CS50/Lecture_3/selection_sort/selection_sort_2.png
selection_sort_2
/images/Harvard_CS50/Lecture_3/selection_sort/selection_sort_2.png
selection_sort_3

3.2.5 Recursion

/images/Harvard_CS50/Lecture_3/recursion/recursion_1.png
recursion_1
/images/Harvard_CS50/Lecture_3/recursion/recursion_2.png
recursion_2
/images/Harvard_CS50/Lecture_3/recursion/recursion_3.png
recursion_3
/images/Harvard_CS50/Lecture_3/recursion/recursion_4.png
recursion_4
/images/Harvard_CS50/Lecture_3/recursion/recursion_5.png
recursion_5
/images/Harvard_CS50/Lecture_3/recursion/recursion_6.png
recursion_6
/images/Harvard_CS50/Lecture_3/recursion/recursion_7.png
recursion_7
/images/Harvard_CS50/Lecture_3/recursion/recursion_8.png
recursion_8
/images/Harvard_CS50/Lecture_3/recursion/recursion_9.png
recursion_9
/images/Harvard_CS50/Lecture_3/recursion/recursion_10.png
recursion_10
/images/Harvard_CS50/Lecture_3/recursion/recursion_11.png
recursion_11

3.2.6 Merge Sort

/images/Harvard_CS50/Lecture_3/merge_sort/merge_sort_1.png
merge_sort_1
/images/Harvard_CS50/Lecture_3/merge_sort/merge_sort_2.png
merge_sort_2
/images/Harvard_CS50/Lecture_3/merge_sort/merge_sort_3.png
merge_sort_3
/images/Harvard_CS50/Lecture_3/merge_sort/merge_sort_4.png
merge_sort_4

3.3 Lab 3


3.4 Problem Set 3

3.4.1 Plurality

  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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

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

// Max number of candidates
#define MAX 9

// Candidates have name and vote count
typedef struct
{
    string name;
    int votes;
}
candidate;

// declare functions
int selectionSort(candidate people[]);
int bubbleSort(candidate people[]);
int mergeSort(candidate people[], int length);

// Array of candidates
candidate candidates[MAX];

// Number of candidates
int candidate_count;

// Function prototypes
bool vote(string name);
void print_winner(void);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: plurality [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].name = argv[i + 1];
        candidates[i].votes = 0;
    }

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

    // Loop over all voters
    for (int i = 0; i < voter_count; i++)
    {
        string name = get_string("Vote: ");

        // Check for invalid vote
        if (!vote(name))
        {
            printf("Invalid vote.\n");
            i--;
        }
    }

    // Display winner of election
    print_winner();
}

// Update vote totals given a new vote
bool vote(string name)
{
    for (int i = 0; i < candidate_count; i++) {
        if (strcmp(name, candidates[i].name) == 0) {
            candidates[i].votes++;
            return true;
        }
    }
    return false;
}

// Print the winner (or winners) of the election
void print_winner(void)
{
    // int highestVotes = selectionSort(candidates);
    // int highestVotes = bubbleSort(candidates);
    int highestVotes = mergeSort(candidates, candidate_count);
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes == highestVotes) {
            printf("%s\n", candidates[i].name);
        }
    }
    return;
}

int selectionSort(candidate people[]) {
    candidate temp;
    for (int i = 0; i < candidate_count; i++) {
        for (int j = i + 1 ; j < candidate_count; j++) {
            if (people[i].votes > people[j].votes) {
                temp = people[i];
                people[i] = people[j];
                people[j] = temp;
            }
        }
    }
    return people[candidate_count - 1].votes;
}

int bubbleSort(candidate people[]) {
    candidate temp;
    for (int i = 0; i < candidate_count; i++) {
        for (int j = 0; j < candidate_count - i - 1; j++) {
            if (people[j].votes > people[j + 1].votes) {
                temp = people[j];
                people[j] = people[j + 1];
                people[j + 1] = temp;
            }
        }
    }
    return people[candidate_count - 1].votes;
}

int mergeSort(candidate people[], int length) {
    int half = length / 2;
    if (half < 1) {
        return 0;
    }
    candidate leftHalf[half];
    candidate rightHalf[length - half];
    for (int i = 0; i < half; i++) {
        leftHalf[i] = people[i];
    }
    for (int i = 0; i < length - half; i++) {
        rightHalf[i] = people[half + i];
    }
    mergeSort(leftHalf, half);
    mergeSort(rightHalf, length - half);
    int leftIndex = 0;
    int rightIndex = 0;
    for (int i = 0; i < length; i++) {
        if (leftIndex < half) {
            if (leftHalf[leftIndex].votes <= rightHalf[rightIndex].votes) {
                people[i] = leftHalf[leftIndex];
                leftIndex++;
            } else {
                people[i] = rightHalf[rightIndex];
                rightIndex++;
            }
        } else {
            people[i] = rightHalf[rightIndex];
            rightIndex++;
        }
    }
    return people[length - 1].votes;
}

  • 非常有必要修改一下手写的非常原始的三种排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 我写的选择排序
int selectionSort(candidate people[]) {
    candidate temp;
    for (int i = 0; i < candidate_count; i++) {
        for (int j = i + 1 ; j < candidate_count; j++) {
            if (people[i].votes > people[j].votes) {
                temp = people[i];
                people[i] = people[j];
                people[j] = temp;
            }
        }
    }
    return people[candidate_count - 1].votes;
}
  • 这个选择排序有若干问题
    1. i < candidate_count -1，因为 i 层的循环不会到最后一个数字。
    2. 与标准写法比，我并没有额外记录最小值的索引，这里不是很清楚为什么要这么做。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 我写的冒泡排序
int bubbleSort(candidate people[]) {
    candidate temp;
    for (int i = 0; i < candidate_count; i++) {
        for (int j = 0; j < candidate_count - i - 1; j++) {
            if (people[j].votes > people[j + 1].votes) {
                temp = people[j];
                people[j] = people[j + 1];
                people[j + 1] = temp;
            }
        }
    }
    return people[candidate_count - 1].votes;
}

  • 这个冒泡排序有若干问题

    1. i < candidate_count -1，因为 i 层的循环不会到最后一个数字。

    2. 可以增加一个布尔类型变量，用于记录是否交换，如果都没有交换，说明顺序是排好的，不需要排序，提升效率。

    3.  1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

      // 修改后的程序
int bubbleSort(candidate people[]) {
    candidate temp;
  	bool exchanged = true;
    for (int i = 0; exchanged && i < candidate_count - 1; i++) {
      	exchanged = false;
        for (int j = 0; j < candidate_count - i - 1; j++) {
            if (people[j].votes > people[j + 1].votes) {
                temp = people[j];
                people[j] = people[j + 1];
                people[j + 1] = temp;
              	exchanged = true;
            }
        }
    }
    return people[candidate_count - 1].votes;
}


 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

// 我写的归并排序
int mergeSort(candidate people[], int length) {
    int half = length / 2;
    if (half < 1) {
        return 0;
    }
    candidate leftHalf[half];
    candidate rightHalf[length - half];
    for (int i = 0; i < half; i++) {
        leftHalf[i] = people[i];
    }
    for (int i = 0; i < length - half; i++) {
        rightHalf[i] = people[half + i];
    }
    mergeSort(leftHalf, half);
    mergeSort(rightHalf, length - half);
    int leftIndex = 0;
    int rightIndex = 0;
    for (int i = 0; i < length; i++) {
        if (leftIndex < half) {
            if (leftHalf[leftIndex].votes <= rightHalf[rightIndex].votes) {
                people[i] = leftHalf[leftIndex];
                leftIndex++;
            } else {
                people[i] = rightHalf[rightIndex];
                rightIndex++;
            }
        } else {
            people[i] = rightHalf[rightIndex];
            rightIndex++;
        }
    }
    return people[length - 1].votes;
}
  • 这个归并排序有若干问题
    1. 与标准写法比，我多了一个临时数组的变量。
    2. 看起来比标准写法好理解一点。

3.4.2 Runoff

  1. 因为先尝试 Tideman 没有成功，所以把这个 Runoff 写一下。
  2. 感觉做麻烦了，应该有更简单的方式。
  3. 检测有点问题，find_min 函数必须循环 candidates 数组，用 temp 数组不行，但其实结果是对的。
  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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323

#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];
candidate temp[MAX_CANDIDATES];

// Numbers of voters and candidates
int voter_count;
int candidate_count;
bool exchange = true;
string winner;


// 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);
bool selectionSort(void);
bool bubbleSort(void);
bool mergeSort(void);
void mergeSorting(candidate temp[MAX_CANDIDATES], int count);

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

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++) {
        if (strcmp(name, candidates[i].name) == 0) {
            preferences[voter][rank] = i;
            return true;
        }
    }
    return false;
}

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    for (int i = 0; i < voter_count; i++) {
        for (int j = 0; j < candidate_count; j++) {
            int index = preferences[i][j];
            if (candidates[index].eliminated == true) {
                continue;
            } else {
                candidates[index].votes++;
                break;
            }
        }
    }
    return;
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    if(mergeSort()) {
        printf("%s\n", winner);
        return true;
    }
    return false;
}

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min = voter_count + 1;
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].eliminated != true) {
            if (candidates[i].votes < min) {
                min = candidates[i].votes;
            }
        }
    }
    return min;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].eliminated != true) {
            if (candidates[i].votes == min) {
                continue;
            } else {
                return false;
            }
        }
    }
    return true;
}

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++) {
        if (candidates[i].votes == min) {
            candidates[i].eliminated = true;
        }
        if (temp[i].votes == min) {
            temp[i].eliminated = true;
        }
    }
    return;
}

bool selectionSort(void) {
    for (int i = 0; i< candidate_count; i++) {
        temp[i] = candidates[i];
    }

    for (int i = 0; i < candidate_count - 1; i++) {
        for (int j = i + 1; j < candidate_count; j++) {
            if (temp[j].votes < temp[i].votes) {
                candidate replace = temp[i];
                temp[i] = temp[j];
                temp[j] = replace;

            }
        }
    }

    if (temp[candidate_count - 1].votes > temp[candidate_count - 2].votes && temp[candidate_count - 1].votes > (voter_count / 2)) {
        winner = temp[candidate_count - 1].name;
        return true;
    }
    return false;

}

bool bubbleSort(void) {

    for (int i = 0; i< candidate_count; i++) {
        temp[i] = candidates[i];
    }

    for (int i = 0; exchange && i < candidate_count - 1; i++) {
        exchange = false;
        for (int j = 0; j < candidate_count - 1 - i; j++) {
            candidate replace = temp[j];
            if (temp[j].votes > temp[j + 1].votes) {
                replace = temp[j];
                temp[j] = temp[j + 1];
                temp[j + 1] = replace;
                exchange = true;
            }
        }
    }

    if (temp[candidate_count - 1].votes > temp[candidate_count - 2].votes && temp[candidate_count - 1].votes > (voter_count / 2)) {
        winner = temp[candidate_count - 1].name;
        return true;
    }
    return false;

}

bool mergeSort(void) {
    for (int i = 0; i< candidate_count; i++) {
        temp[i] = candidates[i];
    }

    mergeSorting(temp, candidate_count);

    if (temp[candidate_count - 1].votes > temp[candidate_count - 2].votes && temp[candidate_count - 1].votes > (voter_count / 2)) {
        winner = temp[candidate_count - 1].name;
        return true;
    }
    return false;
}

void mergeSorting(candidate people[MAX_CANDIDATES], int count) {
    int leftPart = count / 2;
    int rightPart = count - leftPart;

    candidate leftSide[leftPart];
    candidate rightSide[rightPart];

    for (int i = 0; i < leftPart; i++) {
        leftSide[i] = people[i];
    }

    for (int i = 0; i < rightPart; i++) {
        rightSide[i] = people[i + leftPart];
    }

    if (leftPart < 1) {
        return;
    } else {
        mergeSorting(leftSide, leftPart);
        mergeSorting(rightSide, rightPart);
    }

    int leftIndex = 0;
    int rightIndex = 0;

    for (int i = 0; i < count; i++) {
        if (i < leftPart) {
            if (leftSide[leftIndex].votes >= rightSide[rightIndex].votes) {
                people[i] = rightSide[rightIndex];
                rightIndex++;
            } else {
                people[i] = leftSide[leftIndex];
            leftIndex++;
            }
        } else {
            people[i] = rightSide[rightIndex];
            rightIndex++;
        }
    }

}

3.4.3 Tideman

  1. 这个题没有做完，未通过所有测试，没有解决平局的情况，暂时放弃，不能花更多时间了
  2. 这个题的难点有二：
    1. 题目不好理解，代码的设计感觉有点问题（应该是我太菜）。
    2. 所学习内容太初级，无法很好的解决问题，例如只能用二维数组而不能使用 Map 类型等。
  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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254

#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;
bool loop = true;

// 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);
void selectionSort(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
// 把候选人的索引，根据其优先级，保存到rank数组里
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 true;
        }
    }
    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    for (int i = 0; i < candidate_count - 1; 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)
{
    int index = 0;
    for (int i = 0; i < candidate_count - 1; i++) {
        for (int j = i + 1; j < candidate_count; j++) {

            if (preferences[i][j] > preferences[j][i]) {
                pairs[index].winner = i;
                pairs[index].loser = j;
                index++;
                pair_count++;
            } else if (preferences[i][j] < preferences[j][i]) {
                pairs[index].winner = j;
                pairs[index].loser = i;
                index++;
                pair_count++;
            } else {
                continue;
            }
        }
    }
    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{

    selectionSort();
    return;
}

// Lock pairs into the candidate graph in order, without creating cycles
// 这里未通过测试
void lock_pairs(void)
{
    for (int i = 0;i < pair_count; i++) {
        locked[pairs[i].winner][pairs[i].loser] = true;
    }

    for (int i = 0;i < candidate_count -1; i++) {
        for (int j = i +1; j < candidate_count; j++) {
            if(locked[i][j] == true && locked[j][i] == true) {
                locked[i][j] = false;
                locked[j][i] = false;
            }
        }
    }

    for (int i = candidate_count -1; i < candidate_count; i++) {
        for (int j = 0; j < candidate_count; j++) {
            if (locked[i][j] == true) {
                for (int k = 0; k < candidate_count -1; k++) {
                    int index = k+j+1;
                    if (index ==  candidate_count) {
                        index = 0;
                    }
                    if(locked[k][index] == false) {
                        loop = false;
                    }
                }
            }
        }
    }

    // int trueCount[pair_count];
    // for (int i = 0; i < candidate_count; i++) {
    //     int tempTrueCount = 0;
    //     for(int j = 0; j <candidate_count; j++) {
    //         if(locked[i][j] == true) {
    //             tempTrueCount++;
    //         }
    //     }
    //     trueCount[i] = tempTrueCount;
    // }

    // for (int i = 0; i < pair_count - 1; i++) {
    //     if(trueCount[i] != trueCount[i+1]) {
    //         loop = false;
    //         break;
    //     }
    // }
    if (loop) {
        for (int i = candidate_count -1; i< candidate_count; i++) {
            for(int j = 0; i < candidate_count; j++) {
                locked[i][j] = false;
            }
        }
    }
    return;
}

// Print the winner of the election
void print_winner(void)
{
    if (loop) {
        printf("%s\n", candidates[pairs[0].winner]);
    } else {
        int highestVotesIndex;
        int highestVotes = -1;
        for (int i = 0; i < candidate_count; i++) {
            int tempHighestVotes = 0;
            for (int j = 0; j < candidate_count; j++) {
                if (locked[i][j] == true) {
                    tempHighestVotes++;
                }
            }
            if (tempHighestVotes >= highestVotes) {
                highestVotesIndex = i;
            }
        }
    printf("%s\n", candidates[highestVotesIndex]);
    }
    return;
}

void selectionSort(void) {
    pair temp;
    for (int i = 0; i < pair_count - 1; i++) {
        for (int j = i + 1; j < pair_count; j++) {
            if (preferences[pairs[i].winner][pairs[i].loser] < preferences[pairs[j].winner][pairs[j].loser]) {
                temp = pairs[i];
                pairs[i] = pairs[j];
                pairs[j] = temp;
            }
        }
    }
}
更新于 2021/11/29
阅读原始文档
 Harvard CS50
返回 | 主页