13-1 電腦可以協助解決哪些問題 13-2 電腦解題簡介 13-3 電腦解題規劃－演算法 13-4 認識資料結構 第13章 電腦解題與演算法 13-1 電腦可以協助解決哪些問題 13-2 電腦解題簡介 13-3 電腦解題規劃－演算法 13-4 認識資料結構

電腦可以協助解決哪些問題 電腦應用的領域，如科學研究、軍事發展、醫學實驗、氣象預測、生活應用等 網路訂票 網路資料的搜尋 颱風預測 （http://www.google.com.tw/） （http://photino.cwb.gov.tw/） 網路訂票 網路資料的搜尋 颱風預測 （http://irs.thsrc.com.tw/IMINT） 第13章 電腦解題與演算法 / 13-1 電腦可以協助解決哪些問題

電腦解題簡介(1/3) 垂直式邏輯思考又稱為「收斂式思考」 透過反覆的思考與求證等過程，找出解決問題的方法 適用在科學研究、數學運算及電腦解題等邏輯性思考的問題 第13章 電腦解題與演算法 / 13-2 電腦解題簡介

電腦解題簡介(2/3) 垂直式邏輯思考問題的範例 ●2GB單位價格 = 1,800/2GB = 900 問題：某家商店1GB的RAM 1,000元，2GB的RAM 1,800元，如何用5,000元買到最多容量的RAM？ 1.根據問題得知以下4個線索： 2.計算1GB與2GB RAM的單位價格，比較何者便宜？ 　●1GB單位價格 = 1,000/1GB = 1,000 　●2GB單位價格 = 1,800/2GB = 900 3.因為2GB RAM的單位價格較便宜，所以應儘量多買2GB的RAM 答案：買2GB的RAM 2條、1GB的RAM 1條，共花用4,600元 可花用的金額為5,000元 1GB的RAM 1,000元 2GB的RAM 1,800元 RAM不能分割出售 答案 第13章 電腦解題與演算法 / 13-2 電腦解題簡介

水平式邏輯思考(1/2) 水平式邏輯思考又稱為「發散式思考」 是一種不受既有事物或觀念拘束的思考方式，來激發創意或尋求新的見解 適用在藝術創作、創意研發等領域 第13章 電腦解題與演算法 / 13-2 電腦解題簡介

水平式邏輯思考(2/2) 水平式邏輯思考問題的範例 問題：某家商店1GB的RAM 1,000元，2GB的RAM 1,800元，請問如何用5,000元買到最多容量的RAM？ 先把 5,000元拿去投資增值 去網路商店買可能比較便宜 多買一點，應該可以殺價 買二手品應該比較便宜 問題 第13章 電腦解題與演算法 / 13-2 電腦解題簡介

電腦解題簡介(3/3) 循序漸進的解題流程：須先規劃出解決問題的明確指令或步驟 死巷 是 判斷是否有沒走過的路 前進並記路 選一條沒走過的路 回前一個叉路口 顯示 過關畫面 否 叉路 出口 老鼠走迷宮問題的解題流程範例 其他 判斷前方情形 第13章 電腦解題與演算法 / 13-2 電腦解題簡介

電腦解題規劃－演算法(1/21) 如何規劃兩天一夜，預算為8,000元的行程呢？ 上網查詢 交通資訊 查詢班次與車資 查詢住宿資訊 查詢景點及門票費用 彙整相關 旅遊資訊 選擇合適方案 民宿 飯店 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(2/21) 演算法：用來解決特定問題的有限指令或步驟，必須具備5項特性 特性 說明 圖中編號 輸入 （input） 要有輸入資料，但並非絕對必要 輸出 （output） 要有一個以上的輸出資料 有限性 （finiteness） 必須在有限的處理步驟內得到結果 明確性 （definiteness） 每個步驟都必須明確，不能有模稜兩可的情況 有效性 （effectiveness） 每個步驟都必須是可執行的 A B C D E 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(3/21) 成績計算演算法的實例 輸入 各科成績 有限性 經過步驟1~4，即可輸出成績單 輸出 各科成績及總分 A C 1. 讀入一筆考生的成績資料 2. 加總各科考試成績 3. 輸出各科考試成績（含加總成績） 4. 重複步驟1~3，直到所有考生的成績資料都處理完畢 輸入 各科成績 有限性 經過步驟1~4，即可輸出成績單 輸出 各科成績及總分 A C B 明確性 每個步驟都很明確 有效性 步驟都可執行 D E 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(4/21) 設計演算法時，常以流程圖表示法與敘述表示法來表示 流程圖：使用圖示符號來表達解決問題的步驟 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(5/21) 常用的流程圖符號與說明 符號 代表意義 作用 開始或結束 表示流程圖的開始或結束 螢幕 表示將資料輸出於螢幕上 輸入或輸出 表示資料的輸入或輸出 處理符號 表示執行某些工作 決策或判斷 表示以符號內的條件式作判斷， 決定執行的流向 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(6/21) 常用的流程圖符號與說明 符號 代表意義 作用 迴圈符號 設定迴圈變數的初值與終值 流向符號 表示程式的執行方向和順序 連接符號 表示流程圖的出口或入口 列印符號 表示資料由印表機輸出 磁碟符號 表示由磁碟輸入或輸出資料 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(7/21) 使用流程圖表示法描述ATM轉帳的流程 12.螢幕顯示 交易明細 1.將金融卡放入ATM 2.輸入密碼 3.密碼是否正確？ 4.顯示錯誤訊息 13.結束 F T 6.輸入對方 銀行代碼 11.列印交易明細表 7.輸入對方帳號 8.輸入轉帳金額 9.取回金融卡 10.是否列印交易明細表？ 5.本行轉帳或 跨行轉帳 F(跨行轉帳) T(本行轉帳) 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(8/21) 敘述表示法：使用虛擬碼，來表達演算法的處理步驟 虛擬碼：以簡潔扼要的文字，來設計程式邏輯 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(9/21) 使用敘述表示法來描述ATM轉帳的流程 1. 放入金融卡 7. 輸入對方帳號 2. 輸入密碼 8. 輸入轉帳金額 3. 判斷密碼是否正確，若正確，跳至步驟5；若錯誤，跳至步驟4 9. 取回金融卡 4. 在螢幕顯示錯誤訊息，並跳至步驟2 10. 判斷是否需要列印交易明細表，若需要，跳至步驟11；若不需要，跳至步驟12 5. 判斷是本行轉帳或跨行轉帳，若為 "跨行轉帳"，跳至步驟6；若為 "本行轉帳"，跳至步驟7 11. 列印交易明細表，並跳至步驟13 12. 在螢幕顯示交易明細 6. 輸入對方銀行代碼 13. 結束流程 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(10/21) 演算法包含循序、條件及重複等3種基本結構 循序結構：由上而下依序執行 1. 輸出一拍的 "So" 音 2. 輸出一拍的 "Mi" 音 3. 輸出二拍的 "Mi" 音 4. 輸出一拍的 "Fa" 音 5. 輸出一拍的 "Re" 音 6. 輸出二拍的 "Re" 音 … 步驟1 步驟2 步驟N 循序結構範例－輸出小蜜蜂音樂 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(11/21) 條件結構：依特定條件或測試結果，來決定執行的路徑 下一個步驟 條件式成立？ T F 步驟 （1至多個） 1. 判斷數值除以2所得之餘數是否等於0 2. 若為0，就顯示 "此數字為偶數"；若不為0，則顯示 "此數字為奇數" 3. 上一個步驟… 條件結構範例－判斷奇偶數 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(12/21) 重複結構：反覆執行解決問題的步驟，直到特定條件出現才停止執行 F 條件式成立？ 步驟 （1至多個） 下一個步驟 T F 條件式成立？ 1. 設定數值i = 1，sum = 0 2. 判斷i值是否 ≦ 10，若為是，跳至步驟3；若為否，跳至步驟5 3. 將i值加到sum中 4. 將i值加1，並跳至步驟2 5. 顯示sum值 重複結構範例－累加1~10 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

變數的概念 變數是指一種內容不固定的資料項目，會隨著程式的執行而改變 變數通常是由名稱、儲存空間、儲存位址、資料型別及內容等5項內涵所組成 1. 名稱：sum 2. 儲存空間：2個bytes 3. 儲存位址：從記憶體的(5A34)16位址開始存放資料 4. 資料型別：整數 5. 內容：60 60 5A34 5A35 5A36 5A37 儲存空間佔2bytes （假設整數型別使用2bytes儲存） 一格代表 1 byte 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(13/21) 規劃演算法前，應先選擇一個合適的解題策略 暴力法：透過逐一比對或計算，以找出最佳解 暴力法的策略簡單易懂，但當資料量龐大時，會沒效率，因此該策略為最後選擇 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(14/21) 請問應在哪幾條路段上興建馬路，才能使成本最低呢？ A B C D E 馬路興建成本示意圖 景點位置示意圖 路段編號 成本 A B C D E 馬路興建成本示意圖 景點位置示意圖 一 1 四 6 三 2 五 3 二 7 六 5 七 4 八 9 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(15/21) 用暴力法找出最低成本的路段組合 路線組合 路段編號 成本 連接所有景點 一 二 三 四 五 六 七 八 A B C D E 連接所有景點， 且成本最低 路線組合 路段編號 成本 連接所有景點 一 二 三 四 五 六 七 八 1  － ╳ 2 7 … n-1 12 ○ n 11 256 37 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(16/21) 貪進法：以最小的成本或最大的效益為原則，找出可行的解答 貪進法的概念簡單、解題效率高，常被用來解決最佳化的問題，如求最低成本、最短路徑等 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(17/21) 用貪進法找出最低成本的路段組合 選取路段 成本 徒增成本 路段組合 A B C D E 一 1 否→選取 {一} 三 2 {一、三} 五 3 {一、三、五} 七 4 是→不選 六 5 {一、三、五、六} 四 6 二 7 八 9 一 四 三 五 二 七 六 八 已不 連必 接往 所下 有判 景斷 點 ， A B C D E 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(18/21) 各個擊破法：將一個問題分解成數個子問題，並找出共通的解決方法，再透過重複操作的方式來解決各個子問題，即可將問題解決 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(19/21) 用各個擊破法，將一串數值由小到大排序的範例 排序規則（演算法） 1. 以第一個數值為中心（標準值），分左右兩邊 2. 將右邊大於標準值的數值依次移至最左邊（標準值左右兩邊即為2個子問題） 3. 對左邊的數值重複步驟1、2，直到排序完成 4. 對右邊的數值重複步驟1、2，直到排序完成 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(20/21) 分 解 擊 破 　　　　20　02　52　48　13　 　　　02　20　02　52　48　13 　13　02　20　02 52　48　13 　　　　13　02　20　52　48 　　　02　13　02　20　52　48 　 02 13　20　52　48 　　　02　13　20　48　52　48 移到最左邊 1 2 左 48　52　48 52　48 右 02　13　02 標準值 13　02 4 3 02 13 20 48 52 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

電腦解題規劃－演算法(21/21) 演算法與程式設計的關係 構思演算法 流程圖 虛擬碼 撰寫程式碼 第13章 電腦解題與演算法 / 13-3 電腦解題規劃-演算法

認識資料結構(1/4) 資料結構：用來組織及管理資料的結構設計 陣列（array）：由一群資料型別相同且依序排列的陣列元素所組成，可分為一維陣列、二維陣列等 83 77 42 66 9 76 93 54 6 10 22 45 37 11 25 B (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) 元素B(1, 1)存放的資料：22 元素B(3, 5)存放的資料：9 … 元素 註標 10 70 90 66 75 1 2 3 4 5 A 元素A(1)存放的資料：10 … 元素 註標 元素A(5)存放的資料：75 一維陣列範例 二維陣列範例 第13章 電腦解題與演算法 / 13-4 認識資料結構

認識資料結構(2/4) 堆疊（stack）：具有後進先出 （LIFO）的特性 存取規則：從頂端（top）加入及取出資料 彈出（pop） 推入（push） 彈出（pop） 頂端（top） 第13章 電腦解題與演算法 / 13-4 認識資料結構

認識資料結構(3/4) 堆疊的應用如瀏覽器的上一頁功能 MSN首頁 科技新聞 娛樂新聞 拜訪網路 （推入） 按上一頁鈕 （彈出） 記錄網址的堆疊 按1次上一頁鈕，回到娛樂新聞； 按2次上一頁鈕，回到MSN首頁 2. 娛樂新聞 1. MSN首頁 第13章 電腦解題與演算法 / 13-4 認識資料結構

認識資料結構(4/4) 佇列（queue）：具有先進先出（FIFO）的特性 存取規則：從尾端（rear）加入資料；從前端（front）取出資料 尾端（rear） 前端（front） 完成程序的人 （已取出的資料） 佇列的儲存空間 第13章 電腦解題與演算法 / 13-4 認識資料結構