高二數(shù)學(xué)算法初步.ppt

《高二數(shù)學(xué)算法初步.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《高二數(shù)學(xué)算法初步.ppt（41頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1、算法初步,目標(biāo)：了解算法的基本思想；培養(yǎng)使用算法的思想進(jìn)行思考與表達(dá)解決問(wèn)題的能力。,內(nèi)容： 1、算法的含義。 2、程序框圖。 3、實(shí)現(xiàn)算法的程序。 4、典型的算法介紹。,1、算法的含義,算法：用計(jì)算機(jī)解決問(wèn)題的某一類問(wèn)題的程序或步驟，且在有限步內(nèi)完成。,理解： 1、算法是一種解決問(wèn)題的過(guò)程和步驟。 2、算法是解決某一類問(wèn)題的。 3、算法具有某種意義上的通用性和普適性。 4、算法是與計(jì)算機(jī)對(duì)話的一種思維方式。 5、算法必須有限步完成。,舉例：求一元二次方程ax2+bx+c=0的實(shí)根。用算法的思想怎樣來(lái)求？(全解p7例三),1、算法的含義,因式分解的方法行不行？,不具有通用性！,解：,Ste

2、p1：確定a,b,c Step2：計(jì)算判別式 Step3：判別的符號(hào) Step4：三種結(jié)果 1）無(wú)實(shí)根； 2）有兩個(gè)相等實(shí)根； 3）有兩個(gè)不等實(shí)根。 Step5：輸出實(shí)根,1、算法的含義,例1 任意給定一個(gè)大于1的整數(shù)n，試設(shè)計(jì)一個(gè)算法步驟對(duì)n是否為質(zhì)數(shù)做出判斷。,Step1：輸入n，如果n=2，則n是質(zhì)數(shù)；若n2，執(zhí)行第二步； Step2：令flag=1，標(biāo)記flag區(qū)分是否存在整除的情況； Step3：依次從2n-1循環(huán)檢驗(yàn)是否為n的因數(shù)，在某一步，若是n的因數(shù)，則令flag=0，中途直接停止即可，并作出判斷，n不是質(zhì)數(shù)； Step4：如果循環(huán)檢查完2n-1中的每一個(gè)數(shù)，flag=1仍然成

3、立，則可以做出判斷， n是質(zhì)數(shù)。,總體思路：如果n大于2，將n依次除以2n-1，檢查每一次是否整除，若某一次整除，則n不是質(zhì)數(shù)，否則，全部檢查完，仍沒(méi)有整除的情況，則n是質(zhì)數(shù)；n=2，直接判斷是質(zhì)數(shù)。,1、算法的含義,例1、詳細(xì)步驟：,Step1：輸入n，如果n=2，則n是質(zhì)數(shù)，結(jié)束；若n2，執(zhí)行第二步； Step2：令flag=1； Step3：1）d=2； 2）d整除n ? 21）是，flag=0； 22）否，d自增加1（d=d+1）； 3）d<=n-1且flag=1 ？ 31）是，重新判斷第2）步（即轉(zhuǎn)2）步）； 32）否，下一步； S

4、tep4：flag=1 ? 41）是， n是質(zhì)數(shù)； 42）否， n不是質(zhì)數(shù)。,框圖,1、算法的含義,例2、 用二分法求方程x2-2=0的近似根的算法。,Step1：令f (x)=x2-2，取區(qū)間端點(diǎn)為x1=1,x2=2，則f (x1)0； Step2：令m=(x1+x2)/2，判斷f (m) =0 ? 若是，m即為所求，停止； Step3：否則，判斷f (x1) f (m) 0 ? 若成立，令x1= m ； 否則，令x2= m； Step4：判斷| x1-x2 |

5、的任意點(diǎn)均為滿足條件的近似根； 否則，返回Step2重復(fù)進(jìn)行。,總體思路：設(shè)定一個(gè)區(qū)間，包含方程的根，每次取區(qū)間的中點(diǎn)，改變?cè)瓍^(qū)間的一個(gè)端點(diǎn)，以縮小區(qū)間，但始終保持該區(qū)間包含方程的根，最后使區(qū)間縮小到非常小的程度，達(dá)到近似根的精度要求，則區(qū)間內(nèi)任意點(diǎn)都可以作為方程的根。,框圖,1、算法的含義,,,,,,,,f(x)=x2-2,x2=2,x1=1,1.5,1.25,1.375,1、算法的含義,小結(jié)：算法是“傻瓜式”的，即算法要“面面俱到”，不能省略任何一個(gè)細(xì)小的步驟，只有這樣，才能在設(shè)計(jì)出算法后，把具體的執(zhí)行過(guò)程交給計(jì)算機(jī)完成。 但，算法有“好”與“不好” 之分，“好”的算法可以節(jié)約計(jì)算機(jī)

6、的執(zhí)行時(shí)間，“不好” 的算法占用大量的計(jì)算機(jī)時(shí)間。,1、算法的含義,例如：枚舉法。 x1,x2,x3,x4,x5為0-999之間的整數(shù)，求滿足x1+x2+x3+x4+x5=2050的條件下，乘積 x1x2x3x4x5 達(dá)到最大。 解：計(jì)算機(jī)枚舉出所有可能的組合 (1000)5=1015，現(xiàn)有計(jì)算機(jī)計(jì)算約為200多年。 而實(shí)際上，可以找到算法算出，當(dāng)x1=x2=x3=x4=x5=410時(shí)，x1x2x3x4x5 達(dá)到最大。,2、程序框圖,框圖：又稱流程圖，是表達(dá)算法的重要工具，借助框圖，人們可以清晰而條理地表達(dá)思想。,理解： 1、框圖的表現(xiàn)形式：程序框和流程線的組合形式。 2、程序框和流程線是一

7、種形式規(guī)范，好的形式規(guī)范，是交流重要前提。 3、通過(guò)框圖將解題思想表達(dá)為計(jì)算機(jī)的“思維”習(xí)慣。,例1的框圖,返回,例2的框圖,返回,2、程序框圖,通過(guò)框圖，算法的邏輯結(jié)構(gòu)表現(xiàn)得非常清楚，通常有三種結(jié)構(gòu)： 1.順序結(jié)構(gòu)； 2.條件（選擇）結(jié)構(gòu)； 3.循環(huán)結(jié)構(gòu)。,2、程序框圖,（1）順序結(jié)構(gòu) 例3:已知三角形的三邊邊長(zhǎng)為2,3,4,計(jì)算面積。,思路： 1、秦九韶面積公式：S=p(p-a)(p-b)(p-c)1/2 2、其中，p=(a+b+c)/2,解決： 1、輸入邊長(zhǎng)a,b,c，計(jì)算p的值。 2、按公式計(jì)算S，輸出S。,2、程序框圖,解：,2、程序框圖,（2）條件結(jié)構(gòu) 例4:任意給定3個(gè)正實(shí)數(shù)，判

8、斷分別以這些實(shí)數(shù)為邊長(zhǎng)的三角形是否存在。,思路： 1、條件：a+bc且a+cb且b+ca 2、條件成立，存在該三角形，否則，不存在。,解決： 1、輸入邊長(zhǎng)a,b,c，判斷思路1中的條件。 2、根據(jù)思路2中的結(jié)論，輸出結(jié)論。,2、程序框圖,解：,2、程序框圖,（3）循環(huán)結(jié)構(gòu) 例5：設(shè)計(jì)一個(gè)計(jì)算1+2++100的值的算法。,思路： 1、算法要實(shí)現(xiàn)累加：?jiǎn)栴}是一個(gè)連加，按照算法的通用性和普適性來(lái)說(shuō)，該問(wèn)題的共性是加法，且重復(fù)。 2、有限次完成。,解決： 1、設(shè)置一個(gè)累加變量，用于存放總和。 2、設(shè)置一個(gè)計(jì)數(shù)變量，用于判斷累加次數(shù)是否超過(guò)100次。,2、程序框圖,解：,直到型,當(dāng)型,習(xí)題：1、設(shè)計(jì)一個(gè)

9、求12+22++1002的值。（思考）,2、某居民區(qū)的物業(yè)部門每月向居民收取衛(wèi)生費(fèi)：3人和3人以下的住戶，每月收取5元，超過(guò)3人的住戶，每超過(guò)1人加收1.2元.設(shè)計(jì)算法，根據(jù)輸入的人數(shù)，計(jì)算應(yīng)收取的衛(wèi)生費(fèi)，畫出框圖。（思考）,解答：1、略。,2、分析：衛(wèi)生費(fèi)是一個(gè)分段函數(shù)：,3、實(shí)現(xiàn)算法的程序,計(jì)算機(jī)要完成任何一項(xiàng)任務(wù)都需要算法，但要讓計(jì)算機(jī)正確執(zhí)行，必須要將算法“翻譯”成計(jì)算機(jī)能夠讀懂的程序才能執(zhí)行。,高級(jí)語(yǔ)言包括：BASIC，PASCAL，C， C++（Visual C++，Bland C++等），JAVA，Power Builder， Delphi等，只要掌握一門或兩門高級(jí)語(yǔ)言即可。,3

10、、實(shí)現(xiàn)算法的程序,例1、用描點(diǎn)法作函數(shù) 的圖像時(shí)，要求出自變量和函數(shù)的一組對(duì)應(yīng)值，編寫程序，分別計(jì)算當(dāng)x=-5,-4,-3,-2,-1,0,1,2,3,4,5時(shí)的函數(shù)值.,3、實(shí)現(xiàn)算法的程序,例2、計(jì)算一個(gè)學(xué)生的數(shù)學(xué)、語(yǔ)文、英語(yǔ)三門課的平均成績(jī).,例3、給一個(gè)變量重復(fù)賦值.,例4、交換兩個(gè)變量A和B的值，并輸出交換前后的值.,3、實(shí)現(xiàn)算法的程序,例5、編寫程序求ax2+bx+c=0方程的根.,例6、編寫程序，使任意輸入的3個(gè)數(shù)從大到小的順序輸出.,習(xí)題：判斷一年是否為閏年的程序.,3、實(shí)現(xiàn)算法的程序,循環(huán)結(jié)構(gòu)：編寫求和程序.,編寫判斷是否是質(zhì)數(shù)的程序.,思考：改進(jìn)判斷質(zhì)數(shù)的程序.,習(xí)題：二分法

11、求x2-2=0的近似根.,案例1：輾轉(zhuǎn)法相除求兩數(shù)最大公約數(shù),求8251與6105的最大公約數(shù),8251=6105 1 +2146,6105=22146+1813,2146=1813 1 +333,1813= 5 333+148,333 = 2 148+37,148 = 4 37+0,4、典型的算法介紹,程序流程圖,更相減損術(shù),可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等著，以等數(shù)約之。,第1步：任給兩個(gè)正整數(shù)；判斷它們是否是偶數(shù)，若是，用2約簡(jiǎn)；若不是，執(zhí)行第2步。,第2步：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個(gè)操作直到所得的數(shù)相

12、等為止。,例1 更相減損術(shù)求98與63的最大公約數(shù),案例2：秦九韶算法,f(x)=x5+x4+x3+x2+x+1（需做10次乘法,5次加法） =x*x*x*x*x+x*x*x*x+x*x*x+x*x+x,=(((( xx+x) x+x) x+x) x+x+1) （4次乘法,5次加法）,f(x)=anxn+ an-1xn-1 + a1x +a0,=((((anx+ an-1)x+ +a1) x+a0,=(anxn-1+ an-1xn-2 + a1 ) x +a0,=((anxn-2+ an-1xn-3 + +a2) x + a1 ) x +a0,=,v1=55+2=27 v2=27 5 +3

13、.5=138.5 v3=138.5 5-2.6=689.9 v4=689.9 5+1.7=3451.2 v5=3451.2 5-0.8=17255.2,例2 :已知一個(gè)5次多項(xiàng)式為f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8,思考：總計(jì)多少次乘，多少次加?,f(x)=anxn+ an-1xn-1 + a1x +a0,=((((anx+ an-1)x+ +a1) x+a0,程序流程圖,案例3：排序,i 0 1 2 3 4 5 6 7 8 (49)，38，65，97，76，13，27，49 2 (38) (38，49)，65，97，76，13，27，49 3 (38

14、，49，65)，97，76，13，27，49 4 (38，49，65，97)，76，13，27，49 5 (76) (38，49，65，76，97)，13，27，49 6 (13) (13，38，49，65，76，97)，27，49 7 (27) (13，27，38，49，65，76，97)，49 8 (49) (13，27，38，49，49，65，76，97),實(shí)例數(shù)據(jù)1： (49)，38，65，97，76，13，27，49,直接插入排序,i 0 1 2 3 4 5 6 （8），3， 2， 5， 9， 6 2 (3) （3， 8）， 2， 5， 9， 6 3 (2) （2， 3

15、， 8）， 5， 9， 6 4 (5) (2， 3， 5， 8），9， 6 5 (9) (2， 3， 5， 8 ， 9 ），6 6 (6) (2， 3， 5 ，6 ， 8 ， 9),實(shí)例數(shù)據(jù)2： 8，3，2，5，9，6,例3 用冒泡法對(duì)數(shù)據(jù)7,5,3,9,1從小到大進(jìn)行排序,7 5 3 9 1,5 7 3 9 1,5 3 7 9 1,5 3 7 9 1,1 3 5 7 9,見(jiàn)程序paixu2.bas,案例4：進(jìn)位制,進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的計(jì)數(shù)系統(tǒng)，“滿幾進(jìn)一” 就是幾進(jìn)制。幾進(jìn)制的基數(shù)就是幾。,3721=3103+ 7102+ 2101+ 1100,一般地，若k是一個(gè)大于1的整

16、數(shù)，那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式 an an -1 a1 a0(k)(0