Yuanchieh's Blog

Yuanchieh's Blog

生命是長期而持續的累積

19 Feb 2019

CS50 — lecture 0

最近在教人寫程式,發現自己雖然有寫部落格的習慣,但是要如何用口語表達卻還有很大一段的落差,更困難的是「我不知道從何教起」

先前看到有人分享到 大腦其實是善於記憶,因為思考太花能量,所以大腦經過反覆的練習就會將成果內化為記憶;
而教學就是加速這個過程,並提供學習方更有動力,希望可以自己上完課後可以更懂得如何教其他人用快樂的方式學寫程式XD

電腦科學 Computer Science 在做什麼

提到電腦科學,大家的刻板印象通常是 一個帶著反社會人格的帽T男瘋狂敲著電腦寫程式,但其實電腦科學專注於 解決問題

input -> [ ] -> output

輸入我們想要解決的問題,通過中間黑盒子的運算,我們得到問題的解法。

數人問題

今天假設要數幾個人來上課,我們可以在黑板上,用「正」字符號表達,一個人頭代表一比,最後累積起來看有多少人;

但如果沒有黑板,我們可以用手指頭來數,手指升起代表加一,但是一隻手指有五根手指頭,這樣我們的上限只能數到五,這樣似乎有點少 ?!

回過頭來思考,在人類世界常用 10 進位制,一個位數只能表達 0–9,但如果我們加入進位的概念,例如 123,這代表的是

123 => 100 * 1 + 10 * 2 + 3 * 1 = 123

同樣的如果數手指用不同的 模式 表達,例如說手指舉起代表 1,手指收下代表 0,並加入了進位的概念,這樣的話數手指可以表達的數字範圍變得更大了,例如我想要比 9可以用

01001 => 0*16 + 1*8 + 0*4 + 0*2 + 1*1 = 9(十進位)

數手指的表達範圍瞬間從 0–5 變成 0–31,這也就是二進位的表示法。

除了用手指表示,我也可以用手機的手電筒開光代表 0 / 1,眾所皆知目前大多數電腦只能分辨 0 / 1,也就是電源的開與關,或更精準的說是電晶體狀態的表示;
而但一一個位數 0/1 我們稱為 位元(binary / bit) ,五根手指頭代表我們用 5個 bits來運算,而 8 bits 會稱為 位元組(byte)

但對人類來說,兩者數字想表達的概念是一樣的,但 (二進位)01001 還是不太直觀,此時我們可透過轉換公式變成我們好理解的表示法 (十進位) 9。

數字如何表達文字

人類除了數字外,我們還想要傳遞文字訊息,例如說 ABCD….,單純用多個0,1該如何表示呢?

剛剛提到,我們可以將 01001 轉換成 9,那同樣的我們修改轉換公式,就可以輸出不同的結果。

在電腦世界中,最基礎的編碼方式是 ACII,透過 8 bits 為一組表示,總共 對應128個常用的美國輸入字,例如說 A 是用 65 表示,也就是 0100 0001,當電腦收到後會自動以 8個bit為單位切割,透過一張轉換表,將二進位轉換成文字。

73 72 33 => 收到這三個字用 ascii 轉換會變成什麼呢 ? => HI!

但如果是繁體輸入,中文字遠遠超過 128個,又或是其他國家不同語言,ascii 顯然遠遠不夠用,後來出現了 unicode 萬國編碼,用更多的 bits 表達一個字,解決文字顯示的問題。

數字如何表達圖像

同樣是收到很多的 0/1,這時候我們需要不同的轉換方式,常見的色碼系統是 RGB,用三個數字 表達紅、綠、藍的深淺程度,從0–255,三者混合就變成了色彩;
為了表達 0–255,我們需要 8 bits。

所以剛才的 (73, 72, 33) 在 ascii 中代表 HI!,但是在 RGB中代表的是淺黃色。

在螢幕上,一張圖片其實近看是由許多許多的像素 pixel組成,一個pixel顯示一個顏色,也就是3個一組的8bits。

而影片,則是由一張張圖片連續快速播放所構成。

抽象化

剛才提到了電腦用二進位,但為了人類的需求,我們又把 0/1 轉換成不同的表示法,例如說有 十進位轉換成易讀的數字、ascii轉換成文字、RGB轉換成顏色,這個轉換的過程我們稱為「抽象化

抽象化的概念在電腦科學非常的基本與重要,抽象化是指

我們不用管底層的實作方式,注重於概念上的表達

例如說 一個像素是由 3 byte 組成 -> 多個像素可以組合成一張圖 -> 多張圖快速播放可以組成一部動畫,透過一層一層的抽象化,可以做到更多的事情。

同樣的,平常我們在使用計算機算數學、上網傳訊息、看圖片看影片,我們完全不用去管背後是用多少個 0/1 去表示,只要電腦可以自動幫我將 binary 轉換成我需要的顯示就好了。

總結以上,電腦最終只看得懂 0/1 ,而對於人類有意義的是 數字、文字、像素等,可以透過不同的轉換方式構成不同的表達 Expression,也就是 Input / Output 的格式。

演算法

剛才提到,電腦主要功能是在於解決問題

input -> [ algorithm ] -> output

中間的運算過程稱之為 演算法 algorithm

電話簿找人

今天桌上有一本電話簿,裡面按照英文字母順序排列,希望可以找到「Mike Smith」的電話號碼,此時我們可以怎麼做?

  1. 從第一頁,一個一個查閱,但這會非常花時間,尤其是電話簿如此大一本
  2. 兩頁兩頁翻,如果翻到過頭就在往回翻一頁,這個做法會比第一個省下一半的時間
  3. 直接翻到電話簿的中間,如果目標的英文字母順序在後半段,我只要翻後半段的電話簿就好,另一半直接丟掉,反覆這個過程,就可以非常快找到;
    這也就是 二元搜尋法 Binary Search

在電腦科學中,通常我們會說第一種是暴力解,就是用最直觀最原始的方式解決問題;
但通常這樣暴力解效率都不高,會開始逐步優化,優化有很大的方向是 拆分擊破 devide and conquer,將大問題拆解成小問題,並透過持續解決小問題就可以得到最後的答案;
例如説翻電話簿,我先從中間對切,問題量(需要查閱的電話數)就剩一半了,再持續對切,問題越來越小,直到找出答案。

我們可以用數學函式圖形表達演算法的效率,x 軸代表問題需要花費的步驟,而y軸代表問題的數量

以電話簿找人為例,y軸代表的是電話簿的厚度,x軸的話舉第一種演算法來說,代表説電話簿多厚,演算法就需要翻閱多少頁才能解決問題。

這邊僅簡略帶出 演算法複雜度的概念

Pseudocode

剛才三種演算法都有一個解決問題的流程,我們可以用 偽代碼 pseudocode ,用一種類似於草稿的概念,表達我們實際解決問題步驟。

圖片出自於影片內容 圖片出自於影片內容

這裡可以細拆成四個部分

  1. Function: 代表某種動作 pick up / open / look / call / quit
  2. Condition 判斷機制 if / else if
  3. Boolean Expression 實際判斷的條件 if Smith is earlier in book
  4. Loop 持續的做某件事 go back to step 2
  5. Variable 暫存結果的變數
  6. Thread (進階) 多工處理
  7. Events (進階) 事件觸發

Let’s Write Some Scratch!

Scratch - Imagine, Program, Share

Scratch 是 MIT 開源的一套用圖形介面程式語言編輯器,透過拖拉的方式,用最簡單的方式就可以寫程式,看到某些範例,覺得功能很完整,能夠發揮的空間十分的大。

以下挑選幾個範例做說明

Scratch 註冊後主要有三個區塊,右邊的執行結果頁、中間的程式邏輯、左邊的程式元件,設計的都相當直覺。

在開始 Scratch 時,都會透過綠色的旗幟符號開始,所以程式碼會先放上圖橘色區塊開始執行,後續依照積木的順序,執行你設計的演算法,例如最基本的「Hello, World!
Hello, World! 是程式界在嘗試新事物的第一個慣例測試,主要是因為某位大神寫了一本非常知名的書,裡頭的第一個範例就是 Hello, World! ,後續就演變成一種文化。

Loop

我希望發出喵聲4次,中間相隔一秒鐘,可以看到以下有兩種寫法

左邊是很直覺的寫法,我要 Meow 四次我就複製貼上四次,但這樣最大的缺點是如果要十次同樣的事情就要做十次…. ,又或是我想要變成 Woof,就需要改十次;
遇到重複做某件事數次,可以改用 Loop 的概念,讓程式自動重複而不用一個一個的自己手動作。

Don’t Repeat Yourself (DIY)

是寫程式一個很重要的原則。

Condition

這裡我寫的邏輯是
定義一個變數 counter,在開始執行後將 counter 設為 0,接著當每次按下 Space 後,顯示 counter 數值,接著將 counter 每次都加 1;
如果目前 counter > 10,就不要發出聲音,反之 Meow 一聲。

Function

類似於上面的事情,但我這時候希望可以目前 counter 多少就 meow 幾次,此時我們需要 Function 的幫忙;
先定義一個自己客製的 Block,這個 Function 的內容就是 Repeat Meow 數次,次數由參數 n 決定。

當然也可以直接把 repeat 那一整段直接塞到 else 當中,但是Function 的好處是可以將某些行為從程式碼中抽取出來,這樣可以讓程式碼更好理解,閱讀到 MeowManyTimes 可以從字面上的意思很直覺想到這是跟發出 Meow 有關。