問題解決與流程圖 高慧君　台北市立南港高中 2006年12月22日

什麼是演算法 解決問題的方法就是演算法 簡單的問題，我們可以憑直覺就解決 例如：兩個數字相加 對於熟悉算術的人來說，根本不是問題。 十進位相加：126 + 56 = 182 但對沒有學過數字及加法運算的人，就是一個問題。 二進位相加：10012 + 11102 =

什麼是流程圖 演算法的表達 標準流程圖 為了清晰地表達演算法，可以將解決問題的過程整理成流程圖。 美國國家標準學會(ANSI)於1970年制定標準的流程圖符號，以利於流通與閱讀流程圖。

常用的流程圖符號 符號 意義 說明 開始/結束 流程圖的開始或結束位置。 處理 進行一項處理工作。 流程線 表示流程進行的方向。 輸入/輸出 進行資料的輸入或輸出工作。 決策 依條件比較結果進行不同的處理。 迴圈 表示迴圈變數初值與終值的描述 連接 連接點 副程式 表示一群程序步驟的組合。

基本邏輯結構 在解決問題的過程中，可以使用三種基本邏輯結構 (1) 循序結構： (2) 選擇結構： (3) 重複結構： 在解題過程中，有些步驟是具有順序性的。 (2) 選擇結構： 能演繹出不同的方式，依決策擇一進行解題。 (3) 重複結構： 能歸納出重複的部份，依次數或決策重複執行某些步驟。

循序結構 例題： 虛擬碼 敘述1 敘述 1 敘述 2 敘述 3 敘述2 敘述3

選擇結構 單向選擇結構 虛擬碼 條件不成立 條件判斷 If (條件判斷) then 敘述 End if 條件成立 敘述

選擇結構 雙向選擇結構 If (條件判斷) then 敘述 1 Else 敘述 2 End if 虛擬碼 條件判斷 敘述1 敘述2 條件不成立 條件判斷 If (條件判斷) then 敘述 1 Else 敘述 2 End if 條件成立 敘述1 敘述2

重覆結構 條件式：先行後測 虛擬碼 Do 敘述 Loop While (條件判斷) 敘述 條件判斷 條件成立 條件不成立

重覆結構 條件式：先測後行 虛擬碼 條件不成立 條件判斷 Do While (條件判斷) 敘述 Loop 條件成立 敘述

重覆結構 計次式 虛擬碼 次數判斷 For 迴圈變數 = 初值 to 終值 敘述 Next 敘述

重覆結構 遞迴式 Function (參數) If (終止條件判斷) 基本狀況 Else 遞迴步驟 End If End Function 開始 虛擬碼 Function (參數) If (終止條件判斷) 基本狀況 Else 遞迴步驟 End If End Function 條件成立 終止條件 條件不成立 基本狀況 遞迴步驟 結束

解題練習 (1) 循序結構 【類型】求平均值 【問題】求國、英、數三科成績的平均值 〔分析〕輸入：三科成績A, B, C 輸出：平均值

解題練習 (1) 解答 開始 結束 輸入A、B、C值 平均值＝(A+B+C) / 3 輸出平均值

解題練習 (2) 循序結構 【類型】單位換算 【問題】將攝氏溫度轉為華氏溫度 〔分析〕輸入：攝氏溫度 處理：華氏溫度= (攝氏溫度+32 ) * (9/5 ) 輸出：華氏溫度

解題練習 (2) 解答 開始 結束 輸入攝氏溫度 華氏溫度＝(攝氏溫度 + 32 ) * ( 9 / 5 ) 輸出華氏溫度

解題練習 (3) 選擇結構 【類型】判斷成績是否及格 【問題】輸入成績換算為成績，並判斷是否及格。 作業(40%)、測驗(40%)、平時表現(20%) 〔分析〕輸入：作業成績、測驗成績、平時表現成績 處理：學期=作業*0.4 +測驗*0.4 +平時表現* 0.2 判斷：學期≧60 則及格，學期＜60 則不及格 輸出：學期成績是否及格

解題練習 (3) 解答 開始 計算學期成績 輸出成績 結束 輸入成績 學期成績< 60 條件成立 條件不成立 輸出不及格 輸出及格

解題練習 (4) 重覆結構 【類型】累加數字 【問題】計算1+2+3+…+10的值 〔分析〕輸入：無 處理：累加下一項 輸出：總和

解題練習 (4) 解答 開始 結束 輸出Sum Sum = 0 For i = 1 to 10 Sum = Sum + i

解題練習 (4) 解答(遞迴) N + S(9) Return 0 條件不成立 條件成立 開始 N = 0 結束 N = 10

解題練習 (5) 重覆結構 【類型】累加數字 【問題】計算1+2+…+N的值 〔分析〕輸入：無 處理：累加下一項 輸出：總和

解題練習 (5) 開始 結束 輸出Sum Sum = 0 For i = 1 to N Sum = Sum + i 輸入N 解答

解題練習 (5) 解答(遞迴) N + S(N-1) Return 0 條件不成立 條件成立 開始 N = 0 結束 N

解題練習 (6) 重覆結構 【類型】階乘數字 N! 【問題】計算 1*2*…*N 的值 〔分析〕輸入：N 處理：累乘下一項 輸出：總乘積

解題練習 (6) 開始 結束 輸出Mul Mul = 1 For i = 1 to N Mul = Mul * i 輸入N 解答

解題練習 (6) 解答(遞迴) N * M(N-1) Return 1 條件不成立 條件成立 開始 N = 0 結束 N S(N-1)

解題練習 (7) 重覆結構 【類型】銀行利率 【問題】本金1000元，年利率7%，複利，求10年後的資產。 〔分析〕輸入：無 處理：1年後 a 1 = 1000 * 1.07 　　　2年後 a 2 = 1000 * (1.07)2 　　　10年後 a 10 = 1000 * (1.07)10 輸出：a10

解題練習 (7) 解答 開始 結束 輸出 M M = 1000 For i = 1 to 10 M = M *1.07

解題練習 (7) 解答(遞迴) A(9) * 1.07 Return 1000 條件不成立 條件成立 開始 N = 0 結束 N=10

解題練習 (8) 重覆結構 【類型】銀行利率 【問題】本金 1000元，年利率7%，複利，求幾年後資產將增加一倍。 〔分析〕輸入：無 處理： 1年後 a 1 = 1000 * 1.07 　　　 2年後 a 2 = 1000 * (1.07)2 　　　 N年後 a N = 1000 * (1.07)N 輸出：a N

解題練習 (8) 解答 開始 M = 1000 N = 0 N = N + 1 條件不成立 M = M * 1.07 M > 2000 結束 輸出N M = 1000 N = N + 1 N = 0 M > 2000 M = M * 1.07 條件不成立 條件成立

解題練習 (9) 重覆結構 【類型】股票投資 【問題】本金10000元，A股票每天都漲停7%，若固定每個營業日將資金的 50%繼續投資A股票，問經過10個營業日後的資金有多少錢？ 〔分析〕輸入：無 處理：a0 = 10000 　 1天後資金 a 1 = a0 * 0.5 * 1.07 + a0 * 0.5 　 2天後資金 a 2 = a1 * 0.5 * 1.07 + a1 * 0.5 　 N天後資金 a n = a n-1 * 0.5 * 1.07 + a n-1 * 0.5 輸出：a 10

解題練習 (9) 開始 結束 輸出M M = 10000 For i = 1 to 10 M = M*0.5*1.07 + M*0.5 解答

解題練習 (9) 解答(遞迴) N = 9 開始 N = 0 A(8) 條件成立 條件不成立 Return 1000 A(8) * 0.5* 1.07 + A(8) * 0.5 N = 10 N = 0 條件成立 條件不成立 A(9) Return 1000 A(9) * 0.5* 1.07 + A(9) * 0.5 N = 9 A(9) N = 0 結束 條件成立 條件不成立 Return 1000 A(8) * 0.5* 1.07 + A(8) * 0.5

解題練習 (10) 重覆結構 【問題】本金10000元，A股票每個營業日都漲停7%，Ｂ股票每個營業日都 跌停7%，若固定每個營業日將資金的70%繼續投資A股票，30% 繼續投資Ｂ股票，問10個營業日後的資金有多少錢？ 〔分析〕輸入：無 處理：a0 = 10000 　 1天後資金 a 1 = a0 * 0.5 * 1.07 + a0 * 0.5 　 2天後資金 a 2 = a1 * 0.5 * 1.07 + a1 * 0.5 　 N天後資金 a n = a n-1 * 0.5 * 1.07 + a n-1 * 0.5 輸出：a 10

解題練習 (10) 解答 開始 M = 10000 For i = 1 to 10 M = M*0.7*1.07 + M*0.3*0.93 結束 輸出M M = 10000 For i = 1 to 10 M = M*0.7*1.07 + M*0.3*0.93 解答

解題練習 (10) 解答(遞迴) N = 9 開始 N = 0 條件成立 條件不成立 A(8) Return 10000 A(9) * 0.7* 1.07 + A(9) * 0.3* 0.93 N = 10 N = 0 條件成立 條件不成立 A(9) Return 10000 A(9) * 0.7* 1.07 + A(9) * 0.3* 0.93 N = 9 A(9) N = 0 結束 條件成立 條件不成立 A(8) Return 10000 A(9) * 0.7* 1.07 + A(9) * 0.3* 0.93

解題練習 (11) 重覆結構 【類型】費式數列 【問題】計算費式數列的第10項值。 〔分析〕輸入：無 處理： a0 = 1 a 1 = 1 a n = a n-1 + a n-2 輸出：a 10

解題練習 (11) 解答(遞迴) N = 9 開始 N = 0 or N = 1 條件成立 A(8) 條件不成立 Return 1 A(8) + A(7) N = 10 A(7) N = 0 or N = 1 條件成立 條件不成立 A(9) Return 1 A(9) + A(8) N = 8 A(8) N = 0 or N = 1 結束 條件成立 A(7) 條件不成立 Return 1 A(7) + A(6) A(6)

解題練習 (11) 解答(迴圈) For i = 1 to 10 開始 M0 = 1 M1 = 1 M2 = 0 M2 = M1 + M0 結束 輸出M2 M0 = 1 For i = 1 to 10 M1 = 1 M2 = 0 M2 = M1 + M0 M0 = M1 M1 = M2

解題練習 (12) 重覆結構 【類型】最大公因數 【問題】計算兩個正整數的最大公因數 〔分析〕輸入：兩個正整數：A=120、B=32 處理：求最大公因數 輸出：最大公因數

解題練習 (12) 解答(遞迴) 開始 A=120 A = 32 A = 24 B=32 B = 24 B = 8 (120 mod 32) = 0 (32 mod 24) = 0 (24 mod 8) = 0 條件成立 條件不成立 條件成立 條件不成立 條件成立 條件不成立 Return B GCD (32, 24) Return B GCD (24, 8) Return 8 GCD (8, 0) 結束

解題練習 (12) 解答 Begin 餘數 = 被除數 mod 除數 Do while (餘數 <> 0) 被除數 = 除數 除數 = 餘數 Loop Print 除數 End Function GCD(A, B) If (A mod B) = 0 Then Return B Else Return GCD(B, (A mod B)) End If End Function 遞迴 迴圈