問題解決與流程圖

問題解決與流程圖高慧君臺北市立南港高中2006年12月22日1第一頁，共四十五頁。什麼是演算法解決問題的方法就是演算法簡單的問題，我們可以憑直覺就解決例如：兩個數(shù)字相加對於熟悉算術(shù)的人來說，根本不是問題。十進(jìn)位相加：126+56=182但對沒有學(xué)過數(shù)字及加法運(yùn)算的人，就是一個問題。二進(jìn)位相加：10012+11102=2第二頁，共四十五頁。什麼是流程圖演算法的表達(dá)為了清晰地表達(dá)演算法，可以將解決問題的過程整理成流程圖。標(biāo)準(zhǔn)流程圖美國國家標(biāo)準(zhǔn)學(xué)會(ANSI)於1970年制定標(biāo)準(zhǔn)的流程圖符號，以利於流通與閱讀流程圖。3第三頁，共四十五頁。常用的流程圖符號符號意義說明開始/結(jié)束流程圖的開始或結(jié)束位置。處理進(jìn)行一項(xiàng)處理工作。流程線表示流程進(jìn)行的方向。輸入/輸出進(jìn)行資料的輸入或輸出工作。決策依條件比較結(jié)果進(jìn)行不同的處理。迴圈表示迴圈變數(shù)初值與終值的描述連接連接點(diǎn)副程式表示一群程序步驟的組合。4第四頁，共四十五頁?；具壿嫿Y(jié)構(gòu)在解決問題的過程中，可以使用三種基本邏輯結(jié)構(gòu)(1)循序結(jié)構(gòu)：在解題過程中，有些步驟是具有順序性的。(2)選擇結(jié)構(gòu)：能演繹出不同的方式，依決策擇一進(jìn)行解題。(3)重複結(jié)構(gòu)：能歸納出重複的部份，依次數(shù)或決策重複執(zhí)行某些步驟。5第五頁，共四十五頁。循序結(jié)構(gòu)例題：敘述1敘述2敘述3敘述1敘述2敘述3虛擬碼6第六頁，共四十五頁。選擇結(jié)構(gòu)單向選擇結(jié)構(gòu)條件判斷敘述條件成立條件不成立If(條件判斷)then敘述Endif虛擬碼7第七頁，共四十五頁。選擇結(jié)構(gòu)雙向選擇結(jié)構(gòu)If(條件判斷)then敘述1Else敘述2Endif虛擬碼條件判斷敘述1條件成立條件不成立敘述28第八頁，共四十五頁。重覆結(jié)構(gòu)條件式：先行後測Do敘述LoopWhile(條件判斷)虛擬碼條件判斷條件不成立條件成立敘述9第九頁，共四十五頁。重覆結(jié)構(gòu)條件式：先測後行DoWhile(條件判斷)敘述Loop虛擬碼條件判斷條件不成立條件成立敘述10第十頁，共四十五頁。重覆結(jié)構(gòu)計(jì)次式For迴圈變數(shù)=初值to終值敘述Next虛擬碼次數(shù)判斷敘述11第十一頁，共四十五頁。重覆結(jié)構(gòu)遞迴式Function(參數(shù))If(終止條件判斷) 基本狀況Else 遞迴步驟EndIfEndFunction虛擬碼遞迴步驟基本狀況終止條件條件不成立條件成立

結(jié)束開始12第十二頁，共四十五頁。解題練習(xí)(1)循序結(jié)構(gòu)【類型】求平均值【問題】求國、英、數(shù)三科成績的平均值〔分析〕輸入：三科成績A,B,C 處理：平均值=(A+B+C)/3 輸出：平均值13第十三頁，共四十五頁。解題練習(xí)(1)解答開始結(jié)束輸入A、B、C值平均值＝(A+B+C)/3輸出平均值14第十四頁，共四十五頁。解題練習(xí)(2)循序結(jié)構(gòu)【類型】單位換算【問題】將攝氏溫度轉(zhuǎn)為華氏溫度〔分析〕輸入：攝氏溫度 處理：華氏溫度=(攝氏溫度+32)*(9/5) 輸出：華氏溫度15第十五頁，共四十五頁。解題練習(xí)(2)解答開始結(jié)束輸入攝氏溫度華氏溫度＝(攝氏溫度+32)*(9/5)輸出華氏溫度16第十六頁，共四十五頁。解題練習(xí)(3)選擇結(jié)構(gòu)【類型】判斷成績是否及格【問題】輸入成績換算為成績，並判斷是否及格。 作業(yè)(40%)、測驗(yàn)(40%)、平時表現(xiàn)(20%)〔分析〕輸入：作業(yè)成績、測驗(yàn)成績、平時表現(xiàn)成績 處理：學(xué)期=作業(yè)*0.4+測驗(yàn)*0.4+平時表現(xiàn)*0.2 判斷：學(xué)期≧60則及格，學(xué)期＜60則不及格 輸出：學(xué)期成績是否及格17第十七頁，共四十五頁。解題練習(xí)(3)解答開始計(jì)算學(xué)期成績輸出成績結(jié)束輸入成績學(xué)期成績<60條件成立條件不成立輸出不及格輸出及格18第十八頁，共四十五頁。解題練習(xí)(4)重覆結(jié)構(gòu)【類型】累加數(shù)字【問題】計(jì)算1+2+3+…+10的值〔分析〕輸入：無 處理：累加下一項(xiàng) 輸出：總和19第十九頁，共四十五頁。解題練習(xí)(4)解答開始結(jié)束輸出SumSum=0Fori=1to10Sum=Sum+i20第二十頁，共四十五頁。解題練習(xí)(4)解答(遞迴)N+S(9)Return0條件不成立條件成立開始N=0結(jié)束N=10N+S(8)Return0條件不成立條件成立N=0N=9S(9)21第二十一頁，共四十五頁。解題練習(xí)(5)重覆結(jié)構(gòu)【類型】累加數(shù)字【問題】計(jì)算1+2+…+N的值〔分析〕輸入：無 處理：累加下一項(xiàng) 輸出：總和22第二十二頁，共四十五頁。解題練習(xí)(5)解答開始結(jié)束輸出SumSum=0Fori=1toNSum=Sum+i輸入N23第二十三頁，共四十五頁。解題練習(xí)(5)解答(遞迴)N+S(N-1)Return0條件不成立條件成立開始N=0結(jié)束N(N-1)+S(N-2)Return0條件不成立條件成立(N-1)=0N-1S(N-1)24第二十四頁，共四十五頁。解題練習(xí)(6)重覆結(jié)構(gòu)【類型】階乘數(shù)字N!【問題】計(jì)算1*2*…*N的值〔分析〕輸入：N 處理：累乘下一項(xiàng) 輸出：總乘積25第二十五頁，共四十五頁。解題練習(xí)(6)解答開始結(jié)束輸出MulMul=1Fori=1toNMul=Mul*i輸入N26第二十六頁，共四十五頁。解題練習(xí)(6)解答(遞迴)N*M(N-1)Return1條件不成立條件成立開始N=0結(jié)束N(N-1)*M(N-2)Return1條件不成立條件成立(N-1)=0N-1S(N-1)27第二十七頁，共四十五頁。解題練習(xí)(7)重覆結(jié)構(gòu)【類型】銀行利率【問題】本金1000元，年利率7%，複利，求10年後的資產(chǎn)?！卜治觥齿斎耄簾o 處理：1年後a1=1000*1.07 2年後a2=1000*(1.07)2 10年後a10=1000*(1.07)10 輸出：a1028第二十八頁，共四十五頁。解題練習(xí)(7)解答開始結(jié)束輸出MM=1000Fori=1to10M=M*1.0729第二十九頁，共四十五頁。解題練習(xí)(7)解答(遞迴)A(9)*1.07Return1000條件不成立條件成立開始N=0結(jié)束N=10A(8)*1.07Return1000條件不成立條件成立N=0N=9A(9)A(8)30第三十頁，共四十五頁。解題練習(xí)(8)重覆結(jié)構(gòu)【類型】銀行利率【問題】本金1000元，年利率7%，複利，求幾年後資產(chǎn)將增加一倍?！卜治觥齿斎耄簾o 處理：1年後a1=1000*1.07 2年後a2=1000*(1.07)2 N年後aN=1000*(1.07)N 輸出：aN31第三十一頁，共四十五頁。解題練習(xí)(8)解答開始結(jié)束輸出NM=1000N=N+1N=0M>2000M=M*1.07條件不成立條件成立32第三十二頁，共四十五頁。解題練習(xí)(9)重覆結(jié)構(gòu)【類型】股票投資【問題】本金10000元，A股票每天都漲停7%，若固定每個營業(yè)日將資金的50%繼續(xù)投資A股票，問經(jīng)過10個營業(yè)日後的資金有多少錢？〔分析〕輸入：無 處理：a0=10000 1天後資金a1=a0*0.5*1.07+a0*0.5 2天後資金a2=a1*0.5*1.07+a1*0.5 N天後資金an=an-1*0.5*1.07+an-1*0.5 輸出：a1033第三十三頁，共四十五頁。解題練習(xí)(9)解答開始結(jié)束輸出MM=10000Fori=1to10M=M*0.5*1.07+M*0.534第三十四頁，共四十五頁。解題練習(xí)(9)解答(遞迴)A(9)*0.5*1.07+A(9)*0.5Return1000條件不成立條件成立開始N=0結(jié)束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)35第三十五頁，共四十五頁。重覆結(jié)構(gòu)解題練習(xí)(10)【問題】本金10000元，A股票每個營業(yè)日都漲停7%，Ｂ股票每個營業(yè)日都跌停7%，若固定每個營業(yè)日將資金的70%繼續(xù)投資A股票，30%繼續(xù)投資Ｂ股票，問10個營業(yè)日後的資金有多少錢？〔分析〕輸入：無 處理：a0=10000 1天後資金a1=a0*0.5*1.07+a0*0.5 2天後資金a2=a1*0.5*1.07+a1*0.5 N天後資金an=an-1*0.5*1.07+an-1*0.5 輸出：a1036第三十六頁，共四十五頁。解題練習(xí)(10)解答開始結(jié)束輸出MM=10000Fori=1to10M=M*0.7*1.07+M*0.3*0.9337第三十七頁，共四十五頁。解題練習(xí)(10)解答(遞迴)A(9)*0.7*1.07+A(9)*0.3*0.93Return10000條件不成立條件成立開始N=0結(jié)束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)38第三十八頁，共四十五頁。重覆結(jié)構(gòu)解題練習(xí)(11)【類型】費(fèi)式數(shù)列【問題】計(jì)算費(fèi)式數(shù)列的第10項(xiàng)值?！卜治觥齿斎耄簾o 處理：a0=1 a1=1 an=an-1+an-2

輸出：a1039第三十九頁，共四十五頁。解題練習(xí)(11)解答(遞迴)A(9)+A(8)Return1條件不成立條件成立開始N=0orN=1結(jié)束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)40第四十頁，共四十五頁。解題練習(xí)(11)解答(迴圈)開始結(jié)束輸出M2M0=1

Fori=1to10M1=1M2=0M2=M1+M0M0=M1M1=M241第四十一頁，共四十五頁。重覆結(jié)構(gòu)解題練習(xí)(12)【類型】最大公因數(shù)【問題】計(jì)算兩個正整數(shù)的最大公因數(shù)〔分析〕輸入：兩個正整數(shù)：A=120、B=32 處理：求最大公因數(shù) 輸出：最大公因數(shù)42第四十二頁，共四十五頁。解題練習(xí)(12)解答(遞迴)GCD(32,24)ReturnB條件不成立條件成立開始(120mod32)=0結(jié)束A=120ReturnB條件不成立條件成立A=32(32mod24)=0GCD(24,8)B=32B=24Return8條件不成立條件成立A=24(24mod8)=0GCD(8,0)B=843第四十三頁，共四十五頁。