數(shù)學(xué)《算法與程序框圖》課件(新人教A版必修)

1、問題的提出問題的提出 有一個(gè)農(nóng)夫帶一條狼狗、一只羊和有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜過河。如果沒有農(nóng)夫看管，則一筐白菜過河。如果沒有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？何解此難題？ 方法和過程方法和過程：1、帶羊到對(duì)岸，返回；帶羊到對(duì)岸，返回；2、帶菜到對(duì)岸，并把羊帶回；帶菜到對(duì)岸，并把羊帶回；3、帶狼狗到對(duì)岸，返回；帶狼狗到對(duì)岸，返回；4、帶羊到對(duì)岸。帶羊到對(duì)岸。問題問題1請(qǐng)你寫出解二元一次方程組的詳細(xì)求解請(qǐng)你寫出解二元一次方程組的詳細(xì)求解過程過程. 35(1

2、)2494(2)xyxy35(1)2494(2)xyxy解方程解方程第一步第一步, ,由（由（1）得）得35(3)xy第二步第二步, ,將（將（3）代入（）代入（2）得）得2(35)494(4)yy第三步第三步, , 解（解（4）得）得12(5)y 第四步第四步, , 將（將（5）代入（）代入（3）得）得23x 第五步第五步, , 得到方程組的解得得到方程組的解得2312xy35(1)2494(2)xyxy解方程解方程第一步第一步, ,(1)2(2)224(3)y 得： 第二步第二步, ,第三步第三步, ,第四步第四步, ,第五步第五步, , 得到方程組的解得得到方程組的解得2312xy(3)

3、12y 解得：(1)4(2)246(4)x得：(4)23x 解得：廣義地說：為了解決某一問題而采取的方廣義地說：為了解決某一問題而采取的方法和步驟，就稱之為算法。法和步驟，就稱之為算法。在數(shù)學(xué)中，按照一定規(guī)則解決某一類問在數(shù)學(xué)中，按照一定規(guī)則解決某一類問題的明確和有限的步驟，題的明確和有限的步驟，稱為算法?，F(xiàn)在，算法通?？梢跃幊捎?jì)算機(jī)程序，現(xiàn)在，算法通常可以編成計(jì)算機(jī)程序，讓計(jì)算機(jī)執(zhí)行并解決問題。讓計(jì)算機(jī)執(zhí)行并解決問題。算法的概念算法的概念:沒有軟件的支持，計(jì)算機(jī)只是一堆廢鐵而已；沒有軟件的支持，計(jì)算機(jī)只是一堆廢鐵而已；算法的特征算法的特征 一.確定性:每一步必須有確切的定義。 二.有效性：原

4、則上必須能夠精確的運(yùn)行。 三.有窮性：一個(gè)算法必須保證執(zhí)行有限步 后結(jié)束算法的優(yōu)缺點(diǎn)算法的優(yōu)缺點(diǎn) 一.缺點(diǎn):算法一般是機(jī)械的,有時(shí)需要進(jìn)行大量重復(fù)的計(jì)算. 二.優(yōu)點(diǎn):算法是一種通法,只要按照步驟去做,總能得到結(jié)果. 廣播操圖解是廣播操的算法；廣播操圖解是廣播操的算法； 菜譜是做菜的算法；菜譜是做菜的算法； 歌譜是一首歌曲的算法；歌譜是一首歌曲的算法； 空調(diào)說明書是空調(diào)使用的算法等空調(diào)說明書是空調(diào)使用的算法等我們身邊的算法我們身邊的算法例例1.(1).(1)設(shè)計(jì)一個(gè)算法判斷設(shè)計(jì)一個(gè)算法判斷7 7是否為質(zhì)數(shù)是否為質(zhì)數(shù). .第一步第一步, 用用2除除7,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0

5、， 所以所以2不能整除不能整除7.第二步第二步, 用用3除除7,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以3不能整除不能整除7.第三步第三步, 用用4除除7,得到余數(shù)得到余數(shù)3.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除7,得到余數(shù)得到余數(shù)2.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以5不能整除不能整除7.第五步第五步, 用用6除除7,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以6不能整除不能整除7.因此，因此，7是質(zhì)數(shù)是質(zhì)數(shù).例例1.(2).(2)設(shè)計(jì)一個(gè)算法判斷設(shè)計(jì)一個(gè)算法判斷3535是否為質(zhì)是否為質(zhì)數(shù)數(shù). .第一步第一

6、步, 用用2除除35,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以2不能整除不能整除35.第二步第二步, 用用3除除35,得到余數(shù)得到余數(shù)2.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以3不能整除不能整除35.第三步第三步, 用用4除除35,得到余數(shù)得到余數(shù)3.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除35,得到余數(shù)得到余數(shù)0.因?yàn)橛鄶?shù)為因?yàn)橛鄶?shù)為0， 所以所以5能整除能整除35.因此，因此，35不是質(zhì)數(shù)不是質(zhì)數(shù).變式：變式：設(shè)計(jì)一個(gè)算法判斷設(shè)計(jì)一個(gè)算法判斷1997是否為質(zhì)數(shù)是否為質(zhì)數(shù)第一步第一步, 用用2除除1997,得到余數(shù)得到余數(shù)1.因

7、為余數(shù)不為因?yàn)橛鄶?shù)不為0， 所以所以2不能整除不能整除1997.第二步第二步, 用用3除除1997,得到余數(shù)得到余數(shù)2.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0， 所以所以3不能整除不能整除1997.第三步第三步, 用用4除除1997,得到余數(shù)得到余數(shù)1.因?yàn)橛鄶?shù)不為因?yàn)橛鄶?shù)不為0，所以，所以4不能整除不能整除1997.第一千九百九十五步第一千九百九十五步, 用用1996除除1997,得到余數(shù)得到余數(shù)1.因?yàn)橐驗(yàn)橛鄶?shù)不為余數(shù)不為0， 所以所以1996不能整除不能整除1997.所以，所以，1997是質(zhì)數(shù)是質(zhì)數(shù)判斷判斷1997是否為質(zhì)數(shù)的算法是否為質(zhì)數(shù)的算法第一步：令第一步：令i=2;第二步：用第二步：用i除除

8、1997，得到余數(shù)，得到余數(shù)r;第三步：判斷第三步：判斷“r=0”是否成立，若是，則是否成立，若是，則1997不是質(zhì)數(shù)，不是質(zhì)數(shù)，結(jié)束算法：否則將結(jié)束算法：否則將i增加增加1，仍用，仍用i表示；表示；第四步：判斷第四步：判斷“i1996”是否成立，若是，則是否成立，若是，則1997是是質(zhì)數(shù)，結(jié)束算法：否則返回第三步質(zhì)數(shù)，結(jié)束算法：否則返回第三步變式變式2：如果讓計(jì)算機(jī)判斷整數(shù)：如果讓計(jì)算機(jī)判斷整數(shù)n(n2），是否為質(zhì)數(shù)，），是否為質(zhì)數(shù)，如何設(shè)計(jì)算法跟步驟？如何設(shè)計(jì)算法跟步驟？第二步：令第二步：令i=2;第三步：用第三步：用i除除n，得到余數(shù)，得到余數(shù)r;第四步：判斷第四步：判斷“r=0”是否成

9、立，若是，則是否成立，若是，則n不是質(zhì)數(shù)，不是質(zhì)數(shù)，結(jié)束算法：否則將結(jié)束算法：否則將i增加增加1，仍用，仍用i表示；表示；第五步：判斷第五步：判斷“i(n-1)”是否成立，若是，則是否成立，若是，則n是質(zhì)是質(zhì)數(shù)，結(jié)束算法：否則返回第三步數(shù)，結(jié)束算法：否則返回第三步第一步：第一步：給定大于給定大于2的整數(shù)的整數(shù)n;練習(xí)一練習(xí)一:任意給定一個(gè)正實(shí)數(shù)任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積算法求以這個(gè)數(shù)為半徑的圓的面積.算法分析算法分析:第一步第一步:輸入任意一個(gè)正實(shí)數(shù)輸入任意一個(gè)正實(shí)數(shù)r;第二步第二步:計(jì)算以計(jì)算以r為半徑的圓的面積為半徑的圓的面積S=r2;第三步第三步:

10、輸出圓的面積輸出圓的面積.課本課本5頁頁 1練習(xí)二練習(xí)二:任意給定一個(gè)大于任意給定一個(gè)大于1的正整數(shù)的正整數(shù)n,設(shè)計(jì)設(shè)計(jì)一個(gè)算法求出一個(gè)算法求出n的所有因數(shù)的所有因數(shù).課本課本5頁頁 2第二步：令第二步：令i=1;第三步：用第三步：用i除除n，得到余數(shù)，得到余數(shù)r;第四步：若第四步：若“r=0”,則輸出則輸出i第五步：將第五步：將i增加增加1，仍用，仍用i表示；表示；第六步：若第六步：若in，則返回第三步，否則結(jié)束，則返回第三步，否則結(jié)束第一步：第一步：給定大于給定大于1的整數(shù)的整數(shù)n;例例2. .用二分法設(shè)計(jì)一個(gè)求方程用二分法設(shè)計(jì)一個(gè)求方程220 x 的近似根的算法的近似根的算法. .(0)

11、x 對(duì)于區(qū)間對(duì)于區(qū)間a,b 上連續(xù)不斷、且上連續(xù)不斷、且f(a)f(b)0的函數(shù)的函數(shù)y=f(x),通過不斷地通過不斷地把函數(shù)把函數(shù)f(x)的零點(diǎn)所在的區(qū)間一分的零點(diǎn)所在的區(qū)間一分為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)近似值的方法零點(diǎn)，進(jìn)而得到零點(diǎn)近似值的方法叫做叫做二分法二分法.22(0)yxx第四步第四步, 若若f(a) f(m) 2,則執(zhí)行第二步則執(zhí)行第二步. 第二步第二步:依次檢驗(yàn)依次檢驗(yàn)2(n-1)這些整數(shù)是不是這些整數(shù)是不是n的的因數(shù)因數(shù),即是不是整除即是不是整除n的數(shù)的數(shù).若有這樣的數(shù)若有這樣的數(shù),則則n不是不是質(zhì)數(shù)質(zhì)數(shù);若沒有這樣的數(shù)若沒

12、有這樣的數(shù),則則n是質(zhì)數(shù)是質(zhì)數(shù).從上節(jié)課我們知道從上節(jié)課我們知道:算法可以用自然語言算法可以用自然語言來描述來描述.如例如例1 為了使算法的程序或步驟表達(dá)得更為直觀為了使算法的程序或步驟表達(dá)得更為直觀,我我們更經(jīng)常地用圖形方式來表示它們更經(jīng)常地用圖形方式來表示它.開始開始輸入輸入ni=2求求n除以除以i的余數(shù)的余數(shù)ri的值增加的值增加1仍用仍用i表示表示in-1或或r=0?n不是質(zhì)數(shù)不是質(zhì)數(shù)結(jié)束結(jié)束是是否否是是n是質(zhì)數(shù)是質(zhì)數(shù)否否r=0? i=i+1程序框圖程序框圖又稱又稱流程圖流程圖,是一種用規(guī)定的圖形、是一種用規(guī)定的圖形、指向線及文字說明來準(zhǔn)確、直觀地表示算法的指向線及文字說明來準(zhǔn)確、直觀地

13、表示算法的圖形圖形.通常通常,程序框圖由程序框和流程線組成程序框圖由程序框和流程線組成.一個(gè)或幾個(gè)程序框的組合表示算法中的一個(gè)步驟一個(gè)或幾個(gè)程序框的組合表示算法中的一個(gè)步驟;流程線是方向箭頭流程線是方向箭頭,按照算法進(jìn)行的順序?qū)⒊绦虬凑账惴ㄟM(jìn)行的順序?qū)⒊绦蚩蜻B接起來框連接起來.基本的程序框和它們各自表示的功能如下基本的程序框和它們各自表示的功能如下:圖形符號(hào)圖形符號(hào)名稱名稱功能功能終端框終端框(起止框起止框)表示一個(gè)算法的開始表示一個(gè)算法的開始和結(jié)束和結(jié)束輸入、輸輸入、輸出框出框表示一個(gè)算法輸入和表示一個(gè)算法輸入和輸出的信息輸出的信息處理框處理框(執(zhí)行框執(zhí)行框)判斷某一條件是否成立判斷某一條件

14、是否成立,成立成立時(shí)在出口處標(biāo)明時(shí)在出口處標(biāo)明“是是”或或“Y”；不；不”成立時(shí)標(biāo)明成立時(shí)標(biāo)明“否否”或或“N”.判斷框判斷框賦值、計(jì)算賦值、計(jì)算流程線流程線連接程序框連接程序框連接點(diǎn)連接點(diǎn)連接程序框圖的兩部分連接程序框圖的兩部分開始開始輸入輸入ni=2求求n除以除以i的余數(shù)的余數(shù)ri的值增加的值增加1仍用仍用i表示表示in-1或或r=0?n不是質(zhì)數(shù)不是質(zhì)數(shù)結(jié)束結(jié)束是是否否是是n是質(zhì)數(shù)是質(zhì)數(shù)否否r=0?設(shè)設(shè)n是一個(gè)大是一個(gè)大于于2的整數(shù)的整數(shù).一般用一般用i=i+1表示表示. i=i+1說明說明:i表示從表示從2(n-1)的所有正整數(shù)的所有正整數(shù),用以用以判斷例判斷例1步驟步驟2是否終是否終止

15、止,i是一個(gè)計(jì)數(shù)變量是一個(gè)計(jì)數(shù)變量,有了這個(gè)變量有了這個(gè)變量,算法算法才能依次執(zhí)行才能依次執(zhí)行.逐步逐步考察從考察從2(n-1)的所的所有正整數(shù)中是否有有正整數(shù)中是否有n的因數(shù)存在的因數(shù)存在.思考思考?通過上述算法的兩種不同表達(dá)方式的比通過上述算法的兩種不同表達(dá)方式的比較較,你覺得用程序框圖來表達(dá)算法有哪些特點(diǎn)你覺得用程序框圖來表達(dá)算法有哪些特點(diǎn)?用程序框圖表示的算法更加簡練用程序框圖表示的算法更加簡練,直觀直觀,流向清流向清楚楚.開始開始輸入輸入ni=2求求n除以除以i的余數(shù)的余數(shù)ri=i+1in或或r=0?n不是質(zhì)數(shù)不是質(zhì)數(shù)結(jié)束結(jié)束是是否否是是n是質(zhì)數(shù)是質(zhì)數(shù)否否r=0?順序結(jié)構(gòu)順序結(jié)構(gòu)用程

16、序框圖來表示算法，有用程序框圖來表示算法，有三種不同的基本邏輯結(jié)構(gòu)：三種不同的基本邏輯結(jié)構(gòu)：條件結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)程序框圖的三種基本的邏輯結(jié)構(gòu)程序框圖的三種基本的邏輯結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)條件結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)(1)順序結(jié)構(gòu)順序結(jié)構(gòu)-是由若干個(gè)依次執(zhí)行的處理是由若干個(gè)依次執(zhí)行的處理步驟組成的步驟組成的.這是任何一個(gè)算法都離不開的這是任何一個(gè)算法都離不開的基本結(jié)構(gòu)基本結(jié)構(gòu).例例1:已知一個(gè)三角形的三邊邊長分別為已知一個(gè)三角形的三邊邊長分別為2,3,4,利用海倫利用海倫-秦九韶公式設(shè)計(jì)一個(gè)算法秦九韶公式設(shè)計(jì)一個(gè)算法,求出它的求出它的面積面積,畫出算法的程序框圖畫出算法的程序框圖.

17、算法分析算法分析:第一步第一步:計(jì)算計(jì)算p的值的值.第二步第二步:由海倫由海倫-秦九韶公式求出三角形的面積秦九韶公式求出三角形的面積S.第三步第三步:輸出輸出S的值的值. A B(1)順序結(jié)構(gòu)順序結(jié)構(gòu)-是由若干個(gè)依次執(zhí)行的處理是由若干個(gè)依次執(zhí)行的處理步驟組成的步驟組成的.這是任何一個(gè)算法都離不開的這是任何一個(gè)算法都離不開的基本結(jié)構(gòu)基本結(jié)構(gòu).例例1:已知一個(gè)三角形的三邊邊長分別為已知一個(gè)三角形的三邊邊長分別為2,3,4,利用海倫利用海倫-秦九韶公式設(shè)計(jì)一個(gè)算法秦九韶公式設(shè)計(jì)一個(gè)算法,求出它的求出它的面積面積,畫出算法的程序框圖畫出算法的程序框圖.算法分析算法分析:第一步第一步:計(jì)算計(jì)算p的值的值

18、.第二步第二步:由海倫由海倫-秦九韶公式求出三角形的面積秦九韶公式求出三角形的面積S.第三步第三步:輸出輸出S的值的值.程序框圖程序框圖:結(jié)束結(jié)束開始開始2342p (2)(3)(4)Sp ppp輸出輸出S畫出畫出:已知三角形的三已知三角形的三邊長邊長a,b,c,求它的面積求它的面積的程序框圖的程序框圖.結(jié)束結(jié)束開始開始2abcp()()()Sp papbpc輸出輸出S輸入輸入a,b,c(2)條件結(jié)構(gòu)條件結(jié)構(gòu)-在一個(gè)算法中在一個(gè)算法中,經(jīng)常會(huì)遇到一經(jīng)常會(huì)遇到一些條件的判斷些條件的判斷,算法的流向根據(jù)條件是否成算法的流向根據(jù)條件是否成立有不同的流向立有不同的流向.條件結(jié)構(gòu)就是處理這種過條件結(jié)構(gòu)就是處理這種過程的結(jié)構(gòu)程的結(jié)構(gòu).例例2:任意給定任意給定3個(gè)正實(shí)數(shù)個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法設(shè)計(jì)一個(gè)算法,判斷分判斷分別以這別以這3個(gè)數(shù)為三邊邊長的三角形是否存在個(gè)數(shù)為三邊邊長的三角形是否存在.畫畫出這個(gè)算法的程序框圖出這個(gè)算法的程序框圖.算法分析算法分析:第一步第一步:輸入輸入3個(gè)正實(shí)數(shù)個(gè)正實(shí)數(shù)a,b,c;第二步第二步:判斷判斷a+bc,a+cb,b+ca是否同時(shí)成立是否同時(shí)成立,若是若是,則能組成三角形則能組成三角形;若否若否,則組不成三角