Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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到無窮 大的天文數字,即使電腦試圖找出所有質數的可能數 值,也不知要運算到何時才能結束問題? 如果把問題改成「找出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 高階語言的翻譯程式


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

Similar presentations


Ads by Google