1、1問題解決與流程圖高慧君台北市立南港高中2006年12月22日2什麼是演算法 解決問題的方法就是演算法 簡單的問題，我們可以憑直覺就解決 例如：兩個數字相加 對於熟悉算術的人來說，根本不是問題。十進位相加：126+56=182 但對沒有學過數字及加法運算的人，就是一個問題。二進位相加：10012+11102=3什麼是流程圖 演算法的表達 為了清晰地表達演算法，可以將解決問題的過程整理成流程圖。標準流程圖 美國國家標準學會(ANSI)於1970年制定標準的流程圖符號，以利於流通與閱讀流程圖。4常用的流程圖符號符號符號意義意義說明說明開始/結束流程圖的開始或結束位置。處理進行一項處理工作。流程線表
2、示流程進行的方向。輸入/輸出進行資料的輸入或輸出工作。決策依條件比較結果進行不同的處理。迴圈表示迴圈變數初值與終值的描述連接連接點副程式表示一群程序步驟的組合。5基本邏輯結構在解決問題的過程中，可以使用三種基本邏輯結構(1)循序結構：在解題過程中，有些步驟是具有順序性的。(2)選擇結構：能演繹出不同的方式，依決策擇一進行解題。(3)重複結構：能歸納出重複的部份，依次數或決策重複執行某些步驟。6循序結構 例題：敘述1敘述2敘述3敘述 1敘述 2敘述 3虛擬碼7選擇結構 單向選擇結構條件判斷敘述條件成立條件不成立If (條件判斷)then 敘述End if虛擬碼8選擇結構 雙向選擇結構If (條件
3、判斷)then 敘述 1Else 敘述 2End if虛擬碼條件判斷敘述1條件成立條件不成立敘述29重覆結構 條件式：先行後測Do 敘述Loop While(條件判斷)虛擬碼條件判斷條件不成立條件成立敘述10重覆結構 條件式：先測後行Do While(條件判斷)敘述Loop虛擬碼條件判斷條件不成立條件成立敘述11重覆結構 計次式For 迴圈變數=初值 to 終值 敘述Next虛擬碼次數判斷敘述12重覆結構 遞迴式Function(參數)If (終止條件判斷)基本狀況 Else遞迴步驟 End IfEnd Function虛擬碼遞迴步驟基本狀況終止條件條件不成立 條件成立 結束開始13解題練習(
4、1)循序結構【類型】求平均值【問題】求國、英、數三科成績的平均值分析輸入：三科成績A,B,C處理：平均值=(A+B+C)/3輸出：平均值14解題練習(1)解答開始結束輸入A、B、C值平均值(A+B+C)/3輸出平均值15解題練習(2)循序結構【類型】單位換算【問題】將攝氏溫度轉為華氏溫度分析輸入：攝氏溫度處理：華氏溫度=(攝氏溫度+32)*(9/5)輸出：華氏溫度16解題練習(2)解答開始結束輸入攝氏溫度華氏溫度(攝氏溫度+32)*(9/5)輸出華氏溫度17解題練習(3)選擇結構【類型】判斷成績是否及格【問題】輸入成績換算為成績，並判斷是否及格。作業(40%)、測驗(40%)、平時表現(20%
5、)分析輸入：作業成績、測驗成績、平時表現成績處理：學期=作業*0.4+測驗*0.4+平時表現*0.2判斷：學期60 則及格，學期60 則不及格輸出：學期成績是否及格18解題練習(3)解答開始計算學期成績輸出成績結束輸入成績學期成績 2000M=M*1.07條件不成立 條件成立 33解題練習(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
6、 N天後資金 a n=a n-1*0.5*1.07+a n-1*0.5輸出：a 1034解題練習(9)解答開始結束輸出MM=10000 For i=1 to 10M=M*0.5*1.07+M*0.535解題練習(9)解答(遞迴)A(9)*0.5*1.07+A(9)*0.5Return 1000條件不成立 條件成立 開始N=0結束N=10Return 1000條件不成立 條件成立 N=0N=9A(8)*0.5*1.07+A(8)*0.5Return 1000條件不成立 條件成立 N=0N=9A(8)*0.5*1.07+A(8)*0.5A(9)A(9)A(8)36 重覆結構解題練習(10)【問題】
7、本金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 1037解題練習(10)解答開始結束輸出MM=10000 For i=1 to 10M=M*0.7*1.07+M*0.3*0.9338解題練習(10)解答(遞迴)A(9)*0.7*1.07+A(9)*
8、0.3*0.93Return 10000條件不成立 條件成立 開始N=0結束N=10Return 10000條件不成立 條件成立 N=0N=9Return 10000條件不成立 條件成立 N=0N=9A(9)A(9)A(8)A(9)*0.7*1.07+A(9)*0.3*0.93A(9)*0.7*1.07+A(9)*0.3*0.93A(8)39 重覆結構解題練習(11)【類型】費式數列【問題】計算費式數列的第10項值。分析輸入：無處理：a0=1 a 1=1 a n=a n-1 +a n-2 輸出：a 1040解題練習(11)解答(遞迴)A(9)+A(8)Return 1條件不成立 條件成立 開始
9、N=0 or N=1結束N=10Return 1條件不成立 條件成立 N=9Return 1條件不成立 條件成立 N=8A(9)A(8)A(8)A(8)+A(7)A(7)+A(6)N=0 or N=1N=0 or N=1A(7)A(7)A(6)41解題練習(11)解答(迴圈)開始結束輸出M2M0=1 For i=1 to 10M1=1M2=0M2=M1+M0M0=M1M1=M242 重覆結構解題練習(12)【類型】最大公因數【問題】計算兩個正整數的最大公因數分析輸入：兩個正整數：A=120、B=32處理：求最大公因數輸出：最大公因數43解題練習(12)解答(遞迴)GCD(32,24)Retur
10、n B條件不成立 條件成立 開始(120 mod 32)=0結束A=120Return B條件不成立 條件成立 A=32(32 mod 24)=0GCD(24,8)B=32B=24Return 8條件不成立 條件成立 A=24(24 mod 8)=0GCD(8,0)B=844解題練習(12)解答Function GCD(A,B)If (A mod B)=0 ThenReturn B ElseReturn GCD(B,(A mod B)End IfEnd FunctionBegin 餘數=被除數 mod 除數 Do while(餘數 0)被除數=除數 除數=餘數 餘數=被除數 mod 除數 Loop Print 除數End迴圈遞迴
