问题解决与流程图

1問題解決與流程圖高慧君台北市立南港高中2006年12月22日2什麼是演算法•解決問題的方法就是演算法•簡單的問題，我們可以憑直覺就解決•例如：兩個數字相加–對於熟悉算術的人來說，根本不是問題。十進位相加：126+56=182–但對沒有學過數字及加法運算的人，就是一個問題。二進位相加：10012+11102=3什麼是流程圖•演算法的表達–為了清晰地表達演算法，可以將解決問題的過程整理成流程圖。•標準流程圖–美國國家標準學會(ANSI)於1970年制定標準的流程圖符號，以利於流通與閱讀流程圖。4常用的流程圖符號符號意義說明開始/結束流程圖的開始或結束位置。處理進行一項處理工作。流程線表示流程進行的方向。輸入/輸出進行資料的輸入或輸出工作。決策依條件比較結果進行不同的處理。迴圈表示迴圈變數初值與終值的描述連接連接點副程式表示一群程序步驟的組合。5基本邏輯結構在解決問題的過程中，可以使用三種基本邏輯結構(1)循序結構：在解題過程中，有些步驟是具有順序性的。(2)選擇結構：能演繹出不同的方式，依決策擇一進行解題。(3)重複結構：能歸納出重複的部份，依次數或決策重複執行某些步驟。6循序結構•例題：敘述1敘述2敘述3敘述1敘述2敘述3虛擬碼7選擇結構•單向選擇結構條件判斷敘述條件成立條件不成立If(條件判斷)then敘述Endif虛擬碼8選擇結構•雙向選擇結構If(條件判斷)then敘述1Else敘述2Endif虛擬碼條件判斷敘述1條件成立條件不成立敘述29重覆結構•條件式：先行後測Do敘述LoopWhile(條件判斷)虛擬碼條件判斷條件不成立條件成立敘述10重覆結構•條件式：先測後行DoWhile(條件判斷)敘述Loop虛擬碼條件判斷條件不成立條件成立敘述11重覆結構•計次式For迴圈變數=初值to終值敘述Next虛擬碼次數判斷敘述12重覆結構•遞迴式Function(參數)If(終止條件判斷)基本狀況Else遞迴步驟EndIfEndFunction虛擬碼遞迴步驟基本狀況終止條件條件不成立條件成立結束開始13解題練習(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%)〔分析〕輸入：作業成績、測驗成績、平時表現成績處理：學期=作業*0.4+測驗*0.4+平時表現*0.2判斷：學期≧60則及格，學期＜60則不及格輸出：學期成績是否及格18解題練習(3)•解答開始計算學期成績輸出成績結束輸入成績學期成績60條件成立條件不成立輸出不及格輸出及格19解題練習(4)•重覆結構【類型】累加數字【問題】計算1+2+3+…+10的值〔分析〕輸入：無處理：累加下一項輸出：總和20解題練習(4)•解答開始結束輸出SumSum=0Fori=1to10Sum=Sum+i21解題練習(4)•解答(遞迴)N+S(9)Return0條件不成立條件成立開始N=0結束N=10N+S(8)Return0條件不成立條件成立N=0N=9S(9)22解題練習(5)•重覆結構【類型】累加數字【問題】計算1+2+…+N的值〔分析〕輸入：無處理：累加下一項輸出：總和23解題練習(5)•解答開始結束輸出SumSum=0Fori=1toNSum=Sum+i輸入N24解題練習(5)•解答(遞迴)N+S(N-1)Return0條件不成立條件成立開始N=0結束N(N-1)+S(N-2)Return0條件不成立條件成立(N-1)=0N-1S(N-1)25解題練習(6)•重覆結構【類型】階乘數字N!【問題】計算1*2*…*N的值〔分析〕輸入：N處理：累乘下一項輸出：總乘積26解題練習(6)•解答開始結束輸出MulMul=1Fori=1toNMul=Mul*i輸入N27解題練習(6)•解答(遞迴)N*M(N-1)Return1條件不成立條件成立開始N=0結束N(N-1)*M(N-2)Return1條件不成立條件成立(N-1)=0N-1S(N-1)28解題練習(7)•重覆結構【類型】銀行利率【問題】本金1000元，年利率7%，複利，求10年後的資產。〔分析〕輸入：無處理：1年後a1=1000*1.072年後a2=1000*(1.07)210年後a10=1000*(1.07)10輸出：a1029解題練習(7)•解答開始結束輸出MM=1000Fori=1to10M=M*1.0730解題練習(7)•解答(遞迴)A(9)*1.07Return1000條件不成立條件成立開始N=0結束N=10A(8)*1.07Return1000條件不成立條件成立N=0N=9A(9)A(8)31解題練習(8)•重覆結構【類型】銀行利率【問題】本金1000元，年利率7%，複利，求幾年後資產將增加一倍。〔分析〕輸入：無處理：1年後a1=1000*1.072年後a2=1000*(1.07)2N年後aN=1000*(1.07)N輸出：aN32解題練習(8)•解答開始結束輸出NM=1000N=N+1N=0M2000M=M*1.07條件不成立條件成立33解題練習(9)•重覆結構【類型】股票投資【問題】本金10000元，A股票每天都漲停7%，若固定每個營業日將資金的50%繼續投資A股票，問經過10個營業日後的資金有多少錢？〔分析〕輸入：無處理：a0=100001天後資金a1=a0*0.5*1.07+a0*0.52天後資金a2=a1*0.5*1.07+a1*0.5N天後資金an=an-1*0.5*1.07+an-1*0.5輸出：a1034解題練習(9)•解答開始結束輸出MM=10000Fori=1to10M=M*0.5*1.07+M*0.535解題練習(9)•解答(遞迴)A(9)*0.5*1.07+A(9)*0.5Return1000條件不成立條件成立開始N=0結束N=10Return1000條件不成立條件成立N=0N=9A(8)*0.5*1.07+A(8)*0.5Return1000條件不成立條件成立N=0N=9A(8)*0.5*1.07+A(8)*0.5A(9)A(9)A(8)36•重覆結構解題練習(10)【問題】本金10000元，A股票每個營業日都漲停7%，Ｂ股票每個營業日都跌停7%，若固定每個營業日將資金的70%繼續投資A股票，30%繼續投資Ｂ股票，問10個營業日後的資金有多少錢？〔分析〕輸入：無處理：a0=100001天後資金a1=a0*0.5*1.07+a0*0.52天後資金a2=a1*0.5*1.07+a1*0.5N天後資金an=an-1*0.5*1.07+an-1*0.5輸出：a1037解題練習(10)•解答開始結束輸出MM=10000Fori=1to10M=M*0.7*1.07+M*0.3*0.9338解題練習(10)•解答(遞迴)A(9)*0.7*1.07+A(9)*0.3*0.93Return10000條件不成立條件成立開始N=0結束N=10Return10000條件不成立條件成立N=0N=9Return10000條件不成立條件成立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=1a1=1an=an-1+an-2輸出：a1040解題練習(11)•解答(遞迴)A(9)+A(8)Return1條件不成立條件成立開始N=0orN=1結束N=10Return1條件不成立條件成立N=9Return1條件不成立條件成立N=8A(9)A(8)A(8)A(8)+A(7)A(7)+A(6)N=0orN=1N=0orN=1A(7)A(7)A(6)41解題練習(11)•解答(迴圈)開始結束輸出M2M0=1Fori=1to10M1=1M2=0M2=M1+M0M0=M1M1=M242•重覆結構解題練習(12)【類型】最大公因數【問題】計算兩個正整數的最大公因數〔分析〕輸入：兩個正整數：A=120、B=32處理：求最大公因數輸出：最大公因數43解題練習(12)•解答(遞迴)GCD(32,24)ReturnB條件不成立條件成立開始(120mod32)=0結束A=120ReturnB條件不成立條件成立A=32(32mod24)=0GCD(24,8)B=32B=24Return8條件不成立條件成立A=24(24mod8)=0GCD(8,0)B=844解題練習(12)•解答FunctionGCD(A,B)If(AmodB)=0ThenReturnBElseReturnGCD(B,(AmodB))EndIfEndFunctionBegin餘數=被除數mod除數Dowhile(餘數0)被除數=除數除數=餘數餘數=被除數mod除數LoopPrint除數End迴圈遞迴