基礎演算法筆記

最近二週在讀一本由日本人所寫的「if 與 else 的思考術」,副標題為:程式設計邏輯腦的養成講座。
ifelse
感覺這是一本TOT(training for trainer)的程式教學入門書,所以內容反而不是標準的電腦技術教課程編排寫作:用太過複雜磝口的技術用語、程式規定語法結構、上百行的函數與程式碼來嚇走讀者(尤其是我這種沒任何程式編碼基礎背景者),而是作者想像如果你(讀者)如果要教別人(可能也是無任何基礎背景者)寫程式、認識電腦操作,甚致是其它任何一種學科的入門式教學法,講師要如何掌握住學習對像的興趣與借由互動提高學習成果,在這本書當中作者循循善誘的提示法倒是對我有一點啟發,即使只是從書面上看到內容,反而讓我更願意主動去思考:嗯這個題目解出來,那程式碼有沒有改善把它寫得更簡潔的地方,有沒有沒考慮到的bug、除了解決了這樣的題目外進一步更複雜的廷申題要如何來處理?(當然以我的程度,這些題目在程式能手眼中根本也不是什麼難題)

本文重點仍在該書第六章「值得學會的演算法」部份的一些筆記。作者提到程式學習者最好應該熟練且學好的基礎演算法建議如下:
1.排序演算法
*氣泡排序法
*選擇排序法
*插入排序法 
2.搜㝷演算法
*線性搜㝷法
*二分搜㝷法
3.其它演算法
*輾轉演算法
*質數演算法
*閏年演算法

其它演算法
*輾轉演算法:求得兩個整數之間的最大公因數
機械化地求取二數字之間最大公因數的步驟:
由比較大的數字減去比較小的數字,直到二者相等,則相等的數字即為最大公因數(據說這是小學中所教的求出最大公因數的作法,但我一直想不起來,只記得要先拆解因數再來求二者的共同因數與最大公因數)

原書是以C語言為示範教材,我後來分別試著用python和javascript來練習這些題目(果然一個月沒碰javascript,許多基本的語法函數又要重新查找熟悉Orz),並透過GitHub Gist可以在部落格上顯示出高亮程式碼的支援功能來把它貼上(後面為了節省gist,只有貼python程式碼)
#####python

#####javascript


*質數演算法:判定某個整數是否為質數?
質數a:無法被其它整數整除的數字
機械式步驟:a是否能被2~(a開根號)之間的數字整除(最笨的方式當然是從2算到a之間是否有整數可以被a整除,但想像a若被2除盡, 則其除2所得的商數x同理也可以被a整除,故一直計算到a的開根號即可
演算法設計思考訣竅:從基本解決問題的步驟到找到步驟中是否有其它規律以提高效率減少電腦執行的資源。
#####python


*閏年演算法
閏年實際規則:西元年份可被4整除,且不能被100整除,但可以用400整除。
########python


延伸應用==》
如何找出二個整數之間的最小公倍數? 
如何找多二個數字以上的最大公因數?
如何找出二個數字以上的最小公倍數?

排序演算法

:升幕或降幕(由小到大或由大到小依次序排列)
*氣泡排序法:兩兩相比,最小者(或最大者)從隊伍中不斷地往前出現,就如何池底的氣泡浮上水面。
*選擇排序法:掃視出一組數字中最小數字(或最大)然後將其排到最前頭,剩下照前一步驟依次完成排序。
*插入排序法:按數字大小來決定其排列的位置。

搜㝷演算法


*線性搜㝷法(linear search):從資料最前端開始一個一個比對,以查找出要找的數字,在資料一致時就結束的反覆結構。
**「保護數字」的線性搜㝷法:從中任抽一個數字作為「保護數字」(即要找的數字),將該數字為放在這組數字的最末端,第一步以「保護數字」作為每一個比對數字的值,第二個動作檢查所比對的數字有無超過尾端)
*二分搜㝷法:如資料已順序排列,則使用二分搜㝷法會比前述的線性搜㝷更有效率。一組數字為升幕排序(由小到大),故以先檢查最中間的資料,立刻能將搜㝷範圍減半,這樣減半再減半地縮小範圍方式,可以很有效率地找到想要的東西。

複雜度:為判斷花在演算法上的處理時間,故利用了「複雜度」 (complexity)概念,其是一般對應於資料庫,所使用的符號為大O符號(Big O notation)。例如在線性搜㝷中最糟情況
的複雜度為O(n),即處理時間與n成比例。而若以二分搜㝷則其最複雜的狀況則以O(log n)來表示,即指處理時間與log n成比例

0 意見:

Security First: umbrella app 中文化滙整

之前提過會作一篇 Security First's umbrella app 滙整與中文化超連結整合,以讓未下載使用、觀看過原手機應用的讀者(其實指的就是錯亂的我自己本人)稍能有全盤的概念來想像這個手機應用程式(或更精準的說:一個手機上的隨身電子書)的內容。好了,本文...