電腦與問題解決 5-1 電腦解題概論 5-2 電腦解題程序 5-3 演算法概論.

Presentation on theme: "電腦與問題解決 5-1 電腦解題概論 5-2 電腦解題程序 5-3 演算法概論."— Presentation transcript:

1 電腦與問題解決 5-1 電腦解題概論 5-2 電腦解題程序 5-3 演算法概論

2 5-1　電腦解題概論 雖然電腦不像人類一樣聰明，不會自主思考解決問 題，但如果我們能以電腦處理問題的方式給予正確 的指令，那電腦就能按照我們的指示處理問題。

3 5-1.1　問題解決的概念 垂直與水平的邏輯思考 人類思考問題的方式可分為垂直 思考(vertical thinking)與水平思 考(lateral thinking) 兩種。 垂直思考又稱為邏輯思考 (logical thinking)，強調按部 就班、循序漸進的流程，則思 考流圖5-1.1。

4 5-1.1　問題解決的概念 水平思考又稱為發散式思考 (divergent thinking)，水平思考 屬於跳躍性思考，思考方向會從 問題的本身四處發散，想法間不 一定會彼此相關聯，也不會有所 謂對與錯的答案。以圖5-1.2。 對電腦而言，垂直式的思考方 式比較容易直接轉化成實際的 解題程式。 水平思考有突破僵直有限的思考模式，找到新解題 方向的特性。

5 5-1.1　問題解決的概念 垂直思考會依循著上一步的結論繼續延伸，步驟與 步驟間也都有邏輯的相關，但假如其中有任何一個 環節錯誤，就可能導向錯誤的結果，甚至是無法繼 續運作的狀況。 水平思考則是不遵循按部就班的思考規則，跳脫出 原有的思考角度來解決問題，甚至是重新組合問題 ，因此通常會出現較新穎的觀點。

6 5-1.1　問題解決的概念

7 5-1.1　問題解決的概念 循序漸進的流程 首先會先思考該以什麼樣的方式解決問題，並規劃 問題解決的流程，但要一邊設計解決步驟還要一邊 考慮各種可能性實在很困難。 因此我們可以先將大項目的動作按步驟列出，有了 雛形之後，接著可以再逐步分解成細項。

8 5-1.1 問題解決的概念 以「計算全班期中考的數學平均分數」範例作說明
5-1.1　問題解決的概念 以「計算全班期中考的數學平均分數」範例作說明 初步提出問題的解決流程後，接著可以嘗試將流程 再細分，例如圖5-1.3 的「計算全班的數學平均分數 」步驟，我們還可以再分解成幾個動作執行，如圖 所示。

9 5-1.1　問題解決的概念 舉一個生活中的解題範例做說明，當我們操作自動 櫃員機進行提款時，自動櫃員機系統會以什麼樣的 步驟處理提款要求？依照循序漸進的概念，我們可 以先初步地將處理步驟規劃成圖5-1.5 狀況。

10 5-1.1　問題解決的概念 圖5-1.6 是理想的提款處理步驟，但實際電腦處理的 流程沒有那麼簡單，並不是使用者輸入任何數字及 金額就可以順利領到錢，對自動櫃員機來說，它必 須確定 輸入的密碼是否正確？ 提款的金額是否有超過當日提取上限？ 或者提款金額是否比戶頭內的存款金額高？ 因此我們可以再延續著圖5-1.5 的規劃，再細分成圖5- 1.6 的狀況。

11 5-1.1　問題解決的概念

12 5-1.2 電腦解決問題 電腦解題的限制 純機率問題 經濟與投資問題
5-1.2　電腦解決問題 電腦解題的限制 純機率問題 電腦可以做到設計亂數選號，或是從過去開獎紀錄統 計出各個號碼出現的次數，讓投注者做為選號的參考 ，但無法保證電腦所選擇的號碼就一定會中樂透。 經濟與投資問題 在投資理財方面，電腦可以根據來自各方的大量數據 如利率、匯率、匯兌、稅賦等數據，從過去的模式推 演未來的趨勢，讓投資人可以做為「參考」。

13 5-1.2　電腦解決問題 法律問題 法官在審判案件時，不會完全依照法條照本宣科地審 理案件，而是依據實際狀況及情節決定結果。 因為法律過程牽涉到邏輯與思辯，若是利用電腦來協 助審理，頂多只是查詢過去的判例，列出觸犯的法條 ，但無法代替法官進行判決。 從以上例子可以總結，只要牽涉到人心理層面，或 是不曉得影響的變數有那些，電腦無法掌握的問題 ，電腦只能提供參考，對解決問題不一定有幫助。

14 5-1.2 電腦解決問題 電腦解題在各領域的應用 日常生活中常能看見電腦代替人類處理各式各樣的 問題，例如： 高鐵購票系統 員工排班規劃
5-1.2　電腦解決問題 電腦解題在各領域的應用 日常生活中常能看見電腦代替人類處理各式各樣的 問題，例如： 高鐵購票系統 員工排班規劃 升學志願分發 ATM 自動櫃員機 投幣式販賣機 網路搜尋引擎

15 5-1.2 電腦解決問題 雖然電腦本身不具有思考能力，卻因為人類依據電 腦能懂的邏輯給予指令，讓電腦依照程式忠實地執 行，進而解決問題。
5-1.2　電腦解決問題 雖然電腦本身不具有思考能力，卻因為人類依據電 腦能懂的邏輯給予指令，讓電腦依照程式忠實地執 行，進而解決問題。 在網路上的應用－搜尋引擎 現今網路資訊發達，找尋資料是不容易的，在這些網 頁中聯繫的橋樑是一個連結一個的超連結，而搜尋引 擎就是利用這個機制而發展出來的。 搜尋引擎利用特殊程式來蒐集資料，這些特殊程式有 多種稱呼，例如爬行器(crawler)、蜘蛛(spider)、機器 人(robot) 等，

16 5-1.2　電腦解決問題 搜尋網頁間的關鍵字，自動地蒐集相關的網頁並紀錄 下來，因為網頁數量龐大，通常機器人全數瀏覽一次 需要約一個月的時間。 有規則次序的排列整理並建立索引(index)，當使用者 鍵入關鍵字後， 搜尋引擎會先檢查索引資料庫並一一 比對在極短的速度裡列出有關聯性(relevance) 的網頁 連結。

17 5-1.2 電腦解決問題 在氣象上的應用－颱風路徑預報 為了有效掌握颱風動態，氣象人員會利用電腦來預測 颱風未來的路徑。
5-1.2　電腦解決問題 在氣象上的應用－颱風路徑預報 為了有效掌握颱風動態，氣象人員會利用電腦來預測 颱風未來的路徑。 電腦可以用來模擬複雜的天氣系統，只要輸入利用儀 器觀測到的各種資料，像是氣溫、濕度、風向和風速 、氣壓等等數據，經過電腦進行複雜的運算，模擬颱 風未來一週可能的路徑。

18 5-1.2 電腦解決問題 在醫學上的應用－醫療診斷專家系統
5-1.2　電腦解決問題 在醫學上的應用－醫療診斷專家系統 在醫學領域裏，電腦也扮演了重要的角色，不僅僅是 門診預約掛號系統，電腦也開始能「看病」。 「電腦醫生」是依靠著一個大型資料庫來運作，當醫 師在看診時，會依照一固定格式將病例輸入至電腦裡 儲存（包含有診斷方式、治療方式、治療結果等）， 資料庫會累積龐大的診斷參考資料。

19 5-1.2　電腦解決問題 當下次醫生在診斷新病人時，將病例資料輸入資料庫 內，並藉著電腦程式的分析比對，就能找出所有相似 的病歷及病徵以作為治療的參考（圖5-1.9）。

20 5-1.2 電腦解決問題 在交通上的應用－火車訂票系統
5-1.2　電腦解決問題 在交通上的應用－火車訂票系統 透過資訊系統管理火車訂票作業（圖5-1.10），利用 資料庫記錄各種會影響火車剩餘座位的資訊（例如列 車車次、預約訂票人數）。 更新資料庫中的各個列車的 剩餘座位資料，如此就能減 少車票超賣，或是造成過多 座位閒置的問題發生。

21 5-2 電腦解題程序 電腦沒辦法像人類一樣自主思考，而無法理解語意 模糊、沒有明確指示的命令。
5-2　電腦解題程序 電腦沒辦法像人類一樣自主思考，而無法理解語意 模糊、沒有明確指示的命令。 若能依照電腦的運作方式循序思考， 先確立問題解決的目標，依照問題分 析→解題方法設計→測試與修正的流 程（如圖5-2.1），以電腦可以處理 的程序來設計解決方法。

22 5-2.1 問題分析 在進行問題分析的過程中，可先從以下重點著手： 了解問題 第一步要做的是要讓問題明確化，了解 問題要達成的目標是什麼？
5-2.1　問題分析 在進行問題分析的過程中，可先從以下重點著手： 了解問題 第一步要做的是要讓問題明確化，了解 問題要達成的目標是什麼？ 已知的資料、狀況和條件是什麼？ 有哪些資源可以使用？ 問題的限制範圍為何？ 將問題描述清楚，才不會搞錯問題的方向，得到錯誤的結果。

23 5-2.1　問題分析 例如我們遇到一個問題：「從學生的期中考的成績 ，比較各科加總的分數，計算班上第一名的各科成 績總平均」，像這樣的問題，可以用以下的條列式 做法，將問題的條件一一釐清： 問 題 目 標： 班上第一名的各科成績總平均。 問 題 範 圍： 班上的期中考成績。 已 知 條 件： 計算學生的各科總平均，是將該名學生各科的分數加 總，除以科目數。

24 5-2.1 問題分析 輸入內容 不明確條件： 各科包含哪些科目？ 在輸入資料時，我們必須注意以下幾個問題：
5-2.1　問題分析 第一名是班上期中考各科分數加總最高分的同學。 不明確條件： 各科包含哪些科目？ 輸入內容 在輸入資料時，我們必須注意以下幾個問題： 輸入的方式 例如用鍵盤輸入用滑鼠點取選單項目或條碼掃描等 方式 輸入資料的型態 決定輸入的資料必須以什麼樣的型態儲存

25 5-2.1　問題分析 輸入資料的長度 限制資料長度的目的，可避免使用者輸入過長的資 料，否則使用者沒有節制輸入超過原本規定的資料 量，會造成資料處理或儲存上的負擔。 輸入不合法資料的處理方式 如果使用者輸入了不合法的資料（例如要求輸入數 字，使用者卻輸入英文），電腦就必須針對這樣的 情況進行處理（例如顯示提示訊息，請使用者重新 輸入）。

26 5-2.1 問題分析 輸出結果 輸出結果指的是「問題要求產生什麼樣的結果」。
5-2.1　問題分析 輸出結果 輸出結果指的是「問題要求產生什麼樣的結果」。 在設計問題的解決程序，除了找出問題要求的輸出結 果，還要考慮以下事項： 輸出的方式 決定輸出的結果要用什麼樣的方式呈現，呈現的方 式可以選擇以螢幕畫面顯示、聲音播放、紙張列印 等，只要符合問題的要求即可。

27 5-2.1 問題分析 輸出的格式 輸出格式可以幫助人們在閱讀資訊時，能夠以有條 理、有效率的方式順利解讀資訊。
5-2.1　問題分析 輸出的格式 輸出格式可以幫助人們在閱讀資訊時，能夠以有條 理、有效率的方式順利解讀資訊。 例如圖5-2.3 列印學生的成績單

28 5-2.1 問題分析 輸入與輸出的對應關係 邊界條件 在進行問題分析時，要特別注意輸入的內容與最後的 輸出結果是否存在對應關係？
5-2.1　問題分析 輸入與輸出的對應關係 在進行問題分析時，要特別注意輸入的內容與最後的 輸出結果是否存在對應關係？ 輸入與輸出的對應關係，關係到我們設計的解決方法 是否值得讓人信賴。 邊界條件 確定邊界條件的目的是為了定義解決問題的「範圍」 ，像是問題有那些限制條件、輸入／輸出的範圍、可 以使用哪些資源等條件。

29 5-2.1　問題分析 例如有個問題要求「找出所有的質數」，如圖 如果沒有明確界定質數的範圍，質數可以是１到無窮 大的天文數字，即使電腦試圖找出所有質數的可能數 值，也不知要運算到何時才能結束問題？ 如果把問題改成「找出1 到100所有的質數」，在解答 問題時就有個明確的範圍。

30 5-2.2 解題方法與設計 搜尋解決方法的相關資源 頭苦思如何去設計方法，而是先去搜尋解決方法的 相關資源。
5-2.2　解題方法與設計 搜尋解決方法的相關資源 頭苦思如何去設計方法，而是先去搜尋解決方法的 相關資源。 想一想是否以前曾經遇過類似的問題，有現成的做法 可拿來套用？ 或是其他人有提出可靠的方法，是否能夠將他人的構 想運用在目前的問題上？

31 5-2.2 解題方法與設計 將問題分解成可解決的小問題
5-2.2　解題方法與設計 將問題分解成可解決的小問題 當我們搜集了解決問題的相關資源， 就可以開始著 手設計問題的解決方法，如果不曉得該從何處著手 ，可以採用分割擊破法(divide and conquer)。 將問題分解成多個能被我們處理的子問題，之後每 個子問題再列出可行的解決方案（見圖5-2.5）。

32 5-2.2　解題方法與設計

33 5-2.2 解題方法與設計 以規劃線上考試系統為例，將問題分成幾個層面來 討論，並列出相關的解決方案。
5-2.2　解題方法與設計 以規劃線上考試系統為例，將問題分成幾個層面來 討論，並列出相關的解決方案。 以樹狀圖的方式進行整理，如圖5-2.6 所示，就可以 將複雜的問題進行分解，變成簡單、容易處理的項 目。

34 5-2.2　解題方法與設計 設計執行流程 設計執行流程的目的，就是規劃要達成一項功能， 需要執行哪些步驟，將這些步驟按照順序組合起來 ，就可以形成流程。 例如以前面的線上考試系統為例，我們想要實作列 印成績單的功能，如圖5-2.7。 我們可以利用一些工具，例如虛擬碼、流程圖 ，清楚的表達執行流程。

35 5-2.2　解題方法與設計

36 5-2.3 測試與修正 設計好的解題方法必須進行測試，找出是否有潛在 的問題，再針對有問題的地方進行修正，使解題方 法能變得更加完善。
5-2.3　測試與修正 設計好的解題方法必須進行測試，找出是否有潛在 的問題，再針對有問題的地方進行修正，使解題方 法能變得更加完善。 測試資料的設計 測試程式是否運作正常，你可以設計兩種類型的資料 來測試程式，一種是正常值的測試資料，目的是測試 程式是否能處理符合原本功能要求的資料。

37 5-2.3　測試與修正 例如有一個程式只要輸入的數值是質數，就會顯示「 是質數」的訊息，如圖5-2.8 輸入正常值（也就是2、 3、5、7 等質數）進行測試程式是否能正常且正確地 運作。

38 5-2.3　測試與修正 除了正常值以外，另一種是異常值的測試資料，目的 是測試程式是否會因為異常的輸入資料，導致程式出 現錯誤的結果或程式執行失敗。 以前面測試質數程式的例子來說，用異常值資料測試 就是輸入偶數、中英文、空白⋯之類的資料（如圖5- 2.9），測試程式是否會出現問題。

39 5-2.3　測試與修正 錯誤的偵測方式 程式在執行時，若無法依照我們預計的要求產生正確 的執行結果，這樣的情況便稱為程式錯誤(bug)，表 列出一般常見程式錯誤的類型。

40 5-2.3　測試與修正 在程式的執行過程中難免會出現錯誤，如果想要找出 程式出錯的地方加以修正，好讓程式執行可以產生正 確的結果，通常可以利用下列幾種方式偵錯： 逐行偵錯 分段偵錯 監看特定內容 如果知道程式執行時，某些內容（例如計算找零金 額，）會影響最後的輸出結果，只要監控特定內容 的變化（監看購買數量的數值），就可以找出程式 出錯的地方。

41 5-3 演算法概論 要電腦執行一項特定的工作，也要告訴它「該如何 去做」！
5-3　演算法概論 要電腦執行一項特定的工作，也要告訴它「該如何 去做」！ 演算法的功用，就是告訴電腦完成這項工作要執行 哪些步驟，當電腦遇到同樣的工作，就可以照這些 步驟就可以將工作做好。

42 5-3.1　演算法的特性 由於電腦只能依照「程式」指示逐步完成指定的工 作，因此在設計程式時，必須先將問題分解成許多 小步驟，然後再依一定的次序逐步執行，而這個描 述問題解決程序的方法便稱做演算法(algorithm)。 在此引用Horowitz、Sahni 和Dinesh 在《 Fundamental of Data Structures in C++ 》一書 對「演算法」的定義：為解決某一問題或完成特定 工作，一系列有次序且明確的指令集合。

43 5-3.1 演算法的特性 所有演算法都會包含以下特性： 輸入(input) 輸出(output) 明確性(definiteness)
5-3.1　演算法的特性 所有演算法都會包含以下特性： 輸入(input) 演算法在運算前通常會有一些事先給定的輸入資料。 輸出(output) 演算法的目的就是產生結果，至少要有一項的輸出結果。 明確性(definiteness) 每個執行步驟都必須明確而清楚，不可存在模稜兩可的情 況。

44 5-3.1 演算法的特性 有限性(finiteness) 有效性(effectiveness)
5-3.1　演算法的特性 有限性(finiteness) 在任何情況下演算法一定要在有限的步驟內完成，不 能無限期執行。 有效性(effectiveness) 演算法所描述的執行過程可以用人工的方式（例如用 紙、筆），在一定時間內推算出相同的結果。

45 5-3.2 演算法的表示方法 演算法的基本元件 輸入 輸出 演算法可以允許輸入多個資料， 甚至也可以不用輸入 資料就能進行運算。
5-3.2　演算法的表示方法 演算法的基本元件 輸入 演算法可以允許輸入多個資料， 甚至也可以不用輸入 資料就能進行運算。 輸出 演算法的目的是為了解決問題，因此最少要產生一個 輸出結果（例如數值、文字、聲音、影像⋯）

46 5-3.2 演算法的表示方法 處理程序 處理程序是產生輸出結果的一連串動作流程。
5-3.2　演算法的表示方法 處理程序 處理程序是產生輸出結果的一連串動作流程。 例如我們要完成「購物」這個動作，就要如圖 所示，執行一連串的動作才能完成。

47 5-3.2　演算法的表示方法 條件判斷 例如以前面的購物動作為例，我們可以在第二步加入 條件判斷的動作（如圖5-3.2）。

48 5-3.2　演算法的表示方法 演算法基本元件組合 演算法是由輸入、輸出、處理程序與條件判斷這幾 個基元件所組成的，因此只要將這些元件組合起來 ，就可以利用來解決問題。 例如我們設計一個計算學生英文成績總平均的演算 法（如圖5-3.3）

49 5-3.2　演算法的表示方法 當我們想將演算法的運作流程傳達給其他人了解， 可透過虛擬碼( pseudocode ) 或流程圖(flowchart) 來描述演算法的運作。 虛擬碼 虛擬碼(pseudocode) 是一種介於一般語言與程式語言 之間的語言碼， 用一種類似程式碼的文字敘述方式（ 中文、英文不拘） 表達程式的邏輯架構與執行程序。

50 5-3.2　演算法的表示方法 流程圖 隨著問題的複雜性逐漸增加，若用文字方式來說明會變 得冗長，這時便可利用流程圖(flowchart) 增加演算法 的說明性。 流程圖是由美國國家標準協會(American National Standards Institute，ANSI) 所制定，藉由各種特定圖 形符號來表示的演算法。

51 5-3.2　演算法的表示方法 下表5-3.1 是流程圖的常用符號。

52 5-3.2　演算法的表示方法

53 5-3.2 演算法的表示方法 比起文字敘述，使用流程圖描述演算法有以下的好處：
5-3.2　演算法的表示方法 比起文字敘述，使用流程圖描述演算法有以下的好處： 對於複雜的演算法結構， 流程圖比虛擬碼更能瞭解整個 流程，方便進行除錯。 修改方便， 可隨時加入或刪減流程圖的圖形符號。 可增加演算法的可讀性。 移交程式給他人進行維護， 附上流程圖可幫助對方暸解 整個程式的處理流程和細部結構。

54 5-3.3　結構化程式設計 如果程式沒有一定架構， 完全隨著自己的喜好撰寫 程式， 當程式碼變得很龐大時，就會看起來雜亂無 章，讓維護程式碼的人很難進行維護。 荷蘭的數學家戴克斯特拉(Edsger W. Dijkstra) 提出 結構化程式設計(structured programming) 的概念 ，強調程式要簡單明瞭，我們必須遵循以下原則： 採用由上而下的方式將程式分解成多個模組，每個 模組分別負責一件獨立的工作。 每個模組只能有一個入口以及一個出口。 每個模組可以由循序、選擇、重複結構構成。

55 5-3.3　結構化程式設計 由上至下的設計方式 由上而下的設計方式是一種將問題分解成多個能被 處理的子問題，並透過解決這些子問題來解決整個 問題的方法。 例如圖5-3.6 設計文書編輯軟體:

56 5-3.3　結構化程式設計 模組 模組是一個日常生活中常見的概念，舉例來說，電 腦就是模組的實例，它是由主機、鍵盤、滑鼠、螢 幕、喇叭所組成。 在開發程式時，使用模組的方式就是將程式分成多 個模組。

57 5-3.3　結構化程式設計 像圖5-3.8 組合模型機器人一樣，每個模組只負責一 件工作，一旦某個模組出現問題，我們可以停止這 個模式的運作，或是換成其他程式模組來取代，就 不會因某個小問題出現，使整個系統無法運作。

58 5-3.3　結構化程式設計 循序、選擇與重複結構 戴克斯特拉(Edsger W. Dijkstra) 認為， 每個程式都可應用循序結構、選擇結構 與重複結構組合而成。 這三種結構又稱為程式的基本結構： 循序結構 是指從上而下， 依序執行的結構。 舉例來說，將領取消費券的流程 以循序結構來表示，做成循序結構 的模組如圖5-3.9 所示。

59 5-3.3　結構化程式設計 選擇結構 測試某一條件並按其結果來改變執行路徑的結構，例如 以選擇結構表示外面是否下雨，再決定接下來要做什麼 事？（如圖5-3.10所示）。

60 5-3.3　結構化程式設計 重複結構 測試某一條件是否成立以決定是否重複執行某一段程式 ，以數學考試為例（如圖 所示）。

61 5-3.4　資料結構與演算法 PASCAL語言之父威爾斯教授(Prof. Niklaus. Wirth) ，在它的著作《Algorithms＋Data Structures＝ Programs》提到「程式＝演算法＋資料結構」的概 念。 什麼是變數 在介紹資料結構之前，首先介紹什麼是變數(variable) ？變數是構成程式的重要元素之一。

62 5-3.4　資料結構與演算法 它可以暫存我們輸入的資料，還可以隨時修改內容。 為什麼要有「變數」這樣的設計？我們可以把變數想 像成用來放置各種物品的「箱子」，如圖 所示

63 5-3.4　資料結構與演算法 變數的資料型態 我們可以把變數想像成搬家時用來裝東西的「箱子」， 如果都使用同一種尺寸的箱子，就會發生下列狀況: 一旦箱子太大，東西會裝不滿，箱子一多就容易佔空間 如果箱子太小，會有很多東西放不進箱子（圖5-3.13）

64 5-3.4 資料結構與演算法 因此，並不是每一種類型的資料，都可用同一種「箱 子」來存放，必須根據資料類型的不同而有所變化。
5-3.4　資料結構與演算法 因此，並不是每一種類型的資料，都可用同一種「箱 子」來存放，必須根據資料類型的不同而有所變化。 程式語言常用的資料型態有整數（包含長整數）、浮 點數（可分為單精度和倍精度浮點數）、字串、布林 、日期等型態，下表5-3.2 以 Visual Basic 為例介紹變 數的資料型態。

65 5-3.4　資料結構與演算法

66 5-3.4 資料結構與演算法 資料結構的類型 資料結構是讓資料存取更有效率的方法。 在程式中適當應用資料結構，會有以下好處：
5-3.4　資料結構與演算法 資料結構的類型 資料結構是讓資料存取更有效率的方法。 在程式中適當應用資料結構，會有以下好處： 可讓演算法的設計變得簡單易懂，使程式更容易維護。 可減少大量程式碼的撰寫，提升程式的執行效率。 可減少記憶體空間的浪費，讓電腦不會耗用太多的系統 資源。

67 5-3.4 資料結構與演算法 以下列舉幾種常見的資料結構類型， 例如陣列、堆疊 、佇列、樹狀結構等，相關的說明如下： 陣列
5-3.4　資料結構與演算法 以下列舉幾種常見的資料結構類型， 例如陣列、堆疊 、佇列、樹狀結構等，相關的說明如下： 陣列 陣列(array) 是最常見、使用率最高的資料結構，它 是由多個元素組成的集合，要存取陣列中的每個元 素要指定該元素的索引值(index value) 來存取。 我們可以把陣列想像成一個放很多張學生成績單大 抽屜，例如 圖5-3.14。

68 5-3.4　資料結構與演算法 一般常用的陣列有一維陣列(one -dimension array) 和二維陣列( two dimension array) 兩種類 型，如圖5-3.15

69 5-3.4　資料結構與演算法 堆疊 堆疊(stack) 是一個串列，它的兩端分別稱為頂端 (top) 和底端(bottom)，資料的推入(push) 和彈出 (pop) 都在頂端(top) 執行，採用後進先出(last in/ first out，LIFO) 的處理方式。 就是最後進來的資料優先處理。（如圖5-3.16）。

70 5-3.4　資料結構與演算法 由於堆疊的特性是後進先出，因此電腦上的副程式 呼叫(subroutine call)就利用這個特性管理副程式 的執行。 佇列 佇列 (queue) 和堆疊的性質相近，只是佇列加入資 料的方式，就像排隊一樣。 佇列資料是固定由尾端（tail，或稱末端rear）加入 ，讀取資料時則固定由頭端（head，或稱前端 front）開始，最先進來的資料優先處理，屬於先進 先出 ( first in /first out，FIFO ) 的處理方式。

71 5-3.4　資料結構與演算法 樹狀結構 樹狀結構( tree ) 是一種階層式的資料表示方式， 是指一個元素可以像樹枝般分成多個元素的結構。 樹狀結構如圖 。

72 5-3.4 資料結構與演算法 最上層是由根( root ) 為起點， 向下可分成數個節點(node)，
5-3.4　資料結構與演算法 最上層是由根( root ) 為起點， 向下可分成數個節點(node)， 節點和節點之間連起來的線條稱為分支(branch)。 若以節點的上下關係來看，位於上層的結點稱為父 節點(parent)，位於下層節點稱為子節點(child)， 位於最下層沒有分支出子節點的節點稱為葉節點 (leaf)。

73 5-3.4　資料結構與演算法 樹狀結構適合用來表現具有次序性、階層性、從屬 性的資料，因此像是族譜、組織圖、電腦的檔案目 錄結構，都很適合用樹狀結構來表示（如圖 所示）。

74 5-3.4　資料結構與演算法 資料結構與演算法結合 在演算法中使用資料結構，究竟有什麼好處？

75 5-3.5　演算法與程式語言 程式語言(programming language) 是指使用者用 來與電腦溝通之文字記號所形成的集合，也就是電 腦能夠接受的語言。 程式語言的種類繁多，且各有其特定的文法（或稱 語法）結構與適用範圍。透過各種程式翻譯器，不 同的程式語言最終都會被翻譯為相同形式。

76 5-3.5 演算法與程式語言 程式語言可分為低階語言、高階語言兩種，以下將 分別簡單介紹。 低階語言
5-3.5　演算法與程式語言 程式語言可分為低階語言、高階語言兩種，以下將 分別簡單介紹。 低階語言 低階語言(low-level language) 指的是會隨著使用的 CPU 架構不同而有顯著的差異的語言，包括機器語言 與組合語言。 優點是執行速度快，不過編寫程式較困難且程式碼不 易理解。

77 5-3.5 演算法與程式語言 第一代語言：機器語言 第二代語言：組合語言
5-3.5　演算法與程式語言 第一代語言：機器語言 機器語言(machine language) 以二進位代碼表示指令 （例如「0000」表示載入，「0001」表示儲存）。 對人類而言不易閱讀及使用，但卻是電腦所能處理最直 接的語言。 第二代語言：組合語言 第二代語言：組合語言由於機器語言對程式設計師來說 並不方便，因此後來設計出一種使用英文簡寫來代表各 種基本運算的語言。

78 5-3.5　演算法與程式語言 這些以英文簡寫所構成的語言叫做組合語言(assembly language)。組合語言必須先被翻譯成機器語言後才能 被電腦接受，擔任這個翻譯工作的程式叫做組譯器 (assembler)，如圖5-3.20。

79 5-3.5　演算法與程式語言 高階語言 高階語言(high-level language) 的語法已經接近人類 日常生活用語，簡單易懂，在高階語言中，一個命令 就可以代表數個組合語言中的命令。 第三代語言：程序式語言和物件導向語言 程序式語言(procedural language) 將重心放在解決問 題的程序，設計師必須仔細思考各步驟的細節並進行控 制， 例如FORTRAN、COBOL、BASIC、C、Pascal 等 都是程序式語言的代表例子。

80 5-3.5 演算法與程式語言 為了讓程式碼可再度使用，不用再重複撰寫同樣的程式 碼，而導致程式開發的效率下降。
5-3.5　演算法與程式語言 為了讓程式碼可再度使用，不用再重複撰寫同樣的程式 碼，而導致程式開發的效率下降。 用物件導向語言開發程式，可以將相關程式碼結合成物 件，要開發程式只要將相關的物件組合起來，可以提升 程式開發的效率，例如C++、Java 等都是物件導向語 言的代表。

81 常見的第三代語言 雖然程式語言已經發展到第五代，但是第三代語言 （高階語言）的嚴謹架構及富有彈性的設計能力仍使它極 受歡迎與重視，簡單介紹常見者如下表5-a。

82 常見的第三代語言

83 常見的第三代語言 另外，隨著時空背景不同，許多人開始學習運用簡 單的語法與邏輯概念來控制或增強應用軟體的功能，網際 網路的風行也帶動標記和文稿語言的發展，如表5-b。

84 5-3.5 演算法與程式語言 第四代語言：目的導向語言
5-3.5　演算法與程式語言 第四代語言：目的導向語言 第四代語言（fourth generation language，簡稱 4GL ）是使用者導向的語言。 它和程序式程式語言最大的不同，在於它是以程式的 「目的」為設計重心而非如第三代語言以「過程」為 法則。 因此「要做什麼？」比「如何做？」更重要，程式設 計師只需寫出「要做什麼？」，無需瞭解電腦是如何 去執行的，例如：

85 5-3.5　演算法與程式語言 4GL 比第三代語言缺少了控制性及設計彈性，執行速 度也比較慢，然而其易學易用的特性畢竟非第三代語 言所能比擬，因此至今在資料庫處理的領域裡，4GL 仍然保有一片天空。 例如結構化查詢語言(structured query language， SQL) 就是典型的代表實例。

86 5-3.5 演算法與程式語言 第五代語言：人工智慧語言
5-3.5　演算法與程式語言 第五代語言：人工智慧語言 第五代程式語言的發展目標為利用人工智慧技術，使 其接近人類使用的自然語言（如英語），在撰寫程式 控制電腦處理工作，就有如我們在和電腦對談一般， 例如： 現今開發的產品則多是以LISP或Prolog 語言為基礎， 專為特定領域設計的知識庫系統(如醫療、財經），或 是智慧型的資料庫存取工具。

87 高階語言的翻譯程式 電腦不能直接接受以高階語言所寫成的程式，必須 先轉換成機器語言後才能執行，而依轉換工具不同可分為 直譯器及編譯器二種，如下表5-c。

88 高階語言的翻譯程式