1、1.1.1算法的概念,隨著科學(xué)技術(shù)的日新月異,算法學(xué)也得到了前所未有的發(fā)展,現(xiàn)在已經(jīng)發(fā)展到了各個(gè)領(lǐng)域.有遺傳算法,排序算法,加密算法,蟻群算法等,與生物學(xué),計(jì)算機(jī)科學(xué)等有著很廣泛的聯(lián)系,尤其是在現(xiàn)在的航空航天中,更是有著更廣泛的應(yīng)用. 很多復(fù)雜的運(yùn)算都是借助計(jì)算機(jī)和算法來完成的,在高端科學(xué)技術(shù)中有著很重要的地位.,把大象放進(jìn)冰箱里需要幾步？,1、把冰箱門打開 2、把大象裝進(jìn)去 3、把冰箱門關(guān)上,2000春晚小品鐘點(diǎn)工,假如你參加一個(gè)猜商品價(jià)格的活動(dòng),只要在規(guī)定時(shí)間內(nèi)大體猜出某商品的價(jià)格,就可獲得該件商品（每猜一次，主持人會(huì)提醒你報(bào)價(jià)是高了還是低了）.現(xiàn)有一商品,價(jià)格在01400元之間,采取怎樣

2、的策略才能在較短時(shí)間內(nèi)說出大體答案呢?,第一步:報(bào)“700”；,第二步:若主持人說高了(說明答案在0700之間),就報(bào)“350”,否則(答數(shù)在350700之間)報(bào)“525”；,第三步:重復(fù)第二步的報(bào)數(shù)方法取中間數(shù),直至得到大體答案., 解決實(shí)際問題需要程序和步驟，解決數(shù)學(xué)問題同樣需要程序和步驟,第一步:2得: 5x=1 ,第二步: 解得:,第三步:-2得: 5y=3 ,第四步: 解得:,第五步:得到方程組的解為,你能寫出與教材解法不同的求解步驟嗎？,你能寫出求一般二元一次方程組的步驟嗎？,第三步:,第四步:解（4）得,第五步:得到方程組的解為,第一步:,第二步:解（3）得,一般地, 按照一定規(guī)

3、則解決某一類問題的明確和有限的步驟稱為算法。,從廣義的角度來看,并不是只有“計(jì)算”的問題才有算法,日常生活中處處都有.如樂譜是樂隊(duì)演奏的算法,菜譜是做菜肴的算法,棋譜是下棋的算法.,它是解決某一類問題的程序或步驟；這些程序或步驟必須是明確有效的，而且能夠在有限步之內(nèi)完成；算法的設(shè)計(jì)盡量簡(jiǎn)單、步驟盡量少。,一.算法的概念,二.算法的基本特征:,明確性:算法中的每一步都應(yīng)該是確定的,并且能有效地執(zhí)行且得到確定的結(jié)果.,有限性:一個(gè)算法的步驟是有限的，它應(yīng)在有限步操作之后停止，而不能是無限的,程序性:算法從初始步驟開始，分為若干明確的步驟，每一個(gè)步驟只能有一個(gè)確定的后續(xù)步驟，只有執(zhí)行完前一步才能進(jìn)行

4、下一步，并且每一步都要準(zhǔn)確無誤.,1下列關(guān)于算法的說法正確的是（ ） （A）某算法可以無止境地運(yùn)算下去 （B）一個(gè)問題的算法步驟可以是可逆的 （C）完成一件事情的算法有且只有一種 （D）設(shè)計(jì)算法要本著簡(jiǎn)單、方便、可操作的原則,D,2下列運(yùn)算中不屬于我們所討論算法范疇的是（ ）. A. 已知圓的半徑求圓的面積 B. 從一副撲克牌隨意抽取3張撲克牌抽到 24點(diǎn)的可能性 C. 已知坐標(biāo)平面內(nèi)的兩點(diǎn)求直線的方程 D. 加減乘除運(yùn)算法則,B,3.有人對(duì)歌德巴赫猜想“任何大于4的偶數(shù)都能寫成兩個(gè)奇質(zhì)數(shù)之和”設(shè)計(jì)了如下操作步驟：,第一步：檢驗(yàn)6=3+3,第二步：檢驗(yàn)8=3+5,第三步：檢驗(yàn)10=5+5,。,

5、利用計(jì)算機(jī)不斷地進(jìn)行下去！,三.算法的表示方式：,自然語言就是人們?nèi)粘Ｊ褂玫恼Z言,可以是漢語、英語或數(shù)學(xué)語言等.用自然語言描述算法的優(yōu)點(diǎn)是通俗易懂,當(dāng)算法中的操作步驟都是順序執(zhí)行時(shí)比較容易理解.缺點(diǎn)是如果算法中包含判斷和循環(huán),并且操作步驟較多時(shí),就不那么直觀清晰了.,(1)自然語言（算法語言）,(2)程序框圖,(3)程序設(shè)計(jì)語言,1.1.2程序框圖中講解,1.2基本算法語句中講解,第一步：用2除7，得到余數(shù)1,所以2不能整除7.,第二步：用3除7，得到余數(shù)1,所以3不能整除7.,例1:（1）設(shè)計(jì)一個(gè)算法，判斷7是否為質(zhì)數(shù)？,第三步：用4除7，得到余數(shù)3,所以4不能整除7.,第四步：用5除7，得

6、到余數(shù)2,所以5不能整除7.,第五步：用6除7，得到余數(shù)1,所以6不能整除7.,因此，7是質(zhì)數(shù).,例1:（2）設(shè)計(jì)一個(gè)算法，判斷35是否為質(zhì)數(shù)？,第一步：用2除35，得到余數(shù)1,所以2不能整除35.,第二步：用3除35，得到余數(shù)2,所以3不能整除35.,第三步：用4除35，得到余數(shù)3,所以4不能整除35.,第四步：用5除35，得到余數(shù)0,所以5能整除35.,因此，35不是質(zhì)數(shù).,第一步：給定一個(gè)大于2的整數(shù)n；,第二步：令i=2；,第三步：用i除n，得到余數(shù)r；,第五步：判斷“i(n-1)”是否成立.若是，則n是質(zhì)數(shù),結(jié)束算法；否則，返回第三步.,第四步：判斷“r=0”是否成立.若是，則n 不

7、是質(zhì)數(shù),結(jié)束算法；否則，將i的值增加1，仍用i表示.,你能寫出“判斷整數(shù)n(n2)是否為質(zhì)數(shù)”的算法嗎？,教材P5:練習(xí)1.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.,第一步：,第二步：,第三步：,給定一個(gè)正實(shí)數(shù)r；,計(jì)算S=r2;,得到圓的面積S.,教材P5：練習(xí)2.任意給定一個(gè)大于1的正整數(shù)n，設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).,第一步：,第二步：,第三步：,依次用2 （n 1）除 n ，,檢查余數(shù)是否為0；,若是，則是 n 的因數(shù)；,若不是，則不是 n 的因數(shù)；,在 n 的因數(shù)中加入 1 和 n；,輸出n的所有因數(shù).,練習(xí)3:寫出過P(a1,b1)、Q(a2,b2)兩點(diǎn)直線

8、斜率的算法：,第一步：,第二步：,第三步：,取出橫坐標(biāo)a1，a2，縱坐標(biāo)b1，b2；,若a1=a2,輸出斜率不存在；,若a1a2,計(jì)算,第四步：,輸出結(jié)果。,練習(xí)4.寫出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步:計(jì)算=b2-4ac.,第三步:輸出x1, x2或無實(shí)數(shù)解的信息.,第二步:如果0,則原方程無實(shí)數(shù)解 ; 否則(0)時(shí)，,練習(xí)5：寫出求1+2+3+4+5+6的一個(gè)算法。,解：算法1： 第一步：計(jì)算1+2得到3； 第二步：將第一步中的運(yùn)算結(jié)果3與3相加得到6 第三步：將第二步中的運(yùn)算結(jié)果6與4相加得到10 第四步：將第三步中的運(yùn)算結(jié)果10與5相加得到15 第五步：將第四

9、步中的運(yùn)算結(jié)果15與6相加得到21,算法2： 第一步：取n=6； 第二步：計(jì)算 第三步：輸出運(yùn)算結(jié)果。,算法3： 第一步： 將原式變形(1+6)+(2+5)+(3+4)=37； 第二步： 計(jì)算37； 第三步：輸出運(yùn)算結(jié)果。,例2.用二分法設(shè)計(jì)一個(gè)求方程 x2-2=0（x0） 的近似根的算法.(精確度為0.005),第一步：,第二步：,第三步：,第四步：,第五步：,令 ，,給定精確度d.,確定區(qū)間a，b，,滿足f(a)f(b)0.,取區(qū)間中點(diǎn),若f(a)f(m)0,則含零點(diǎn)的區(qū)間為,否則，含零點(diǎn)的區(qū)間為,將新得到的含零點(diǎn)的區(qū)間仍記為a,b;,判斷|a-b|d是否成立或f(m)是否等于0.,若是，

10、則m是方程的近似解；,否則，返回,a,m,m，b.,第三步.,分析問題,對(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)近似值的方法叫做二分法.,二分法:,對(duì)于方程 ,給定d=0.005.,此步驟也是求的近似值的一個(gè)算法.,練習(xí)6:為了加強(qiáng)居民的節(jié)水意識(shí),某市制訂了以下生活用水收費(fèi)標(biāo)準(zhǔn):每戶每月用水未超過7m3時(shí),每立方米收費(fèi)1.0元,并加收0.2元的城市污水處理費(fèi);超過7m3的部分,每立方米收費(fèi)1.5元,并加收0.4元的城市污水處理費(fèi),請(qǐng)你寫出某戶居民每月應(yīng)交納的水費(fèi)y(元)與用水量x(m3)之間的函數(shù)關(guān)系,然后設(shè)計(jì)一個(gè)求該函數(shù)值的算法.,解:y與x之間的函數(shù)關(guān)系為:,(當(dāng)0 x7時(shí)) (當(dāng)x7時(shí)),解:y與x之間的函數(shù)關(guān)系為:,(當(dāng)0 x7時(shí)) (當(dāng)x7時(shí)),求該函數(shù)值的算法分析:,第一步:輸入每月用水量x; 第二步:判斷x是否不超過7.若是,則y=1.2x;若否,則y=1.9x-4.9. 第三步:輸出應(yīng)交納的水費(fèi)y.,小結(jié)：,算法的特征是什么？,明確性,程序性,有限性,算法的概念：算法通常指可以用來解決的某 一類問題的步驟或程序，這些步驟或程序必須