July 19, 2017

[CS50] Week 0 Scratch - 中文導讀筆記

*此筆記是依據胡立老師的 CS50 中文導讀直播影片所寫。

胡立老師的直播:
CS50 中文導讀:week 0

原本不想寫這次的導讀筆記,因為所有內容都在胡立老師的 初心者的計概與 coding 火球術 有學過。但是呢,之後應該都會寫每週的導讀筆記,只有第零週沒有寫總覺得不完整(這應該是強迫症 XD),所以最後還是決定寫一下導讀有講到的,而 CS50 課程裡面沒有講到的一些補充。

以下是我的筆記整理:

1. 各種進制:
1) 十進制 (Decimal):
從小到大所學的數學、以及一般日常生活中使用的數學都是十進制,「逢十就進位」的意思。十進制系統裡面沒有「十」這個數字,而是用「1」跟「0」來組成「10」。

十進制的數學函意就是以 10 為底數,所以當看到「512」的時候,可以拆解成:
5 個 100 + 1 個 10 + 2 個 1

其中的 100、10、1 可以用 10 為底數來表示,所以就變成:
5*10^2 + 1*10^1 + 2*10^0
(任何非 0 的數字的 0 次方都是 1,所以 10 的 0 次方等於 1。但 0 的 0 次方一般認為是無意義,參考:冪 Wikipedia

2) 二進制 (Binary):
「逢二就進位」的意思,二進制系統只有「0」跟「1」兩個數字,絕對不會有「2」。電腦最底層就是一堆「0」跟「1」的電子訊號。

同理,二進制的數學函意就是以 2 為底數,看到二進制的「101」時,換算成十進制就變成「5」:
1*2^2 + 0*2^1 + 1*2^0 = 4 + 0 + 1 = 5

3) 八進制 (Octal):
「逢八就進位」的意思。胡立老師先讓我們算八進制的「101」會等於十進制的哪個數字。

依照剛才的十進制跟二進制來推論,八進制的「101」就會等於十進制的「65」:
1*8^2 + 0*8^1 + 1*8^0 = 64 + 0 + 1 = 65

4) 十六進制 (Hexadecimal):
「逢十六就進位」的意思。十六進制跟剛才的三種進制比起來稍微特別一點。阿拉伯數字只有 0 到 9,而十六進制遇到「十」的時候不能用「10」來表示,因為「10」是兩個位數,就是進位的意思,所以在十六進制遇到「十」到「十五」的時候,就用英文字母「A」到「F」來表示,遇到「十六」的時候就進位變成「10」。

電腦上最常用到十六進制的地方就是用來表示 RGB(Red、Green、Blue,因為紅色、綠色、藍色是光的三原色) 的色票。CS50 課程裡面 Malan 教授有提到 RGB 的三個數字在電腦上通常是 24 bits 的大小(一個數字的大小是 8 bits,因為是 2 的 8 次方,所以總數是 256。由 0 到 255 代表那個顏色的紅色、綠色、藍色含量)。

而 RGB 總共用六個十六進制的數字來代表一個顏色,R、G、B 分別各用兩個十六進制的數字表示,00 為最小數,FF 為最大數(FF 就是十進制的 255,15*16^1 + 15*16^0 = 255),所以紅色、綠色、藍色含量最少的 #000000 就表示黑色,而紅色、綠色、藍色含量最多的 #FFFFFF 表示白色。

2. 二元搜尋法 (Binary Search):
在 CS50 課程裡,Malan 教授撕電話簿的方法就是二元搜尋法。這個方法每次搜尋的時候都會把要找的範圍減半,所以搜尋速度很快。

3. 時間複雜度。
這個部分胡立老師只有稍微帶過,從 時間複雜度 Wikipedia 上的定義是「在電腦科學中,演算法的時間複雜度是一個函式,它定量描述了該演算法的執行時間。」,然後其他的都太複雜了,所以我就放棄閱讀了 XD


導讀筆記偏向記錄 CS50 課程裡面沒有講到的部分,所以直播影片中間有一大部分都是原課程裡面講過的內容,那些就沒有寫在這個筆記裡,如果需要原課程筆記可以參考我上上週寫的:[CS50] Week 0 Scratch - 課程筆記與作業

以上筆記如果有錯還請指正。


No comments:

Post a Comment