CS50 Week 4

Lecture

講述Swap的兩個方法如下:

如同程式碼註解說明，此功能沒有成功，是因為沒有把變數的地址傳進

function裡，下一部分就會講到用指標(Pointer)來解決這個問題。

Lecture, continued

用一些Hollywood跟監、追蹤相關影片說明人們會利用監視器去追蹤某一些

人，拍到目標時，會需要放大(Zoom in)或是提高(enhance)影片中的人物，

藉此來說明如何用程式來表現顏色，簡單的就是黑與白(0跟1)，彩色的話

就是255，提供一個網站來表示比較清楚:色碼轉換器。

之後，就又談論到如何使用指標來解決Swap的問題。那課程中也有用生動

的方式來解釋甚麼是指標，請參考以下影片(從50:36開始)

Walkthroughs

Sigma-0

Sigma-1

NoSwap

Swap

Compare-0

Struct-0

Struct-1

Compare-1

Pointers

Copy-0

Copy-1

Section

Hexadecimal

講述人們常用的十進制，電腦用的二進制，以及為了方便簡潔看一大串二

進制的十六進制，例如: 1001010100100111，四個為一組的話就變為: 

1001 0101 0010 0111，改為十六進制: 0x9527。

Pointer

花了將近30分鐘視頻來講述指標的概念，因為之前就講過，這邊就跳過

了。

Dynamic Memory Allocation

就硬體來說，程式所做的任何操作都是在RAM裡面，而不是硬碟儲存空間裡，因此，程式都

是在有限的RAM裡操作。

動態記憶分配需要搭配指標，並且在執行結束之後，釋放記憶體。舉例來說：如果某個瀏覽

器的網頁一直開分頁，沒有釋放記憶體的話，執行速度會越來越慢，因為記憶體都被佔用完

了。在程式裡int* a = malloc(sizeof(int));實際上是建立了兩個記憶體位置，只是其中一個記憶

體位置叫做a，指向了一個沒有名字的記憶體位置。

Structures

自定義型態架構，可以把不同的型態int, char, float, array[]組合為一個型態架構。如果要用指標

的話為：struct car *mycar = malloc(sizeof(struct car));，car裡面的參數設定數值為：

(*mycar).year = 2001; (*mycar).plate = "CS50";或者這樣表示 mycar->year = 2001; mycar->plate =

"CS50";。

Defining Custom Types

自定義型態新名稱，舉例：typedef unsigned char byte;，紅色為舊名稱，藍色為新名稱。因

此，在CS50的標頭檔裡的string就是 typedef char* string; 或是 typedef struct car car_t; 或是如下

Recursion

Call Stack

6	fact(1)	7
5	fact(2)	8
4	fact(3)	9
3	fact(4)	10
2	fact(5)	11
開始 1	main()	結束 12
執行順序	Stack Frames	執行順序

Shorts

File I/O

CS50 Week 3

Lecture

講解排序，分別有Bubble sort, Selection sort, 和Insertion sort

看看聲音搭配排序法的影片

Lecture, continued

講解排序的O(n)的意思，以及位元運算AND, OR, XOR, Shift。

Section

GDB

GDB是一個debugger，可以更清楚地了解程式錯誤訊息是甚麼，

是透過下commad line的方式debug，可以下中斷點，逐步去偵錯。

在cs50的IDE中，可以直接下gdb filename，就可進入debug模式。

Computational Complexity

計算的複雜度，從最簡單到最複雜如下:

Computational Complexity
O(1)	constant time
O(log n)	logarithmic time
O(n)	linear time
O(n lon n)	linearithmic time
O(n^2)	quadratic time
O(n^c)	polynomial time
O(c^n)	exponential time
O(n!)	factorial time
O(infinite)	infinite time

O(1)的例子如下:

int four_for_you(int array[1000]) {

     return 4;

}

O(n)的例子如下:

最差的情況下，要搜尋數字5，必須執行5次

2

4

1

3

5

最差的情況下，要搜尋數字5，必須執行7次

2

4

1

3

7

6

5

Selection Sort

在未排序的排列中，尋找最小的數值，並把它移到第一位；
舉例如下:
紅色為未排列

2

4

1

3

5

找到最小值 1

2

4

1

3

5

移到最前面，藍色為已排列，依此類推。

1

4

2

3

5

演算法複雜度如下:

• 最好的情況下: $\Omega (n^2)$
• 最壞的情況下:$O(n^2)$

Bubble Sort

在未排序的排列中，從最左邊兩個數值value[0], value[1]開始比較，

若value[0]比value[1]的大，則做交換位置，

重複步驟直到最右邊的兩個數值value[n-1], value[n]，

之後再回到value[1], value[2]比較，依此類推。

演算法複雜度如下:

• 最好的情況下: $\Omega (n)$
• 最壞的情況下:$O(n^2)$

Insertion Sort

假設value[0]是已排序的，檢查value[1]是否比value[0]小

若是的話，就把value[1]移到最左邊，之後檢查value[2]是否比

value[0]或value[1]小，依此類推。

演算法複雜度如下:

• 最好的情況下: $\Omega (n)$
• 最壞的情況下:$O(n^2)$

Merge Sort

2	4	1	3	6	5	未排序的陣列
2	4	1	3	6	5	切一半，分左半跟右半
2	4	1	3	6	5	左半再切一半，右半也再切一半
2	1	4	3	5	6	最左半只有2，所以暫時為已排序，左半的右半比較之後，4比1大，交換排序 後，也暫訂為已排序。右半依此類推。
1	2	4	3	5	6	左半的兩個部分做比較，2比1大做交換，2比4小，不做交換。 右半依此類推。
1	2	3	4	5	6	最後左半跟右半做比較，1跟2都比3小，不做交換，4比3大，做交換 。剩餘都不變，完成全部排序。

演算法複雜度如下:

• 最好的情況下: $\Omega (n log n)$
• 最壞的情況下:$O(n log n)$

因此，可以說明Merge Sort比其他基本排序還好，適合大量的資料應用。

Linear Search

在一個陣列中(n個數值)裡，逐步搜尋目標數值x。

因此，演算法複雜度如下:

• 最好的情況下: $\Omega (1)$
• 最壞的情況下:$O(n)$

Binary Search

在一個已經排序好的陣列數值裡，搜尋目標數值x。

舉例:

5	8	15	21	30	44	48
[0]	[1]	[2]	[3]	[4]	[5]	[6]

目標值: 15

起始值: 5 (陣列[0]) 終點值: 48 (陣列[6]) 中間值: 21 (陣列[(0+6)/2])

中間值21不等於目標值15，但我們知道15比21小，所以陣列減一半，

5	8	15
[0]	[1]	[2]

起始值: 5 (陣列[0]) 終點值: 15 (陣列[2]) 中間值: 8 (陣列[(0+2)/2])

中間值8不等於目標值15，但我們知道15比8大，所以陣列再減一半，

15

[2]

起始值: 15 (陣列[2]) 終點值: 15 (陣列[2]) 中間值: 15 (陣列[(2+2)/2])

中間值15等於目標值15，結束這回合XD。

因此，演算法複雜度如下:

• 最好的情況下: $\Omega (1)$
• 最壞的情況下:$O(log n)$

Shorts

Asymptotic Notation

講述Asymptotic complexity的Big O是log n，相較其他的n或是$n^2$都要

好，在輸入資料很大的時候。下圖可以看出log n的優點(X軸是資料量，Y

軸是時間)。

之後講得有點重複(Binary search, Bubble sort, Insertion sort, Linear search, Quick sort, Selection sort)，所以我就跳過沒看了XD。

然後，我的重點不是在於完整地完成這個CS50課程，而是想要快速地了解

HTML, CSS, 機器學習等，因此，Problem set我就不會再做了。

CS50 Week 2

Lecture

解說C的基本程式碼，大概如下：

Lecture, continued

當程式碼擷取四個字串時，記憶體暫存空間會是怎樣排序這些字串呢？

請看下列例子：

其內存會是這樣子：

......	D	e	a	n	\0
H	a	n	n	a	h
\0	M	a	r	i	a
\0	R	o	b	\0	.....

\0是代表結束符號的意思。

之後有講到array、建構子帶參數、加密，其例子如下：

Walkthroughs

functions-0

functions-1

float-0, float-1, float-2

string-0

string-1

ascii-0

ascii-1

capitalize-0

capitalize-1

capitalize-2

ages

argv-0

argv-1

argv-2

Section

詳述Administrivia, Functions, Variables and Scope, Arrays, Command Line Arguments, Magic Numbers。

Shorts

詳述Arrays, Caser Cipher, Command Line Arguments, Global Variables, Redirecting & Pipes, Return Value, RSA, Scope, Vigenère Cipher

CS50 Week 1

Lecture

使用Could 9來教學基本的C語言

Could 9是一個線上的IDE平台，這樣的做法就是讓大家有統一的平台

非常適合用來做教學。

C語言的部分就是從

#include <stdio.h>

void main {

     print("Hello word!");

}

講解得非常詳細，若是有C語言底子的可以跳過這段。

不過最後有很酷的程式，我錄製成影片給大家觀賞

Lecture continued

在我們的認知中，我們知道1/10 = 0.1

但是我們用C去撰寫且編譯時，出來的結果卻是很不一樣唷

This is a amazing!!

OK，回到正題，這次講到關於變數型態的重要性，避免溢出（overflow）

若變數型態沒有設定好，就會發生一些非常簡單卻非常致命傷的問題。

在演講中舉例到，美國的愛國者飛彈是地對空飛彈系統，

當初是為了攔截伊拉克的飛毛腿飛彈所研製出來，

由於飛彈系統時鐘暫存器設計為24 位，精度也只限於24位的精度。

這個精度誤差漸漸放大，100小時後，飛彈的時鐘已經偏差了三分之一秒，

相等於600公尺距離誤差。

由於這個時間誤差，縱使雷達系統偵察到飛毛腿飛彈並預計了它的彈道，

系統卻找不到實際上來襲的飛彈。

Walkthroughs

這邊的練習一樣是把這週演講中的程式碼在拿來複習一次

首先當然是

Hello-0.c

Hello-1

Hello-2

Adder

Condition-0

Condition-1

Nonswitch

Switch

Positive

F2C

Sizeof

Section

Command line 

這部影片是講到用終端機(MaxOS, Linux)的指令，

關於指令當然首推鳥哥的私房菜！

因為MaxOS跟Linux都是基於Unix開發出來的，

或許有些不同，但是大致上普遍的指令都是相同。

影片有用到的指令為ls, cd, pwd, mkdir, cp, rm, mv，

有講到mkdir，但是沒有講到如何建立檔案，建立檔案的指令為touch filename。

Data type

再次講解資料型態的部分，不過這個影片講得比較詳細。

Operator

講述如何在程式裡做加減乘除的運算，以及布林運算。

Conditional statements

詳細講解if else跟switch的用法和不同。

Loops

詳述for, while, do while的用法。

Shorts

Boolean values

詳述布林運算。

Compliers

Rob Bowden感覺是個相當宅的屁孩講述當C語言程式進行編譯時的原理，

個人覺得了解這個部分，對未來寫程式會更有概念了解程式語言是怎麼運作的。

Functions

講述Function裡各個關鍵字的定義，以及不同的建構值。

Libraries

#include <stdio.h>在C語言就是這樣引用一個Library，

Library的好處就是在於可以被任何.c或.h同時使用，也講到如何鏈接Library

當在terminal輸入make filename時，會出現一些訊息，這邊舉例make adder其結果如下：

clang -ggdb3 -O0 -std=c11 -Wall -Werror -Wshadow    adder.c  -lcs50 -lm -o adder

其中-lcs50就是鏈接cs50 library。

Loops

再次講到迴圈...。

Make, Clang

講解當在要compile時，輸入make filename後，所產生的訊息

clang -ggdb3 -O0 -std=c11 -Wall -Werror -Wshadow    adder.c  -lcs50 -lm -o adder

對各個option講解如下：

-o : 更改compiled filename。

-ggdb3 : 顯示哪一行發生錯誤。 

-Wall -Werror : 顯示是什麼的錯誤訊息。

-l : 鏈接Library。

因此，說明make是多麼方便的指令

Precedence

這邊講到程式裡運算的優先權，當然就是跟一般數學的加減乘數是一樣的

只不過多了指標的運算如下：

Style

講了三個要注意的事項

1. 註解
2. 程式的排列
3. 變數的命名

多重註解用在說明函數或是整個程式，而單行註解最好越簡短越好；

程式的排列也是為了讓不管是自己或是別人閱讀程式，都可以輕易閱讀；

變數的名稱也是如此。

參考例子如下：

Typecasting

解說int與float、double和long long之間的轉換

Variables

變數的命名方式，以及如何應用

Problem set

• 實作下列題目
• Hello, C
• CS50 Check
• Shorts
• Hello again, C
• Smart Water
• Itsa Mario
• Time for Change
• 
  

CS50 Week 0

Important Pre-Course Survey

就是哈佛要做資料分析的一些問卷，問題相當的多

還要寫一些個人資料

讓我覺得很不人性化的是，他不會顯示總共有幾頁，現在是第幾頁

應該要像是；例如: 3/10，總共10頁，現在第3頁等等

Lecture

講師David J. Malan在哈佛大學講述基本的電腦布林數值的概念

以及程式邏輯的概念

用簡單的八個燈泡的方式來解說二進制

(有志願上台幫忙的同學，都可以得到小禮物XD)

影片後面就介紹一些助教以及工作人員（這部分我直接跳過了XD)

Lecture continued

一開頭就用有趣的歌曲跟美國的布袋戲玩偶XD，來個娛樂開場

這是一場講師David到耶魯大學的演講

用Scratch講解變數、迴圈，條件的一些觀念

實做一些有趣的遊戲，讓現場的學生可以上台玩玩看

其實這也是通過有趣的實做，來達到有效吸引學生的方法

畢竟現場有70%的學生沒有任何程式觀念

只是我不懂最後的片段是什麼意思XD

Walkthroughs

David手把手的方式教你如何用Scratch寫程式

沒什麼，就按照影片練習就好

Shorts

這邊有五部短片分別簡單說明什麼是演算法、ASCII、二進制、Scrach、多執行緒

都是非常簡單易懂的基本觀念

Problem set

使用Scratch製作動畫、遊戲、互動藝術或是其他專案

專案必須包含以下條件：

• 你的專案必須至少有兩個角色，至少其中一個角色不是一開始的配置的貓咪。
• 你的專案必須至少有三個腳本（不是每個角色都要）。
• 你的專案必須至少有一個條件、一個迴圈、一個變數。
• 你的專案必須至少有一個音效。
• 你的專案應該比那些教學影片示範裡更加複雜（其中許多，儘管有啟發性，卻相當短）但是它可以比 Pikachu’s Pastry Catch 和 Ivy’s Hardest Game 簡單。因此，你的專案應該要使用全部約幾十個拼圖。

這是我製作的賽車遊戲，不過我沒有完成它，因為我的目的是快速學完12週的課程

總結

有程式底子、且英文聽得懂約五成的，大概一天就可以學完這個Week。