算法與程序框圖ppt

1.1算法與程序框圖問題的提出有一個(gè)農(nóng)夫帶一條狼狗、一只羊和一筐白菜過河。如果沒有農(nóng)夫看管，那么狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？方法和過程：1、帶羊到對(duì)岸，返回；2、帶菜到對(duì)岸，并把羊帶回；3、帶狼狗到對(duì)岸，返回；4、帶羊到對(duì)岸。廣義地說：為了解決某一問題而采取的方法和步驟，就稱之為算法。在數(shù)學(xué)中，按照一定規(guī)那么解決某一類問題的明確和有限的步驟，稱為算法?，F(xiàn)在，算法通?？梢跃幊捎?jì)算機(jī)程序，讓計(jì)算機(jī)執(zhí)行并解決問題。這些程序或步驟必須是明確和有效的,而且能夠在有限步之內(nèi)完成.算法的概念:沒有軟件的支持，計(jì)算機(jī)只是一堆廢鐵而已；軟件的核心就是算法！算法的特征一.確定性:每一步必須有確切的定義。二.有效性：原那么上必須能夠精確的運(yùn)行。三.有窮性：一個(gè)算法必須保證執(zhí)行有限步后結(jié)束算法的優(yōu)缺點(diǎn)一.缺點(diǎn):算法一般是機(jī)械的,有時(shí)需要進(jìn)行大量重復(fù)的計(jì)算.二.優(yōu)點(diǎn):算法是一種通法,只要按照步驟去做,總能得到結(jié)果.播送操圖解是播送操的算法；菜譜是做菜的算法；歌譜是一首歌曲的算法；空調(diào)說明書是空調(diào)使用的算法等我們身邊的算法應(yīng)用舉例例1.(1)設(shè)計(jì)一個(gè)算法判斷7是否為質(zhì)數(shù).第一步,用2除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以2不能整除7.第二步,用3除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以3不能整除7.第三步,用4除7,得到余數(shù)3.因?yàn)橛鄶?shù)不為0，所以4不能整除7.第四步,用5除7,得到余數(shù)2.因?yàn)橛鄶?shù)不為0，所以5不能整除7.第五步,用6除7,得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以6不能整除7.因此，7是質(zhì)數(shù).應(yīng)用舉例例1.(2)設(shè)計(jì)一個(gè)算法判斷35是否為質(zhì)數(shù).第一步,用2除35,得到余數(shù)1.因?yàn)橛鄶?shù)不為0，所以2不能整除35.第二步,用3除35,得到余數(shù)2.因?yàn)橛鄶?shù)不為0，所以3不能整除35.第三步,用4除35,得到余數(shù)3.因?yàn)橛鄶?shù)不為0，所以4不能整除7.第四步,用5除35,得到余數(shù)0.因?yàn)橛鄶?shù)為0，所以5能整除35.因此，35不是質(zhì)數(shù).任意給定一個(gè)大于1的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是否為質(zhì)數(shù)做出判定.第一步：判斷n是否等于2.假設(shè)n=2，那么n是質(zhì)數(shù)；假設(shè)n>2，那么執(zhí)行第二步.第二步:依次從2～〔n－1〕檢驗(yàn)是不是n的因數(shù)，即整除n的數(shù),假設(shè)有這樣的數(shù)，那么n不是質(zhì)數(shù)；假設(shè)沒有這樣的數(shù)，那么n是質(zhì)數(shù).這是判斷一個(gè)大于1的整數(shù)n是否為質(zhì)數(shù)的最根本算法.用語(yǔ)言描述一個(gè)算法,最便捷的方式就是按解決問題的步驟進(jìn)行描述.每一步做一件事情.應(yīng)用舉例例2.用二分法設(shè)計(jì)一個(gè)求方程的近似根的算法.探究解決

對(duì)于區(qū)間[a,b]上連續(xù)不斷、且f(a)f(b)<0的函數(shù)y=f(x),通過不斷地把函數(shù)f(x)的零點(diǎn)所在的區(qū)間一分為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)近似值的方法叫做二分法.解決問題×第四步,假設(shè)f(a)·f(m)<0,那么含零點(diǎn)的區(qū)間為［a,m］；第一步,令.給定精確度d.第二步,給定區(qū)間［a,b］,滿足f(a)·f(b)＜0．第三步,取中間點(diǎn)．第五步,判斷［a,b］的長(zhǎng)度是否小于d或者f(m)是否等于０.將新得到的含零點(diǎn)的仍然記為［a,b］

.否那么，含零點(diǎn)的區(qū)間為［m,b］.假設(shè)是，那么m是方程的近似解;否那么，返回第三步．解決問題當(dāng)d=0.05時(shí)評(píng)析:實(shí)際上,上述步驟就是在求的近似值.與一般的解決問題的過程比較,算法有以下特征:①設(shè)計(jì)一個(gè)具體問題的算法時(shí),與過去熟悉地解數(shù)學(xué)題的過程有直接的聯(lián)系,但這個(gè)過程必須被分解成假設(shè)干個(gè)明確的步驟,而且這些步驟必須是有效的.②算法要“面面俱到〞,不能省略任何一個(gè)細(xì)小的步驟,只有這樣,才能在人設(shè)計(jì)出算法后,把具體的執(zhí)行過程交給計(jì)算機(jī)完成.練習(xí)一:任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.算法分析:第一步:輸入任意一個(gè)正實(shí)數(shù)r;第二步:計(jì)算以r為半徑的圓的面積S=πr2;第三步:輸出圓的面積.課本5頁(yè)1練習(xí)二:任意給定一個(gè)大于1的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).算法分析:第一步:依次以2~(n-1)為除數(shù)去除n,判斷余數(shù)是否為0,假設(shè)是,那么是n的因數(shù);假設(shè)不是,那么不是n的因數(shù).第二步:在n的因數(shù)中參加1和n;第三步:輸出n的所有因數(shù).課本5頁(yè)2 計(jì)算機(jī)解決任何問題都要依賴于算法.只有將解決問題的過程分解為假設(shè)干個(gè)明確的步驟,即算法,并用計(jì)算機(jī)能夠接受的“語(yǔ)言〞準(zhǔn)確地描述出來,計(jì)算機(jī)才能夠解決問題.1.1.2程序框圖例1:任意給定一個(gè)大于1的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對(duì)n是否為質(zhì)數(shù)做出判定.算法分析:第一步:判斷n是否等于2.若n=2,則n是質(zhì)數(shù);若n>2,則執(zhí)行第二步.第二步:依次檢驗(yàn)2~(n-1)這些整數(shù)是不是n的因素,即是不是整除n的數(shù).若有這樣的數(shù),則n不是質(zhì)數(shù);若沒有這樣的數(shù),則n是質(zhì)數(shù). 從上節(jié)課我們知道:算法可以用自然語(yǔ)言來描述.如例1為了使算法的程序或步驟表達(dá)得更為直觀,我們更經(jīng)常地用圖形方式來表示它.開始輸入ni=2求n除以i的余數(shù)ri的值增加1仍用i表示i≥n或r=0?n不是質(zhì)數(shù)結(jié)束是否是n是質(zhì)數(shù)否r=0?i=i+1

程序框圖又稱流程圖,是一種用規(guī)定的圖形、指向線及文字說明來準(zhǔn)確、直觀地表示算法的圖形. 通常,程序框圖由程序框和流程線組成.一個(gè)或幾個(gè)程序框的組合表示算法中的一個(gè)步驟;流程線是方向箭頭,按照算法進(jìn)行的順序?qū)⒊绦蚩蜻B接起來.根本的程序框和它們各自表示的功能如下:終端框(起止框)表示一個(gè)算法的起始和結(jié)束輸入、輸出框表示一個(gè)算法輸入和輸出的信息處理框(執(zhí)行框)判斷某一條件是否成立,成立時(shí)在出口處標(biāo)明“是〞或“Y〞；不〞成立時(shí)標(biāo)明“否〞或“N〞.判斷框賦值、計(jì)算流程線連接程序框連接點(diǎn)連接程序框圖的兩局部開始輸入ni=2求n除以i的余數(shù)ri的值增加1仍用i表示i≥n或r=0?n不是質(zhì)數(shù)結(jié)束是否是n是質(zhì)數(shù)否r=0?設(shè)n是一個(gè)大于2的整數(shù).一般用i=i+1表示.i=i+1說明:i表示從2~(n-1)的所有正整數(shù),用以判斷例1步驟2是否終止,i是一個(gè)計(jì)數(shù)變量,有了這個(gè)變量,算法才能依次執(zhí)行.逐步考察從2~(n-1)的所有正整數(shù)中是否有n的因數(shù)存在.思考?通過上述算法的兩種不同表達(dá)方式的比較,你覺得用程序框圖來表達(dá)算法有哪些特點(diǎn)?用程序框圖表示的算法更加簡(jiǎn)練,直觀,流向清楚.開始輸入ni=2求n除以i的余數(shù)ri=i+1i≥n或r=0?n不是質(zhì)數(shù)結(jié)束是否是n是質(zhì)數(shù)否r=0?順序結(jié)構(gòu)用程序框圖來表示算法，有三種不同的根本邏輯結(jié)構(gòu)：條件結(jié)構(gòu)循環(huán)結(jié)構(gòu) 程序框圖的三種根本的邏輯結(jié)構(gòu)順序結(jié)構(gòu)條件結(jié)構(gòu)循環(huán)結(jié)構(gòu)(1)順序結(jié)構(gòu)-----是由假設(shè)干個(gè)依次執(zhí)行的處理步驟組成的.這是任何一個(gè)算法都離不開的根本結(jié)構(gòu). 例1:一個(gè)三角形的三邊邊長(zhǎng)分別為2,3,4,利用海倫-秦九韶公式設(shè)計(jì)一個(gè)算法,求出它的面積,畫出算法的程序框圖.算法分析:第一步:計(jì)算p的值.第二步:由海倫-秦九韶公式求出三角形的面積S.第三步:輸出S的值.AB(1)順序結(jié)構(gòu)-----是由假設(shè)干個(gè)依次執(zhí)行的處理步驟組成的.這是任何一個(gè)算法都離不開的根本結(jié)構(gòu). 例1:一個(gè)三角形的三邊邊長(zhǎng)分別為2,3,4,利用海倫-秦九韶公式設(shè)計(jì)一個(gè)算法,求出它的面積,畫出算法的程序框圖.算法分析:第一步:計(jì)算p的值.第二步:由海倫-秦九韶公式求出三角形的面積S.第三步:輸出S的值.程序框圖:開始輸出S結(jié)束畫出:三角形的三邊長(zhǎng)a,b,c,求它的面積的程序框圖.開始輸出S結(jié)束輸入a,b,c已知三角形三邊長(zhǎng)分別為a,b,c,則三角形的面積為其中這個(gè)公式被稱為海倫—秦九韶公式.返回(2)條件結(jié)構(gòu)---在一個(gè)算法中,經(jīng)常會(huì)遇到一些條件的判斷,算法的流向根據(jù)條件是否成立有不同的流向.條件結(jié)構(gòu)就是處理這種過程的結(jié)構(gòu).例2:任意給定3個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法,判斷分別以這3個(gè)數(shù)為三邊邊長(zhǎng)的三角形是否存在.畫出這個(gè)算法的程序框圖.算法分析:第一步:輸入3個(gè)正實(shí)數(shù)a,b,c;第二步:判斷a+b>c,a+c>b,b+c>a是否同時(shí)成立,假設(shè)是,那么能組成三角形;假設(shè)否,那么組不成三角形.程序框圖:開始輸入a,b,ca+b>c,a+c>b,b+c>a是否同時(shí)成立?是存在這樣的三角形不存在這樣的三角形否結(jié)束課本50頁(yè)1〔1〕開始程序框圖x<0?是y=0否0≤x<1?是y=1否y=x輸出y結(jié)束輸入x作業(yè):課本P50頁(yè)A組1〔2〕,(畫出程序框圖)(3)循環(huán)結(jié)構(gòu)---在一些算法中,也經(jīng)常會(huì)出現(xiàn)從某處開始,按照一定條件,反復(fù)執(zhí)行某一步驟的情況,這就是循環(huán)結(jié)構(gòu).反復(fù)執(zhí)行的步驟稱為循環(huán)體.注意:循環(huán)結(jié)構(gòu)不能是永無終止的“死循環(huán)〞,一定要在某個(gè)條件下終止循環(huán),這就需要條件結(jié)構(gòu)來作出判斷,因此,循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu).例3:設(shè)計(jì)一個(gè)計(jì)算1+2+3+……+100的值的算法,并畫出程序框圖.算法分析:第1步:0+1=1;第2步:1+2=3;第3步:3+3=6;第4步:6+4=10…………第100步:4950+100=5050.第(i-1)步的結(jié)果+i=第i步的結(jié)果各步驟有共同的結(jié)構(gòu):為了方便有效地表示上述過程,我們引進(jìn)一個(gè)累加變量S來表示每一步的計(jì)算結(jié)果,從而把第i步表示為S=S+iS的初始值為0,i依次取1,2,…,100,由于i同時(shí)記錄了循環(huán)的次數(shù),所以i稱為計(jì)數(shù)變量.程序框圖:開始i=1S=0S=S+ii=i+1i>100?是輸出S