1[1]11算法的概念及程序框圖

1、 簡單地說，算法就是解決問題的程序或步驟。例例1：設(shè)計一個算法，判斷：設(shè)計一個算法，判斷7是否為質(zhì)數(shù)。是否為質(zhì)數(shù)。算法：第一步，用第一步，用2除除7，得到余數(shù)，得到余數(shù)1。因為余數(shù)不為。因為余數(shù)不為0，所以，所以2不能整除不能整除7。第二步，用第二步，用3除除7，得到余數(shù)，得到余數(shù)1。因為余數(shù)不為。因為余數(shù)不為0，所以，所以3不能整除不能整除7。第三步，用第三步，用4除除7，得到余數(shù)，得到余數(shù)3。因為余數(shù)不為。因為余數(shù)不為0，所以，所以4不能整除不能整除7。第四步，用第四步，用5除除7，得到余數(shù)，得到余數(shù)2。因為余數(shù)不為。因為余數(shù)不為0，所以，所以5不能整除不能整除7。第五步，用第五步，用6除

2、除7，得到余數(shù)，得到余數(shù)1。因為余數(shù)不為。因為余數(shù)不為0，所以，所以6不能整除不能整除7。因此，。因此，7是質(zhì)數(shù)。是質(zhì)數(shù)。例例2：設(shè)計一個算法，判斷：設(shè)計一個算法，判斷53是否為質(zhì)數(shù)。是否為質(zhì)數(shù)。第一步，用第一步，用2除除53，得到余數(shù)，得到余數(shù)1。因為余數(shù)不為。因為余數(shù)不為0，所以，所以2不能整除不能整除53。第二步，用第二步，用3除除53，得到余數(shù)，得到余數(shù)2。因為余數(shù)不為。因為余數(shù)不為0，所以，所以3不能整除不能整除53。第三步，用第三步，用4除除53，得到余數(shù)，得到余數(shù)1。因為余數(shù)不為。因為余數(shù)不為0，所以，所以4不能整除不能整除53。第五十一步，用第五十一步，用52除除53，得到余數(shù)

3、，得到余數(shù)1。因為余數(shù)不為。因為余數(shù)不為0，所以所以52不能整除不能整除53。因此，。因此，53是質(zhì)數(shù)。是質(zhì)數(shù)。算法的基本特征算法的基本特征:明確性與有效性明確性與有效性:算法對每一個步驟都有確切的算法對每一個步驟都有確切的,能有效執(zhí)行且得到確定結(jié)果的能有效執(zhí)行且得到確定結(jié)果的,不能模棱兩可。不能模棱兩可。 有限性有限性:算法應(yīng)由有限步組成算法應(yīng)由有限步組成, 應(yīng)在有限多步內(nèi)結(jié)應(yīng)在有限多步內(nèi)結(jié)束束,并給出計算結(jié)果并給出計算結(jié)果 順序性順序性:算法從初始步驟開始算法從初始步驟開始,分為若干明確的步分為若干明確的步驟驟,每一步都只能有一個確定的繼任者每一步都只能有一個確定的繼任者,只有執(zhí)行只有執(zhí)行

4、完前一步才能進入到后一步完前一步才能進入到后一步,并且每一步都確定無并且每一步都確定無誤后誤后,才能解決問題。才能解決問題。不唯一性不唯一性:求解某一個問題的解法不一定是唯一的求解某一個問題的解法不一定是唯一的,對于同一個問題可以有不同的解法對于同一個問題可以有不同的解法算法的表示算法的表示 描述算法可以有不同的方式描述算法可以有不同的方式, ,常用的有自常用的有自然語言、程序框圖、程序設(shè)計語言等然語言、程序框圖、程序設(shè)計語言等. . 自然語言就是人們?nèi)粘Ｊ褂玫恼Z言自然語言就是人們?nèi)粘Ｊ褂玫恼Z言, ,可以是可以是漢語、英語或數(shù)學(xué)語言等漢語、英語或數(shù)學(xué)語言等. .用自然語言描述算法用自然語言描述

5、算法的優(yōu)點是通俗易懂的優(yōu)點是通俗易懂, ,當算法中的操作步驟都是順當算法中的操作步驟都是順序執(zhí)行時比較容易理解序執(zhí)行時比較容易理解. .缺點是如果算法中包含缺點是如果算法中包含判斷和轉(zhuǎn)向判斷和轉(zhuǎn)向, ,并且操作步驟較多時并且操作步驟較多時, ,就不那么直就不那么直觀清晰了觀清晰了. .(1)(1)自然語言自然語言(2)(2)程序框圖程序框圖(3)(3)程序設(shè)計語言程序設(shè)計語言1.1.21.1.2程序框圖程序框圖中講解中講解1.21.2基本算法語句基本算法語句中講解中講解 、一位商人有、一位商人有9枚銀元，其中有枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用枚略輕的是假銀元。你能用天平（不用

6、砝碼）將假銀元找出來嗎？砝碼）將假銀元找出來嗎？ 按照這樣的理解按照這樣的理解, ,我們可以設(shè)計出很多具我們可以設(shè)計出很多具體數(shù)學(xué)問題的算法體數(shù)學(xué)問題的算法. .下面看幾個例子下面看幾個例子: :第一步第一步: :將將9 9枚銀元平均分成三組枚銀元平均分成三組, ,將其中兩組將其中兩組放在天平的兩邊放在天平的兩邊. . 如果天平平衡如果天平平衡, , 則假的銀元則假的銀元必定在另外一組必定在另外一組; ;如果天平不平衡如果天平不平衡, ,則假的銀元則假的銀元必定在較輕的一組必定在較輕的一組; ;第二步第二步: :將有假銀元的一組金幣中將有假銀元的一組金幣中, ,取出兩枚銀取出兩枚銀元元, ,分

7、別放在天平的兩邊分別放在天平的兩邊. .如果天平平衡如果天平平衡, ,則假則假的銀元必定是剩余的的銀元必定是剩余的; ;如果天平不平衡如果天平不平衡, ,則假的則假的銀元必定在較輕的一邊銀元必定在較輕的一邊. . 、一個農(nóng)夫帶著一條狼、一頭山羊和一籃、一個農(nóng)夫帶著一條狼、一頭山羊和一籃蔬菜要過河蔬菜要過河,但只有一條小船但只有一條小船.乘船時乘船時,農(nóng)夫只能農(nóng)夫只能帶一樣?xùn)|西帶一樣?xùn)|西.當農(nóng)夫在場的時候當農(nóng)夫在場的時候,這三樣?xùn)|西相安這三樣?xùn)|西相安無事無事.一旦農(nóng)夫不在一旦農(nóng)夫不在,狼會吃羊狼會吃羊,羊會吃菜羊會吃菜.請設(shè)計請設(shè)計一個算法一個算法,使農(nóng)夫能安全地將這三樣?xùn)|西帶過河使農(nóng)夫能安全地

8、將這三樣?xùn)|西帶過河.第一步第一步: :農(nóng)夫帶羊過河農(nóng)夫帶羊過河; ;第二步第二步: :農(nóng)夫獨自回來農(nóng)夫獨自回來; ;第三步第三步: :農(nóng)夫帶狼過河農(nóng)夫帶狼過河; ;第四步第四步: :農(nóng)夫帶羊回來農(nóng)夫帶羊回來; ;第五步第五步: :農(nóng)夫帶蔬菜過河農(nóng)夫帶蔬菜過河; ;第六步第六步: :農(nóng)夫獨自回來農(nóng)夫獨自回來; ;第七步第七步: :農(nóng)夫帶羊過河農(nóng)夫帶羊過河. . 、給出求、給出求1+2+3+4+5+6的一個算法的一個算法.解法解法1.1.按照逐一相加的程序進行按照逐一相加的程序進行. .第一步第一步:計算計算1+2,得得3;第二步第二步:將第一步中的運算結(jié)果將第一步中的運算結(jié)果3與與3相加得相加得

9、6;第三步第三步:將第二步中的運算結(jié)果將第二步中的運算結(jié)果6與與4相加得相加得10;第四步第四步:將第三步中的運算結(jié)果將第三步中的運算結(jié)果10與與5相加得相加得15;第五步第五步:將第四步中的運算結(jié)果將第四步中的運算結(jié)果15與與6相加得相加得21.解法解法2.2.可以運用下面公式直接計算可以運用下面公式直接計算. .(1)12342n nn 第一步第一步: :取取 n = =6; ;第二步第二步: :計算計算 ; ;2)1( nn第三步第三步: :輸出計算結(jié)果輸出計算結(jié)果. .點評點評: :解法解法1 1繁瑣繁瑣, ,步驟較多步驟較多; ; 解法解法2 2簡單，步簡單，步驟較少驟較少. . 找

10、出好的算法是我們的追求目標找出好的算法是我們的追求目標. .例例2.2.寫出用寫出用“二分法二分法”求方程求方程 x2-2=0（x0） 的近似解的算法的近似解的算法. .第一步，令第一步，令f(x)=x2-2，給定精確度，給定精確度d;第二步，確定區(qū)間第二步，確定區(qū)間a，b，滿足，滿足f(a)f(b)0;2ab 第三步，取區(qū)間中點第三步，取區(qū)間中點m= ;第四步，若第四步，若f(a)f(m) 2 2）是否為質(zhì)數(shù)）是否為質(zhì)數(shù)”的的算法步驟如何？算法步驟如何？第一步第一步，給定一個大于，給定一個大于2 2的整數(shù)的整數(shù)n n； 第二步第二步，令，令i=2i=2； 第三步第三步，用，用i i除除n n

11、，得到余數(shù)，得到余數(shù)r r； 第四步第四步，判斷，判斷“r=0”r=0”是否成立是否成立. .若是，則若是，則n n 不是質(zhì)數(shù)，結(jié)束算法；否則，將不是質(zhì)數(shù)，結(jié)束算法；否則，將i i 的值增加的值增加1 1，仍用，仍用i i表示；表示； 第五步第五步，判斷，判斷“i i(n-1)”(n-1)”是否成立，若是，是否成立，若是， 則則n n是質(zhì)數(shù)，結(jié)束算法；否則，返回是質(zhì)數(shù)，結(jié)束算法；否則，返回 第三步第三步. . Copyright 2004-2009 版權(quán)所有 盜版必究思考思考2:2:我們將上述算法用下面的圖形表示：我們將上述算法用下面的圖形表示：開始開始r=0？輸出輸出“n是質(zhì)數(shù)是質(zhì)數(shù)”輸出輸

12、出“n不是質(zhì)數(shù)不是質(zhì)數(shù)”求求n除以除以i的余數(shù)的余數(shù)i=2輸入輸入ni的值增加的值增加1，仍用，仍用i表示表示i in-1n-1或或r=0r=0？是是是是結(jié)束結(jié)束否否否否輸入輸入n i=2 =2 r=0?是是n不是質(zhì)數(shù)不是質(zhì)數(shù)n是質(zhì)數(shù)是質(zhì)數(shù)否否求求n除以除以i的余數(shù)的余數(shù)ri=i+1 +1 in-1或或r=0?否否是是(1)(1)(2)(2)(3)(3)問問: :這些分解框圖各有什么特點這些分解框圖各有什么特點? ?順序順序結(jié)構(gòu)結(jié)構(gòu)條件條件結(jié)構(gòu)結(jié)構(gòu)循環(huán)循環(huán)結(jié)構(gòu)結(jié)構(gòu)算法的三種基本邏輯結(jié)構(gòu)解：求面積的算法解：求面積的算法:第一步第一步:輸入三角形三條邊的邊長輸入三角形三條邊的邊長a,b,c第二步第

13、二步:計算計算第三步第三步:計算計算第四步第四步:輸出三角形的面積輸出三角形的面積S()()()Sp papbpc圖示圖示:2abcp2abcp()()()Sp papbpc輸出S例例3、已知一個三角形的、已知一個三角形的三邊邊長分別是三邊邊長分別是a,b,c,利利用海倫用海倫-秦九韶面積公式秦九韶面積公式,求三角形的面積求三角形的面積.順序結(jié)構(gòu)順序結(jié)構(gòu)是任何一個算法都不可缺少的基本結(jié)是任何一個算法都不可缺少的基本結(jié)構(gòu)，它由若干個構(gòu)，它由若干個依次執(zhí)行依次執(zhí)行的處理步驟組成。的處理步驟組成。開始開始結(jié)束結(jié)束輸入a,b,cCopyright 2004-2009 版權(quán)所有 盜版必究 例例1 1 一

14、個籠子里裝有雞和兔共一個籠子里裝有雞和兔共m m只，且只，且雞和兔共雞和兔共n n只腳，設(shè)計一個計算雞和兔各有多只腳，設(shè)計一個計算雞和兔各有多少只的算法，并畫出程序框圖表示少只的算法，并畫出程序框圖表示. .理論遷移理論遷移算法分析：算法分析： 第一步，輸入第一步，輸入m m，n.n.第二步，計算雞的只數(shù)第二步，計算雞的只數(shù) . .42mnx-=第三步，計算兔的只數(shù)第三步，計算兔的只數(shù)y=m-x.y=m-x.第四步，輸出第四步，輸出x x，y.y.Copyright 2004-2009 版權(quán)所有 盜版必究開始開始結(jié)束結(jié)束輸出輸出x，y輸入輸入m，n42mnx-=y y= m-xm-x程序框圖：

15、程序框圖： Copyright 2004-2009 版權(quán)所有 盜版必究順序結(jié)構(gòu)的程序框圖的基本特征：順序結(jié)構(gòu)的程序框圖的基本特征：小結(jié)作業(yè)小結(jié)作業(yè)（2 2）各程序框從上到下用流程線依次）各程序框從上到下用流程線依次連接連接. .（1 1）必須有兩個起止框，穿插輸入、輸）必須有兩個起止框，穿插輸入、輸出框和處理框，沒有判斷框出框和處理框，沒有判斷框. .（3 3）處理框按計算機執(zhí)行順序沿流程線）處理框按計算機執(zhí)行順序沿流程線依次排列依次排列. .條件結(jié)構(gòu)條件結(jié)構(gòu):在算法流程中需根據(jù)條件是否成立有在算法流程中需根據(jù)條件是否成立有不同的流向的結(jié)構(gòu)不同的流向的結(jié)構(gòu).雙分支的條件結(jié)構(gòu)非對稱的條件結(jié)構(gòu)滿足

16、條件？滿足條件？步驟步驟A步驟步驟B滿足條件？滿足條件？步驟步驟ANNYY否否圖示圖示:開始開始存在這樣存在這樣的三角形的三角形結(jié)束結(jié)束解：判斷三角形存在的算法解：判斷三角形存在的算法:第一步第一步:輸入正實數(shù)輸入正實數(shù)a,b,c第二步第二步:判斷判斷a+bc,b+ca,c+ab是否是否都成立都成立,若是若是,則存在這樣則存在這樣的三角形的三角形,若不是若不是,則不存則不存在這樣的三角形在這樣的三角形.a+bc,b+ca,c+ab是否同是否同時成立時成立?輸入輸入a,b,c是是不存在這樣不存在這樣的三角形的三角形例例4、任意給定、任意給定3個正實個正實數(shù)數(shù),判斷以這判斷以這3個數(shù)為三邊個數(shù)為三

17、邊邊長的三角形是否存在邊長的三角形是否存在.例例5.5.設(shè)計算法設(shè)計算法, ,求一元二求一元二次方程次方程axax2 2+bx+c=0,+bx+c=0,畫出相畫出相應(yīng)的流程圖應(yīng)的流程圖 解決這一問題的算法步驟如下:第一步:輸入3個系數(shù)a,b,c第二步:計算=b2-4ac第三步:判斷0是否成立.若是,則計算p=- ,q= ;否則, 輸出“方程沒有實數(shù)根”,結(jié)束算法.第四步:判斷=0是否成立.若是,則輸出x1=x2=p;否則,計算x1=p+q, x2=p-q,并輸出x1,x2b2a2a開始輸入a,b,c=b2-4ac0? P=- q=0?b2a2ax1=p+qx2=p-q輸出x1,x2結(jié)束輸出“方

18、程沒有實數(shù)根”輸出p否是是否例例5.5.設(shè)計算法設(shè)計算法, ,求一元二求一元二次方程次方程axax2 2+bx+c=0,+bx+c=0,畫出相畫出相應(yīng)的流程圖應(yīng)的流程圖 解決這一問題的算法步驟如下:第一步:輸入3個系數(shù)a,b,c第二步:計算=b2-4ac第三步:判斷0，則原方程無實數(shù)解；否則（0）x1 = x2=第四步:輸出x1,x2或無實數(shù)解信息-b+2a-b-2a開始輸入a,b,c=b2-4ac100?是是輸出輸出S結(jié)束結(jié)束否否直到直到型循型循環(huán)結(jié)環(huán)結(jié)構(gòu)構(gòu)開始開始i=1S=0i100?是是S=S+ii=i+1否否輸出輸出S結(jié)束結(jié)束當型循環(huán)當型循環(huán)結(jié)構(gòu)結(jié)構(gòu) 直到型循環(huán)直到型循環(huán)在執(zhí)行了在執(zhí)行

19、了一次循環(huán)體之后一次循環(huán)體之后,對控對控制循環(huán)條件進行判斷制循環(huán)條件進行判斷,當條件不滿足時執(zhí)行當條件不滿足時執(zhí)行循環(huán)體循環(huán)體,滿足則停滿足則停止止.(反復(fù)執(zhí)行循環(huán)體反復(fù)執(zhí)行循環(huán)體,直到條件滿足直到條件滿足)開始開始i=1S=0S=S+ii=i+1i100?是是輸出輸出S結(jié)束結(jié)束否否直到直到型循型循環(huán)結(jié)環(huán)結(jié)構(gòu)構(gòu)說明說明:(1)一般地一般地,循環(huán)結(jié)構(gòu)中都有循環(huán)結(jié)構(gòu)中都有一個一個計數(shù)變量計數(shù)變量和和累加變量累加變量.計數(shù)計數(shù)變量用于記錄循環(huán)次數(shù)變量用于記錄循環(huán)次數(shù),同時它同時它的取值還用于判斷循環(huán)是否終的取值還用于判斷循環(huán)是否終止止,累加變量用于輸出結(jié)果累加變量用于輸出結(jié)果.累加累加變量和計數(shù)變量

20、一般是同步執(zhí)變量和計數(shù)變量一般是同步執(zhí)行的行的,累加一次累加一次,記數(shù)一次記數(shù)一次. 當型循環(huán)當型循環(huán)在每次執(zhí)在每次執(zhí)行循環(huán)體前對循環(huán)行循環(huán)體前對循環(huán)條件進行判斷條件進行判斷,當當條件滿足時執(zhí)行循條件滿足時執(zhí)行循環(huán)體環(huán)體,不滿足則停不滿足則停止止;(當條件滿足時當條件滿足時反復(fù)執(zhí)行循環(huán)體反復(fù)執(zhí)行循環(huán)體)開始開始i=1S=0i100?是是S=S+ii=i+1否否輸出輸出S結(jié)束結(jié)束當型循環(huán)當型循環(huán)結(jié)構(gòu)結(jié)構(gòu)例例2. 畫出計算畫出計算 值的一個算法值的一個算法程序框圖程序框圖.10131211開始開始輸出輸出s結(jié)束結(jié)束i10s=s+1/ii=i+1i=1s=0是是否否例例3. 設(shè)計一個求滿足設(shè)計一個求

21、滿足“1+3+5+i2008” 的的i的最小值的算法，的最小值的算法，并畫出程序框圖并畫出程序框圖解解:在這個問題中，需要累加多少次，事先在這個問題中，需要累加多少次，事先并不知道，為此我們采用并不知道，為此我們采用直到型直到型的循環(huán)的循環(huán). 例例4. 畫出對畫出對x=1，2，3，10，求求x2的算法的程序的算法的程序框圖框圖.開始開始結(jié)束結(jié)束x10y=x2x=x+1x=1是是否否輸出輸出y例例5、某工廠、某工廠2005年生產(chǎn)總值年生產(chǎn)總值200萬元，技術(shù)革新后萬元，技術(shù)革新后預(yù)計以后每年的年生產(chǎn)總值比上一年增長預(yù)計以后每年的年生產(chǎn)總值比上一年增長5%，設(shè)計，設(shè)計一個程序框圖，輸出預(yù)計年生產(chǎn)總

22、值超過一個程序框圖，輸出預(yù)計年生產(chǎn)總值超過300萬元萬元的最早年份的最早年份。（1）確定循環(huán)體）確定循環(huán)體 t=0.05a設(shè)設(shè)a為某年的年生產(chǎn)總值，為某年的年生產(chǎn)總值，t為年生產(chǎn)總值的年為年生產(chǎn)總值的年增長量，增長量，n為年份，則為年份，則循環(huán)體循環(huán)體為：為：a=a+tn=n+1(2)初始變化量：初始變化量：2005年生產(chǎn)總值看成計年生產(chǎn)總值看成計算起點，則算起點，則n=2005，a=200（3）設(shè)定循環(huán)控制條件：）設(shè)定循環(huán)控制條件：當年生產(chǎn)總值超過當年生產(chǎn)總值超過300萬元時終止循環(huán)，可萬元時終止循環(huán)，可以通過判斷以通過判斷“a300”是否成立來控制循環(huán)是否成立來控制循環(huán)n = 2005開始開始a3