《算法與程序框圖ppt課件》由會員分享，可在線閱讀，更多相關(guān)《算法與程序框圖ppt課件（71頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1.1算法與程序框圖,1,問題的提出,有一個農(nóng)夫帶一條狼狗、一只羊和一筐白菜過河。如果沒有農(nóng)夫看管，則狼狗要吃羊，羊要吃白菜。但是船很小，只夠農(nóng)夫帶一樣?xùn)|西過河。問農(nóng)夫該如何解此難題？,方法和過程：,1、帶羊到對岸，返回；,2、帶菜到對岸，并把羊帶回；,3、帶狼狗到對岸，返回；,4、帶羊到對岸。,2,[問題1]請你寫出解二元一次方程組的詳細(xì)求解過程.,3,,解方程,第一步,,由（1）得,第二步,,將（3）代入（2）得,第三步,,解（4）得,第四步,,將（5）代入（3）得,第五步,,得到方程組的解得,4,,解方程,第一步,,第二步,,第三步,,第四步,,第五步,,得到方程組的解得,5,廣義地說：為了解決某一問題而采取的方法和步驟，就稱之為算法。,在數(shù)學(xué)中，按照一定規(guī)則解決某一類問題的明確和有限的步驟，稱為算法。,現(xiàn)在，算法通?？梢跃幊捎嬎銠C程序，讓計算機執(zhí)行并解決問題。這些程序或步驟必須是明確和有效的,而且能夠在有限步之內(nèi)完成.,算法的概念:,沒有軟件的支持，計算機只是一堆廢鐵而已；,軟件的核心就是算法 ！,6,算法的特征,一.確定性: 每一步必須有確切的定義。 二.有效性：原則上必須能夠精確的運行。 三.有窮性：一個算法必須保證執(zhí)行有限步 后結(jié)束,算法的優(yōu)缺點,一.缺點:算法一般是機械的,有時需要進行大量重復(fù)的計算. 二.優(yōu)點:算法是一種通法,只要按照步驟去做,總能得到結(jié)果.,7,廣播操圖解是廣播操的算法； 菜譜是做菜的算法； 歌譜是一首歌曲的算法； 空調(diào)說明書是空調(diào)使用的算法等,我們身邊的算法,8,算法學(xué)的發(fā)展,隨著科學(xué)技術(shù)的日新月異,算法學(xué)也得到了前所未有的發(fā)展,現(xiàn)在已經(jīng)發(fā)展到了各個領(lǐng)域.有遺傳算法,排序算法,加密算法,蟻群算法等,與生物學(xué),計算機科學(xué)等有著很廣泛的聯(lián)系,尤其是在現(xiàn)在的航空航天中,更是有著更廣泛的應(yīng)用. 很多復(fù)雜的運算都是借助計算機和算法來完成的,在高端科學(xué)技術(shù)中有著很重要的地位.,9,應(yīng)用舉例,,,例1.(1)設(shè)計一個算法判斷7是否為質(zhì)數(shù).,第一步, 用2除7,得到余數(shù)1.因為余數(shù)不為0， 所以2不能整除7.,第二步, 用3除7,得到余數(shù)1.因為余數(shù)不為0， 所以3不能整除7.,第三步, 用4除7,得到余數(shù)3.因為余數(shù)不為0， 所以4不能整除7.,第四步, 用5除7,得到余數(shù)2.因為余數(shù)不為0， 所以5不能整除7.,第五步, 用6除7,得到余數(shù)1.因為余數(shù)不為0， 所以6不能整除7.因此，7是質(zhì)數(shù).,10,應(yīng)用舉例,,,例1.(2)設(shè)計一個算法判斷35是否為質(zhì)數(shù).,第一步, 用2除35,得到余數(shù)1.因為余數(shù)不為0， 所以2不能整除35.,第二步, 用3除35,得到余數(shù)2.因為余數(shù)不為0， 所以3不能整除35.,第三步, 用4除35,得到余數(shù)3.因為余數(shù)不為0， 所以4不能整除7.,第四步, 用5除35,得到余數(shù)0.因為余數(shù)為0， 所以5能整除35.因此，35不是質(zhì)數(shù).,11,“判斷整數(shù)n（n2）是否為質(zhì)數(shù)”的算法步驟如何？,第一步，給定一個大于2的整數(shù)n；,第二步，令i=2；,第三步，用i除n，得到余數(shù)r；,第四步，判斷“r=0”是否成立.若是，則n 不是質(zhì)數(shù)，結(jié)束算法；否則，將i 的值增加1，仍用i表示；,第五步，判斷“i(n-1)”是否成立，若是， 則n是質(zhì)數(shù)，結(jié)束算法；否則，返回 第三步.,12,應(yīng)用舉例,,,13,探究解決,,,對于區(qū)間[a,b ]上連續(xù)不斷、且 f(a)f(b)0的函數(shù)y=f(x),通過不斷地 把函數(shù)f(x)的零點所在的區(qū)間一分 為二，使區(qū)間的兩個端點逐步逼近 零點，進而得到零點近似值的方法 叫做二分法.,14,解決問題,,,,×,,第四步, 若f(a) ·f(m) 0,則含零點的區(qū)間為［a,m］；,第一步, 令 .給定精確度d.,第二步, 給定區(qū)間［a,b］,滿足f(a) ·f(b)＜0．,第三步, 取中間點 ．,第五步, 判斷［a,b］的長度是否小于d或者 f(m)是否等于０.,將新得到的含零點的仍然記為［a,b］ .,否則，含零點的區(qū)間為［m, b］.,若是，則m是方程的近似 解;否則，返回第三步．,15,解決問題,,,當(dāng)d=0.05時,評析:實際上,上述步驟就是在求 的近似值.,16,與一般的解決問題的過程比較,算法有以下特征: ①設(shè)計一個具體問題的算法時,與過去熟悉地解數(shù)學(xué)題的過程有直接的聯(lián)系,但這個過程必須被分解成若干個明確的步驟,而且這些步驟必須是有效的. ②算法要“面面俱到”,不能省略任何一個細(xì)小的步驟,只有這樣,才能在人設(shè)計出算法后,把具體的執(zhí)行過程交給計算機完成.,17,練習(xí)一:任意給定一個正實數(shù),設(shè)計一個算法求以這個數(shù)為半徑的圓的面積.,算法分析:,第一步:輸入任意一個正實數(shù)r; 第二步:計算以r為半徑的圓的面積S=πr2; 第三步:輸出圓的面積.,課本5頁 1,18,練習(xí)二:任意給定一個大于1的正整數(shù)n,設(shè)計一個算法求出n的所有因數(shù).,算法分析:,第一步:依次以2~(n-1)為除數(shù)去除n,判斷余數(shù)是否為0,若是,則是n的因數(shù);若不是,則不是n的因數(shù). 第二步:在n的因數(shù)中加入1和n; 第三步:輸出n的所有因數(shù).,課本5頁 2,19,計算機解決任何問題都要依賴于算法.只有將解決問題的過程分解為若干個明確的步驟,即算法,并用計算機能夠接受的“語言”準(zhǔn)確地描述出來,計算機才能夠解決問題.,20,1.1.2 程序框圖,21,問題提出,1.算法的含義是什么？,在數(shù)學(xué)中，按照一定規(guī)則解決某一類問題的明確和有限的步驟稱為算法.,2.算法是由一系列明確和有限的計算步驟組成的，我們可以用自然語言表述一個算法，但往往過程復(fù)雜，缺乏簡潔性，因此，我們有必要探究使算法表達(dá)得更加直觀、準(zhǔn)確的方法，這個想法可以通過程序框圖來實現(xiàn).,22,知識探究（一）：算法的程序框圖,思考1:“判斷整數(shù)n（n2）是否為質(zhì)數(shù)”的算法步驟如何？,第一步，給定一個大于2的整數(shù)n；,第二步，令i=2；,第三步，用i除n，得到余數(shù)r；,第四步，判斷“r=0”是否成立.若是，則n 不是質(zhì)數(shù)，結(jié)束算法；否則，將i 的值增加1，仍用i表示；,第五步，判斷“i(n-1)”是否成立，若是， 則n是質(zhì)數(shù)，結(jié)束算法；否則，返回 第三步.,23,i=i+1,思考2 ：為了使算法的程序或步驟表達(dá)得更為直觀,我們更經(jīng)常地用圖形方式來表示它.,24,程序框圖又稱流程圖,是一種用規(guī)定的圖形、指向線及文字說明來準(zhǔn)確、直觀地表示算法的圖形.,通常,程序框圖由程序框和流程線組成.,一個或幾個程序框的組合表示算法中的一個步驟;,流程線是方向箭頭,按照算法進行的順序?qū)⒊绦?框連接起來.,25,思考3：基本的程序框和它們各自表示的功能？,,,,,,,終端框(起止框),表示一個算法的起始和結(jié)束,輸入、輸出框,表示一個算法輸入和輸出的信息,處理框(執(zhí)行框),判斷某一條件是否成立,成立時在出口處標(biāo)明“是”或“Y”；不”成立時標(biāo)明“否”或“N”.,判斷框,賦值、計算,流程線,連接程序框,連接點,連接程序框圖的兩部分,26,設(shè)n是一個大于2的整數(shù).,一般用i=i+1表示.,i=i+1,說明:i表示從2~(n-1)的所有正整數(shù),用以判斷例1步驟2是否終止,i是一個計數(shù)變量,有了這個變量,算法才能依次執(zhí)行.逐步考察從2~(n-1)的所有正整數(shù)中是否有n的因數(shù)存在.,,27,思考4：通過上述算法的兩種不同表達(dá)方式的比較,你覺得用程序框圖來表達(dá)算法有哪些特點?,用程序框圖表示的算法更加簡練,直觀,流向清楚.,28,,順序結(jié)構(gòu),思考:5：用程序框圖來表示算法，有幾種不同的基本邏輯結(jié)構(gòu)？,,條件結(jié)構(gòu),,循環(huán)結(jié)構(gòu),29,知識探究（二）：算法的順序結(jié)構(gòu),思考1:任何一個算法各步驟之間都有明確的順序性，在算法的程序框圖中，由若干個依次執(zhí)行的步驟組成的邏輯結(jié)構(gòu)，稱為順序結(jié)構(gòu)，用程序框圖可以表示為：,30,思考2:若一個三角形的三條邊長分別為a，b，c，令 ，則三角形的面積 .你能利用這個公式設(shè)計一個計算三角形面積的算法步驟嗎？,第一步，輸入三角形三條邊的邊長 a，b，c.,第二步，計算 .,第三步，計算 .,第四步，輸出S.,31,思考3:上述算法的程序框圖如何表示？,32,練習(xí)：,1.就（1）、（2）兩種邏輯結(jié)構(gòu)，說出各自的算法功能,,（2）,,答案：（1）求直角三角形斜邊長；,（2）求兩個數(shù)的和．,33,順序結(jié)構(gòu)的程序框圖的基本特征：,順序結(jié)構(gòu)知識小結(jié),（2）各程序框從上到下用流程線依次連接.,（1）必須有兩個起止框，穿插輸入、輸出框和處理框，沒有判斷框.,（3）處理框按計算機執(zhí)行順序沿流程線依次排列.,34,條件結(jié)構(gòu),r=0?,N不是質(zhì)數(shù),n是質(zhì)數(shù),是,否,知識探究（三）：算法的條件結(jié)構(gòu),35,,,36,課本例4:任意給定3個正實數(shù),設(shè)計一個算法,判斷分別以這3個數(shù)為三邊邊長的三角形是否存在.畫出這個算法的程序框圖.,算法分析:,第一步:輸入3個正實數(shù)a,b,c;,第二步:判斷a+bc,a+cb,b+ca是否同時成立,若是,則能組成三角形;若否,則組不成三角形.,,37,程序框圖:,開始,,輸入a,b,c,,a+bc,a+cb,b+ca是否 同時成立?,,是,存在這樣的 三角形,不存在這樣的 三角形,否,,結(jié)束,,38,算法步驟如下（課本例5）：,39,開始,,輸入a，b，c,,,,,,,,,,,,,,,,X1=p+q,X2=p-q,輸出x1,x2,輸出“方程沒 有實數(shù)根”,輸出p,結(jié)束,否,是,否,是,,,40,是,練習(xí)2：設(shè)計一個求任意數(shù)的絕對值的算法,并畫出程序框圖.,算法分析:,第一步:輸入數(shù)x; 第二步:判斷x≥0是否成立?若是,則|x|=x;若否,則|x|=-x.,程序框圖:,開始,,輸入x,,x≥0?,,輸出x,否,輸出-x,,結(jié)束,41,練習(xí)3：畫程序框圖,對于輸入的x值,輸出相應(yīng)的y值.,開始,,程序框圖,x0?,是,y=0,,否,0≤x1?,是,y=1,,否,y=x,,輸出y,結(jié)束,,輸入x,,42,P:50頁A組T1(2),開始,,程序框圖,x0?,是,y=(x+2)2,,否,x=0?,是,y=4,,否,,輸出y,結(jié)束,,輸入x,,y=(x-2)2,43,練習(xí)5：,1.就邏輯結(jié)構(gòu)，說出其算法功能．,,2.此為某一函數(shù)的求值程序圖，則滿足該流程圖的函數(shù)解析式為（ ）（不能寫成分段函數(shù)）．,,,3.求函數(shù) 的值的算法流程圖．,,開始,輸入x,X2?,y=－2,,,輸出y,結(jié)束,,,,,,是,答案:1.求兩個數(shù)中的最大值.,答案:2. y=|x-3|+1.,44,循環(huán)結(jié)構(gòu),i=i+1,in-1,或r=0?,否,是,求n除以i的余數(shù)r,循環(huán)結(jié)構(gòu)---在一些算法中,也經(jīng)常會出現(xiàn)從某處開始,按照一定條件,反復(fù)執(zhí)行某一步驟的情況,這就是循環(huán)結(jié)構(gòu).,,,,,知識探究（四）：算法的循環(huán)結(jié)構(gòu),45,引例：設(shè)計一算法，求和:1+2+3+…+100,第一步：確定首數(shù)a，尾數(shù)b，項數(shù)n；,第二步：利用公式“總和=(首數(shù)+尾數(shù)）×項數(shù)/2”求和；,第三步：輸出求和結(jié)果。,算法1：,46,課本例6:設(shè)計一個計算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):,為了方便有效地表示上述過程,我們引進一個變量S來表示每一步的計算結(jié)果,從而把第i步表示為 S=S+i,S=0 S=S + 1 S=S + 2 S=S + 3 … S=S + 100,47,求和:1+2+3+…+100,S=S+ i,怎么用程序框圖表示呢？,思考1：i有什么作用?S呢？,S=0 S=S + 1 S=S + 2 S=S + 3 … S=S + 100,累加變量S來表示每一步的計算結(jié)果,從而把第i步表示為 S=S+i,S的初始值為0,i依次取1,2,…,100,,由于i同時記錄了循環(huán)的次數(shù),所以i稱為計數(shù)變量.,48,,解決方法就是加上一個判斷，判斷是否已經(jīng)加到了100，如果加到了則退出，否則繼續(xù)加。,,試分析兩種流程的異同點,直到型結(jié)構(gòu),當(dāng)型結(jié)構(gòu),i=100?,i100?,請?zhí)钌吓袛嗟臈l件。,49,程序框圖:,開始,,i=1,,S=0,,S=S+i,,i=i+1,,i100?,是,,輸出S,,結(jié)束,否,直到型循環(huán)結(jié)構(gòu),開始,,i=1,,S=0,,i≤100?,是,S=S+i,,i=i+1,否,,輸出S,,結(jié)束,當(dāng)型循環(huán)結(jié)構(gòu),50,思考2：若將“i=1”改成“i=0”，則程序框圖怎么改？,直到型循環(huán)結(jié)構(gòu),當(dāng)型循環(huán)結(jié)構(gòu),51,思考:3:將步驟A和步驟B交換位置，結(jié)果會怎樣？能達(dá)到預(yù)期結(jié)果嗎？為什么？要達(dá)到預(yù)期結(jié)果，還需要做怎樣的修改？,答：達(dá)不到預(yù)期結(jié)果；當(dāng)i = 100時，沒有退出循環(huán)，i的值為101加入到S中；修改的方法是將判斷條件改為i100,52,Until（直到型）循環(huán),說明（1）循環(huán)結(jié)構(gòu)分為兩種------當(dāng)型和直到型.,當(dāng)型循環(huán)在每次執(zhí)行循環(huán)體前對循環(huán)條件進行判斷,當(dāng)條件滿足時執(zhí)行循環(huán)體,不滿足則停止;(當(dāng)條件滿足時反復(fù)執(zhí)行循環(huán)體),直到型循環(huán)在執(zhí)行了一次循環(huán)體之后,對控制循環(huán)條件進行判斷,當(dāng)條件不滿足時執(zhí)行循環(huán)體,滿足則停止.(反復(fù)執(zhí)行循環(huán)體,直到條件滿足),53,（2）注意:循環(huán)結(jié)構(gòu)不能是永無終止的“死循環(huán)”,一定要在某個條件下終止循環(huán),這就需要條件結(jié)構(gòu)來作出判斷,因此,循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu).,說明:一般地,循環(huán)結(jié)構(gòu)中都有一個計數(shù)變量和累加變量.計數(shù)變量用于記錄循環(huán)次數(shù),同時它的取值還用于判斷循環(huán)是否終止,這個變量的取值一般都含在執(zhí)行或終止循環(huán)體的條件中。 累加變量用于輸出結(jié)果.累加變量和計數(shù)變量一般是同步執(zhí)行的,累加一次,記數(shù)一次.,54,結(jié)束,輸出S,i=0，S=0,開始,i = i + 1,S=S + i,i=n?,否,是,輸入n,,改進上面的算法，表示輸出1,1+2,1+2+3, …, 1+2+3+…+(n-1)+n( ) 的過程。,55,練習(xí)鞏固,1、設(shè)計一算法，求積:1×2×3×…×100，畫出流程圖,思考：該流程圖與前面的課本例6中求和的流程圖有何不同？,56,課本例7： 某工廠2005年的年生產(chǎn)總值為200萬，技術(shù)革新以后每年的年生產(chǎn)總值比上一年增長5％。設(shè)計一個程序框圖，輸出預(yù)計年生產(chǎn)總值超過300萬元的最早年份。,算法分析：,第一步，輸入2005年的年生產(chǎn)總值。,第二步，計算下一年的年生產(chǎn)總值。,第三步，判斷所得的結(jié)果是否大于300.若是，則輸出該年的年份；否則，返回第二步,57,由于“第二步”是重復(fù)操作的步驟，所以可以用循環(huán)結(jié)構(gòu)來實現(xiàn)。我們按照“確定循環(huán)體” “初始化變量” “設(shè)定循環(huán)控制條件”的順序來構(gòu)造循環(huán)結(jié)構(gòu)。,（2）初始化變量：若將2005年的年生產(chǎn)總值堪稱計算的起始點，則n的初始值為2005，a的初始值為200.,（3）設(shè)定循環(huán)控制條件：當(dāng)“年生產(chǎn)總值超過300萬元”時終止循環(huán)，所以可通過判斷“a300”是否成立來控制循環(huán)。,（1）確定循環(huán)體：設(shè)a為某年的年生產(chǎn)總值，t為年生產(chǎn)總值的年增長量，n為年份，則循環(huán)體為,58,程序框圖:,開始,,n=2005,,a=200,,t=0.05a,,n=n+1,,a300?,是,,輸出n,,結(jié)束,否,a=a+t,,59,小結(jié),1、循環(huán)結(jié)構(gòu)的特點,2、循環(huán)結(jié)構(gòu)的框圖表示,3、循環(huán)結(jié)構(gòu)有注意的問題,避免死循環(huán)的出現(xiàn)，設(shè)置好進入（結(jié)束）循環(huán)體的條件。,當(dāng)型和直到型,重復(fù)同一個處理過程,60,61,62,63,64,【答案】D,65,【答案】C,66,67,【答案】B.,68,69,【答案】B,70,作業(yè): 課本P20頁A組2;,71,