算法概念 演示文稿

1、1.1.1 算法的概念,思考,解二元一次方程組：,1.-2，得：,5y3,2. 解的,3.將 代入.得,解,寫出一般二元一次方程組的解法步驟.,第一步,第二步,解（3）得,第四步,解（4）得,第三步,第五步,得到方程組的解為,按照上面步驟求解?？梢缘玫蕉淮畏匠探M的一般算法，我們可以根據(jù)這一算法編制計(jì)算機(jī)程序，讓計(jì)算機(jī)自動(dòng)來完成二元一次方程組的解,這些步驟就構(gòu)成了解二元一次方程組的算法,我們可以根據(jù)這一算法編制計(jì)算機(jī)程序,讓計(jì)算機(jī)來解二元一次方程組.,算法的概念與特征,算法(algorithm)這個(gè)詞出現(xiàn)于12世紀(jì),指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程.,在數(shù)學(xué)上,現(xiàn)代意義上的“算法”通常是

2、指可以用計(jì)算機(jī)來解決的某一類問題的程序或步驟,這些程序或步驟必須是明確和有效的,而且能夠在有限步之內(nèi)完成.,說明: (1)事實(shí)上算法并沒有精確化的定義. (2)算法雖然沒有一個(gè)明確的定義,但其特點(diǎn)是鮮明的,不僅要注意算法的程序性、有限性、構(gòu)造性、精確性的特點(diǎn)，還應(yīng)該充分理解算法問題的指向性，即算法往往指向解決某一類問題，泛泛地談算法是沒有意義的。,應(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

3、不能整除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ù).,例2:任意給定一個(gè)大于1的整數(shù)n,試設(shè)計(jì)一個(gè)程序或步驟對n是否為

4、質(zhì)數(shù)做出判定.,分析:請回顧這個(gè)問題的解題過程.,算法分析:,第一步:判斷n是否等于2.,若n=2,則n是質(zhì)數(shù);,若n2,則執(zhí)行第二步.,第二步:依次檢驗(yàn)2(n-1)這些整數(shù)是不是n的因素,即是不是整除n的數(shù).若有這樣的數(shù),則n不是質(zhì)數(shù);若沒有這樣的數(shù),則n是質(zhì)數(shù).,說明:用語言描述一個(gè)算法,最便捷的方式就是按解決問題的步驟進(jìn)行描述.每一步做一件事情.,若是,則m 為所求;,例3:用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近似根的算法.,算法分析:,設(shè)所求近似根與精確解的差的絕對值不超過=0.005.,第一步:令f(x)=x2-2.,因?yàn)閒(1)0,所以設(shè)a=1,b=2.,第二步:令,判斷f(m)是

5、否為0.,第四步:判斷|a-b|是否成立?若是,則a或b為滿足條件的近似根;若否,則返回第二步.,點(diǎn)評(píng): (1)上述算法也是求 的近似值的算法.,(2)與一般的解決問題的過程比較,算法有以下特征: 設(shè)計(jì)一個(gè)具體問題的算法時(shí),與過去熟悉地解數(shù)學(xué)題的過程有直接的聯(lián)系,但這個(gè)過程必須被分解成若干個(gè)明確的步驟,而且這些步驟必須是有效的. 算法要“面面俱到”,不能省略任何一個(gè)細(xì)小的步驟,只有這樣,才能在人設(shè)計(jì)出算法后,把具體的執(zhí)行過程交給計(jì)算機(jī)完成.,計(jì)算機(jī)解決任何問題都要依賴于算法.只有將解決問題的過程分解為若干個(gè)明確的步驟,即算法,并用計(jì)算機(jī)能夠接受的“語言”準(zhǔn)確地描述出來,計(jì)算機(jī)才能夠解決問題.,

6、鞏固概念,【1】寫出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步,計(jì)算=b2-4ac.,第二步,如果0,則原方程無實(shí)數(shù)解 ;否則(0)時(shí)，,第三步:輸出x1, x2或無實(shí)數(shù)解的信息.,、給出求1+2+3+4+5+6的一個(gè)算法.,解法1.按照逐一相加的程序進(jìn)行.,第一步:計(jì)算1+2,得3;,第二步:將第一步中的運(yùn)算結(jié)果3與3相加得6;,第三步:將第二步中的運(yùn)算結(jié)果6與4相加得10;,第四步:將第三步中的運(yùn)算結(jié)果10與5相加得15;,第五步:將第四步中的運(yùn)算結(jié)果15與6相加得21.,3,解法2.可以運(yùn)用下面公式直接計(jì)算.,第一步:取 n =6;,第二步:計(jì)算 ;,第三步:輸出計(jì)算結(jié)果

7、.,點(diǎn)評(píng):解法1繁瑣,步驟較多; 解法2簡單，步驟較少. 找出好的算法是我們的追求目標(biāo).,例、給出求1+2+3+4+5的一個(gè)算法。,算法1：,S1：計(jì)算1+2得到3；,S2：將第一步中的運(yùn)算結(jié)果3與3相加得到6；,S3：將第二步中的運(yùn)算結(jié)果6與4相加得到10；,S4：將第三步中的運(yùn)算結(jié)果10與5相加得到15；,三、數(shù)學(xué)運(yùn)用,1下面的四種敘述不能稱為算法的是（ ） （A）廣播的廣播操圖解 （B）歌曲的歌譜 （C）做飯用米 （D）做米飯需要刷鍋、淘米、添水、加熱這些步驟,練習(xí)題,C,2下列關(guān)于算法的說法正確的是（ ） （A）某算法可以無止境地運(yùn)算下去 （B）一個(gè)問題的算法步驟可以是可逆的 （C）完

8、成一件事情的算法有且只有一種 （D）設(shè)計(jì)算法要本著簡單、方便、可操作的原則,D,3下列關(guān)于算法的說法中，正確的是（ ）. A. 算法就是某個(gè)問題的解題過程 B. 算法執(zhí)行后可以不產(chǎn)生確定的結(jié)果 C. 解決某類問題的算法不是惟一的 D. 算法可以無限地操作下去不停止,C,4下列運(yùn)算中不屬于我們所討論算法范疇的是（ ）. A. 已知圓的半徑求圓的面積 B. 從一副撲克牌隨意抽取3張撲克牌抽到24點(diǎn)的可能性 C. 已知坐標(biāo)平面內(nèi)的兩點(diǎn)求直線的方程 D. 加減乘除運(yùn)算法則,B,5下列語句表達(dá)中是算法的有（ ）. 從濟(jì)南到巴黎可以先乘火車到北京再坐飛機(jī)抵達(dá)； 利用公式 S = ah2 計(jì)算底為1高為2的

9、三角形的面積； x2x +4； 求M(1，2)與N(3，5)兩點(diǎn)連線的方程可先求MN的斜率再利用點(diǎn)斜式方程求得 A. 1 個(gè) B. 2 個(gè) C. 3 個(gè) D. 4 個(gè),C,6寫出求123100的一個(gè)算法.可以運(yùn)用公式123n 直接計(jì)算. 第一步； 第二步； 第三步輸出運(yùn)算結(jié)果.,取n100,計(jì)算,7已知一個(gè)學(xué)生的語文成績?yōu)?9，數(shù)學(xué)成績?yōu)?6，外語成績?yōu)?9，求他的總分和平均成績的一個(gè)算法為： 第一步取A89，B96，C99; 第二步； 第三步； 第四步輸出D，E.,計(jì)算總分DA+B+C,計(jì)算平均成績E,1.任意給定一個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法求以這個(gè)數(shù)為半徑的圓的面積.,第一步:輸入任意一個(gè)正實(shí)數(shù)r；,第二步:計(jì)算圓的面積: S=r2;,第三步:輸出圓的面積S.,課堂練習(xí),2.任意給定一個(gè)大于1 的正整數(shù)n,設(shè)計(jì)一個(gè)算法求出n的所有因數(shù).,第一步：依次以2(n-1)為除數(shù)去除n,檢查余數(shù)是否為0,若是,則