前言

這陣子推廣 cs50 有成，臉書社團陸陸續續有許多人加入，願意給這們課程一個機會
身為推他們入坑的人，覺得我可以提供一些方向，讓正在修這門課的人能夠在修課之前/之後更瞭解這週的內容
於是我之後會寫一系列文章，大致講解每一週的內容會是什麼
目標是讓你看完這篇文章之後，對於課程有六七成的掌握度

課程目標

（直接從官網複製來的，順便幫大家翻中文）

1. Binary（二進位）
2. ASCII
3. Algorithms（演算法）
4. Pseudocode（虛擬碼）
5. Source code（原始碼）
6. Compiler（編譯器）
7. Object code（目的碼）
8. Scratch
9. Statements（敘述）
10. Boolean expressions（布林表達式）
11. Conditions（條件控制）
12. Loops（迴圈）
13. Variables（變數）
14. Functions（函式）
15. Arrays（陣列）
16. Threads（執行緒）
17. Events（事件）

程式在幹嘛？

其實說穿了，整個流程就是三件事
輸入（input）-> 處理（processing）-> 輸出（output）

舉幾個例子會比較好懂
假設你今天要做三明治，那分成這三個步驟來看就是：

1. 買做三明治需要的食材（輸入）
2. 開始做三明治（處理）
3. 做完三明治了（輸出）

於是你就把你買好的土司、火腿、蛋，經過一些處理之後，變成了一個三明治
這邊有一個很值得關注的點，那就是：「你只說經過一些處理，但到底要怎樣處理？」
沒錯，依照剛開始的講法，中間那個步驟就像是一個黑盒子，你把東西餵進去，就有東西跑出來
可是你卻不知道裡面到底是怎麼做的？
而這個黑盒子裡面的東西，就叫做演算法（algorithm）
演算法聽起來很困難，但實際上卻不是如此，你就把它想成：我要怎麼把輸入變成輸出？
例如說三明治這個例子，「做成三明治」的演算法就是

1. 把土司對角切開，變成兩個三角形
2. 在其中一片土司上面抹上沙拉醬
3. 在其中一片土司上面放上肉鬆
4. 在其中一片土司上面放上蛋
5. 把兩片土司蓋起來

有了演算法的概念，最上方的三個流程，就可以改寫為
輸入（input）-> 處理（algorithm）- > 輸出（output）

所以囉，程式其實就是：「輸入一些東西，程式裡面經過一系列的步驟，最後產出結果」
這些東西也可以套用在生活上
例如說你今天想要在電話簿上面找到 peter 這個人，那就會是

1. 從電話簿（輸入）
2. 找出（處理）
3. peter 的電話（輸出）

我們接下來要思考的是中間那一步：該怎麼找？
最簡單直接的方法就是一頁一頁翻，轉化成文字就是

1. 翻開第一頁
2. 找有沒有 peter
3. 沒有，翻下一頁，跳到步驟 2
4. 有，我找到 peter 的電話了！（結束）

跟剛剛做三明治的例子比起來，有發現差在哪邊嗎？沒發現的可以拉回去上面看看
做三明治的流程很固定，你就從 1 做到 5，一條一條順序執行，三明治就做完了
但是翻電話簿的例子，多了兩件事情

第一：條件判斷（Conditions）
在我們執行完第二個步驟之後，才能決定你要執行第三步還是第四步
於是這邊就會有個分支（branch），要嘛你就走三，不然就走四，就像是兩條岔路一樣

第二：重複的動作（迴圈，Loops）
在我們執行第三個步驟的時候，把電話簿翻下一頁之後，必須跳回去步驟2：找有沒有 peter
那如果沒有的話，我們又跳到第三步了
在程式上，我們把這樣「不斷做同樣事情」的動作稱為「迴圈」

（你可以稍微想一下，如果沒有這兩種東西的話，你還能寫出翻電話簿找 peter 的步驟嗎？）

總之，照著上面那四個步驟走，我們就有了一個可靠的程式
但是，有沒有更快的作法呢？

終極密碼

相信大家應該都有玩過「終極密碼」，沒玩過的我大致上簡介一下
基本上就是關主跟闖關者兩個人在玩，看闖關者能不能在「最短的次數」猜到關主的數字
每猜一次之後，關主會根據那個數字給予解答的範圍
例如說關主的數字是：23

1. 關主給範圍：1~100（初始值）
2. 闖關者猜：30
3. 關主修正範圍：1~29
4. 闖關者猜：25
5. 關主修正範圍：1~24
6. 闖關者猜：23
7. 猜中了！

接著問大家一個問題：假如我想要最快猜到，有沒有什麼好的策略？
答案就是：一直對半切！為什麼？因為這樣能夠排除最多的數字
例如說我第一個數字猜50，那會有三種情況

1. 小於50，範圍變成1~49
2. 就是50
3. 大於50，範圍變成51~100

就算是最壞的情況，剩下的數字也會剩50個
那如果我第一個猜 30，也會有三種情況

1. 小於30，範圍變成1~29
2. 就是30
3. 大於30，範圍變成31~100

最壞的情況，還有 70 個數字是有可能的

所以，如果我每次都對半切，我能夠「保證」在一定次數之內猜到結果
最壞的情形是我每次對半的時候都猜不到，就會是

1. 1~100 我猜 50，範圍變成 51~100
2. 我猜 75，範圍變成 76~100
3. 我猜 88，範圍變成 89~100
4. 我猜 94，範圍變成 95~100
5. 我猜 98，範圍變成 95~97
6. 我猜 96，範圍變成 95~95
7. 我猜 95，猜中了

七次之內，一定可以猜到答案
如果有興趣知道為什麼是 7 的，可以自己想想，提示是 2^7 = 128 > 100

好了，可是終極密碼跟翻電話簿有什麼關係？
終極密碼之所以可以有這樣的策略，那是因為「答案有範圍、範圍有順序性」
電話簿也有相同的特性，因為電話簿是從 a 排到 z，就跟字典一樣
因此，我們也可以用終極密碼的方式去找出 peter 到底在電話簿的哪裡

1. 翻開電話簿的中間
2. 看看現在這頁的字母是多少
3. 如果比 p 還大，代表 peter 應該在我現在翻的頁數的前面，所以我可以把後面都撕掉，回到步驟 1
4. 如果比 p 還小，代表 peter 應該在我現在翻的頁數的後面，所以我可以把前面都撕掉，回到步驟 1
5. 如果就是 p，那你就成功找到 peter 的電話了

舉個例子，假設你現在第一次翻翻到 c 好了，因為電話簿有順序性，所以 p 一定在 c 的後面才出現
那你可以把 c 以前的頁數都撕掉了，因為 p 絕對不會在那邊

接著你可以把撕掉後的電話簿當成是「另外一本新的電話簿」
然後再翻開中間，假設你現在翻到 x
因為電話簿有順序性，所以 p 一定在 x 的前面
那你可以把 x 以後的頁數都撕掉了，因為 p 絕對不會在那邊（x 的後面）

接著你可以把撕掉後的電話簿當成是「另外一本新的電話簿」
然後再翻開中間，假設你現在翻到 f
因為電話簿有順序性，所以 p 一定在 f 的後面才出現
那你可以把 f 以前的頁數都撕掉了，因為 p 絕對不會在那邊（f 的前面）

....

講到這裡，相信大家對於這個概念應該都滿熟悉的了
接下來我要給這個方法一個專有名詞：二分搜尋法（binary search）
應用最多的場景就是找數字

例如說我今天有100個箱子，每個箱子裡面都有一顆寫著數字的球，而且箱子是按照球的數字的順序排列的，那我應該怎麼找到「數字為 30 的球」？

1. 我先翻開第 50 個箱子，發現裡面的數字是 200，那因為箱子有順序性，所以 30 一定在第1~49個箱子
2. 我翻開第 25 個箱子，發現裡面的數字是 20 ，那因為箱子有順序性，所以 30 一定在第 26~49 個箱子
3. 以此類推...

之後的作業會需要大家在程式上實作這個演算法
總之這個演算法有一個特性一定要遵守：輸入必須是有序的
例如說今天的數列如果是：1, 9, 3, 20, 33, 7, 5
那我可以用二分搜尋法嗎？當然不行！完全行不通，你可以想想看為什麼

接著來談談進制吧

你可能聽說過一種說法：在電腦的世界裡，只有 0 跟 1
但你可能會好奇：不對阿，那為什麼我可以看到電腦畫面、還可以玩遊戲，0 跟 1在哪裡？

我做一個比喻，「在現實生活中，只有原子的存在，但你還是可以看到人、可以看到動物，而不是看到原子」
0 跟 1 就像是原子一樣，是最底層的東西，可以由這些最底層的東西不斷組織、合併，最後變成我們看到的樣子

因此，你只要記得電腦的「最底層」都是 0 跟 1 就好
只有01的數字系統，我們稱之為「二進位」，就是「逢二進位」的意思，所以你在這系統中，絕對不會看見 2 這個數字
因此我們可以來數數一下
第一個數字：1
第二個數字：10（逢二進位）
第三個數字：11
第四個數字：100（逢二進位）

我們現在日常生活中使用的系統叫做「十進位」，逢十進位，照上面的定義，在這系統裡，你不會看見 10（十）
第一個數字：1
第二個數字：2
...
第九個數字：9
第十個數字：10

咦！不是說不會有 10（十） 嗎？
其實這是因為用文字表示很容易誤解，其實十進位裡面的 10 這個數字，應該唸作 一零 才對
一、二、三....九、一零、一一、一二...、一九、二零
你會發現 10（十） 這個數字，不可能出現在「一個位數」

進制相關的投影片可參考我之前做的：https://slides.com/aszx87410/cs-lesson1/live#/2

接著來看 8 進位好了，可能會更理解一點
第一個數字：1
第二個數字：2
...
第七個數字：7
第八個數字：10（因為不能有8，所以要進位變成 10(一零)）
第九個數字：11

如果你覺得以上你都聽不懂，那我們可以用另外一個角度理解「進制」這個概念
請大家把自己的數學程度退化到國小階段，就能很輕鬆的理解這個段落

123這個數字，該怎麼用數學式子表達？
答案：100 + 20 + 3

那 325 呢？
300 + 20 + 5
那其實 300 + 20 + 5
就是：3*100 + 2*10 + 5*1

那 426 呢？
4*100 + 2*10 + 6*1
或可以寫成：4*10^2 + 2*10^1 + 6*10^0
^是次方的意思，10^2 代表 10 的兩次方，就是 100

再多看幾個例子
5566
= 5*1000 + 5*100 + 6*10 + 6*1
= 5*10^3 + 5*10^2 + 6*10^1 + 6*10^0

6723
= 6*1000 + 7*100 + 2*10 + 3*1
= 6*10^3 + 7*10^2 + 2*10^1 + 3*10^0

沒錯，恭喜你得到了「十進位」的數學意義：以 10 為基底
以此類推，你可以猜猜看二進位的：1001 會是多少？

1001
= 1*8 + 0*4 + 0*2 + 1*1
= 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0
= 9（二進位的 1001 = 十進位的 9）

跟 10 進位比起來差在哪邊？差在它是以 2 為基底
以此類推，如果是八進位的 1001

1001
= 1*8^3 + 0*8^2 + 0*8^1 + 1*8^0
= 512 + 1
= 513（八進位的 1001 = 十進位的 513）

最後來看十六進位
因為一個位數不可能容納兩個數字，所以我們約定
10 = A
11 = B
12 = C
13 = D
14 = E
15 = F
那 16 會是什麼呢？ 會是 10，不知道為什麼的，可以把上面那整段重看一遍了XD

談談編碼

太好了，你現在已經有數字的概念了
因為二進位對我們來說太不方便了，所以一旦你知道各個進制之間怎麼轉換
儘管電腦底層是二進位，你跟他講十進位它也聽的懂

這就像是假設你有一個泰文翻譯
儘管你只會講中文，但我跟你講泰文你也聽的懂

可是在電腦的世界裡面，只有數字是不夠的，文字呢？
我要怎麼表達 apple 呢？

大家應該都有聽過摩斯密碼吧？利用一些「制定好的規則」，把一些符號變成文字
其實每個人都可以定義自己的一套系統，例如說我可以定義：
100 就是 a
200 就是 b
300 就是 c
...
2600 就是 z

這樣子當我寫出：300 100 200 的時候，你就知道我表達的是 cab
可是每個人若是都有自己的規則，不就很麻煩嗎？於是這時候我們需要一個「標準」
這個標準就稱作：ASCII

這個標準定義了
A = 65
B = 66
...
Z = 90

a = 97
b = 98
...
z = 122

大家都知道這份標準以後，我們就可以在電腦的世界裡面用文字溝通了！

可是下一個問題就來了：你剛剛說了 65 是 A 的意思，那我要怎麼表示「數字的65」？
好問題！在不同的場景底下，同一個數字又代表不同意思
例如說 65 可能是文字 A 的意思
也可能是數字的 65
在體重計上，也可能代表 65 公斤
在日曆上，也可能代表 65 天

那至於要怎麼區分是文字還是數字，這個就有點太底層了，我很難解釋XD
這邊想傳達的觀念是：「65 是『原始資料』，要搭配使用場景來看，才能變成有用的『資訊』」

舉例來說，255, 255, 255 這三組數字你看起來可能沒什麼
但是在一些場合底下，這三組數字其實是代表：一個顏色，或是我們稱之為色碼
電腦中的顏色是由 Red, Green, Blue 組成，因此又稱為 RGB 系統
第一個數字代表有多少紅色，第二個代表有多少綠色，第三個代表有多少藍色
範圍是 0~255，而為了方便起見，通常都以十六進位表示，就是 0~FF

FF 00 00，就是紅色
FF FF 00 就是紅色加綠色，也就是黃色
00 00 00 就是什麼都沒有，也就是黑色

如果你今天只單純拿到 FF0000 這組數字
你不會知道這是顏色還是數字，因此我上面才講說，要搭配使用場景來看
因為同一組數字，在不同地方會有不同意思

總結

今天這篇文章大致上講解了一些程式的基本概念以及進制相關的內容
如果你能夠理解我上面講的內容，那 week 0 對你來說應該不是難事
加油吧~