課標(biāo)人教A版必修3全套課件第一章算法案例.ppt

《課標(biāo)人教A版必修3全套課件第一章算法案例.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《課標(biāo)人教A版必修3全套課件第一章算法案例.ppt（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、人教A版高中數(shù)學(xué)必修3 多媒體課件,多思、創(chuàng)新、融合,復(fù)習(xí)回顧,基本結(jié)構(gòu),流程圖,順序結(jié)構(gòu),變量與賦值,循環(huán)結(jié)構(gòu),基本語(yǔ)句,循環(huán)語(yǔ)句,條件語(yǔ)句,,WHILE語(yǔ)句,UNTIL語(yǔ)句,IF-THEN語(yǔ)句,,,,語(yǔ)句適用結(jié)構(gòu),算法,,條件結(jié)構(gòu),,我們這節(jié)課就利用基本的算法程序來(lái)解決一些實(shí)際問(wèn)題，進(jìn)一步體會(huì)算法的程序思想。,案例1.輾轉(zhuǎn)相除法與更相減損術(shù),在初中，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知識(shí)，你能求出18與30的最大公約數(shù)嗎？,所以，18和30的最大公約數(shù)是：236,但是，當(dāng)我們處理較大數(shù)（如：8251與6105）的最大公因數(shù)時(shí)，如果利用這種方法可能計(jì)算量比較大，步驟比較多。下面我們介紹一種古老而有效

2、的算法輾轉(zhuǎn)相除法,這種算法是歐幾里得公元前300年左右首先提出的，因此又叫歐幾里得算法,例1 求兩個(gè)正數(shù)8251和6105的最大公約數(shù)。,分析：8251與6105兩數(shù)都比較大，而且沒(méi)有明顯的公約數(shù)，如能把它們都變小一點(diǎn)，根據(jù)已有的知識(shí)即可求出最大公約數(shù),解,8251610512146,顯然8251和6105的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的約數(shù)，所以8251與6105的最大公約數(shù)也是6105與2146的最大公約數(shù),繼續(xù)下去，我們得到：,歐幾里得（公元前330-公元前275）：古希臘數(shù)學(xué)家，雅典人 歐幾里得是柏拉圖的學(xué)生，長(zhǎng)期在亞歷山大里亞教書(shū)。 公

3、元前300年左右，代表作幾何原本13卷問(wèn)世，創(chuàng)立了著名的歐氏幾何，至今仍為中學(xué)生必學(xué)的一門(mén)基礎(chǔ)知識(shí)。歐幾里得對(duì)光學(xué)也有一定研究。,6105214621813214618131333181333351483331482371483740則37為8251與6105的最大公約數(shù),這就是輾轉(zhuǎn)相除法，有除法的性質(zhì)可以知道，對(duì)于任意兩個(gè)正整數(shù)，上述除法步驟總可以在有限步驟之后完成,你能寫(xiě)出它的算法程序嗎？,利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：,第一步：用較大的數(shù)m除以較小的數(shù)n得到一個(gè)商q0和一個(gè)余數(shù)r0；,第二步：若r00，則n為m，n的最大公約數(shù)；若r00，則用除數(shù)n除以余數(shù)r0得到一個(gè)商q1和一個(gè)

4、余數(shù)r1；,第三步：若r10，則r1為m，n的最大公約數(shù)；若r10，則用除數(shù)r0除以余數(shù)r1得到一個(gè)商q2和一個(gè)余數(shù)r2,第n步：依次計(jì)算直至rn0，此時(shí)所得到的rn1即為所求的最大公約數(shù),,程序圖框,帶余除法,INPUT “請(qǐng)輸入m，n的值”；m，n IF mn THEN a=m m=n n=a END IF DO r=m MOD N m=n n=r LOOP UNTIL r=0 PRINT m END,,作用是什么？,,為什么要用直到型循環(huán)結(jié)構(gòu)？,練一練,1.利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù) ，寫(xiě)出它的流程框圖和BASIC程序,更相減損術(shù),我國(guó)早期也有解決求最大公

5、約數(shù)問(wèn)題的算法,九章算術(shù)（公元50年100年或更早 ）是中國(guó)古代數(shù)學(xué)專(zhuān)著，承先秦?cái)?shù)學(xué)發(fā)展的源流，進(jìn)入漢朝后又經(jīng)許多學(xué)者的刪補(bǔ)才最后成書(shū)，這大約是公元一世紀(jì)的下半葉。它的出現(xiàn)，標(biāo)志著中國(guó)古代數(shù)學(xué)體系的形成。,歷代數(shù)學(xué)家把它尊為“算經(jīng)之首”這是世界上最早的印刷本數(shù)學(xué)書(shū)。 九章算術(shù)共收有 246個(gè)數(shù)學(xué)問(wèn)題，分為九章。分別是：方田、栗米、衰分、少?gòu)V、商功、均輸、盈不足、方程、勾股。 九章算術(shù)是世界上最早系統(tǒng)敘述了分?jǐn)?shù)運(yùn)算的著作；其中盈不足的算法更是一項(xiàng)令人驚奇的創(chuàng)造；“方程”章還在世界數(shù)學(xué)史上首次闡述了負(fù)數(shù)及其加減運(yùn)算法則。,更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以

6、少減多，更相減損，求其等也，以等數(shù)約之。,翻譯出來(lái)為：,第一步：任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步。,第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。,第三部：繼續(xù)第二步，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù),例2 用更相減損術(shù)求98與63的最大公約數(shù).,解 由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減,98-6335 63-3528 35-287 28-714 14-77,所以，98與63的最大公約數(shù)是7,兩種算法比較，你有什么發(fā)現(xiàn)？,比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別,（1）都是求最大公約數(shù)

7、的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。,（2）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到,練習(xí),思考一.用輾轉(zhuǎn)相除法求下列各組數(shù)的最大公約數(shù)，并在自己編寫(xiě)的BASIC程序中驗(yàn)證。（1）225，135 （2）98，196 （3）72，168,思考二：用更相減損法可否求上述3組數(shù)的最大公約數(shù)？可否利用更相減損法設(shè)計(jì)出程序框圖及程序？若能，在電腦上測(cè)試自己的程序；若不能說(shuō)明無(wú)法實(shí)現(xiàn)的理由。,思考三：利用輾轉(zhuǎn)相除法是否可以求兩數(shù)的最大公倍數(shù)？

8、試設(shè)計(jì)程序框圖并轉(zhuǎn)換成程序在BASIC中實(shí)現(xiàn)。,據(jù)我們的計(jì)算統(tǒng)計(jì)可以得出我們共需要10次乘法運(yùn)算，5次加法運(yùn)算,,我們把多項(xiàng)式變形為： 再統(tǒng)計(jì)一下計(jì)算當(dāng)時(shí)的值時(shí)需要的計(jì)算次數(shù)，可以得出僅需4次乘法和5次加法運(yùn)算即可得出結(jié)果。顯然少了6次乘法運(yùn)算。這種算法就叫秦九韶算法。,秦九韶（1202--1261年），字道古，安岳縣人。其父秦季棲，進(jìn)士出身，官至工部郎中、秘書(shū)少監(jiān)。秦九韶性敏慧，勤奮好學(xué)，幼年隨父居中都（今北京），受到名師指導(dǎo)，學(xué)習(xí)日益增進(jìn)。及長(zhǎng)，隨父遷湖州（今浙江吳興縣），在西門(mén)外修建住房，由秦九韶設(shè)計(jì)施工，堂分7間，后為列室，僅中堂1間，縱橫7丈，極其宏偉寬敞

9、，顯示出他在建筑方面的才能,它的一般計(jì)算步驟如下：,,求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)的一次多項(xiàng)式的值，即：,再有內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即：,這樣將求n次多項(xiàng)式f(x)的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值。,,i=0 WHILE i5 INPUT ai WEND DO v=a5 v=v*x0+a5-n n=n+1 LOOP UNTIL n6 END,思考：（1）例1計(jì)算時(shí)需要多少次乘法計(jì)算？多少次加法計(jì)算？ （2）在利用秦九韶算法計(jì)算n次多項(xiàng)式當(dāng)時(shí)需要多少次乘法計(jì)算和多少次加法計(jì)算？,練習(xí),案例3.排序問(wèn)題,你會(huì)使用這些字典嗎？,為了便于查詢和檢索，常常需要根據(jù)要求將被查尋的對(duì)象按照一

10、定的順序排列，通常稱為排序，,你會(huì)從這些書(shū)籍中查閱你想要的東西嗎？,我們?cè)谝粋€(gè)已經(jīng)排好循序的一系列數(shù)中插入一個(gè)數(shù)據(jù)，成為一個(gè)新的系列，且仍按原來(lái)的規(guī)則排序。,直接插入排序,要將8插入到1,3,5,7,9,11,13中，我們?cè)鯓涌紤]？,確定8在原系列中的位置，使8小于或等于原系列中右邊的數(shù)據(jù)，大于或等于左邊的數(shù)據(jù),將這個(gè)位置空出來(lái)，將數(shù)據(jù)8插進(jìn)去,8,例題分析,例3.將數(shù)列49,38,65,97,76,13,27,49按小到大的順序排列,我們的想法是：,1.先排49，38的順序：38，49,2.比較第三個(gè)數(shù)與它們的大小得到：38，49，65,3.比較第四個(gè)數(shù)與2的順序得到：38，49，65，97

11、,n.第n個(gè)數(shù)與前面數(shù)的關(guān)系，得到最后的排序： 13，27，38，49，49，65，76，97,,反復(fù)使用直接插入排序算法，即首先把第一個(gè)數(shù)當(dāng)作一個(gè)基準(zhǔn)，插入第二個(gè)數(shù)變成有兩個(gè)數(shù)據(jù)的有序列，再插入第三個(gè)數(shù)，依此類(lèi)推，就完成了整個(gè)無(wú)序列的有序化。流程圖如下：,你會(huì)設(shè)計(jì)它的BASIC算法嗎？,1排序號(hào)：,上述數(shù)據(jù)我們還可以這樣來(lái)排序：,2排序,現(xiàn)將1號(hào)數(shù)據(jù)49和2號(hào)數(shù)據(jù)38比較，因?yàn)?938所以，49和38的位置互換，變?yōu)椋?第一次排序,第一步：1號(hào)2號(hào)排序,第二步：2號(hào)3號(hào)排序,因?yàn)?9<65所以這倆數(shù)的序號(hào)不變,第三步：比較3、4號(hào)數(shù)據(jù),方法同第二步，因?yàn)?5<97所以數(shù)據(jù)順序不變,第四步：比

12、較4、5號(hào)數(shù)據(jù),方法同第一步，因?yàn)?776，所以4、5號(hào)數(shù)據(jù)互換，則：,第五步：比較5、6號(hào)數(shù)據(jù)：,方法同第二步，9713則，交換5、6號(hào)數(shù)據(jù)，則：,第六步：比較6、7號(hào)數(shù)據(jù),同理，上面的順序可以變?yōu)椋?同理第七步比較7、8號(hào)數(shù)據(jù)后可以變?yōu)椋?這樣就完成了第一次排序，它的基本特征是將最大數(shù)排到了最右邊，然后再?gòu)念^開(kāi)始，進(jìn)行第二次排序，將第二大的數(shù)據(jù)排到了倒數(shù)第二位，反復(fù)下去，就可以完成排序。一共要進(jìn)行7次才能完成。我們叫它冒泡排序（bubble sorting）,思考,你會(huì)用冒泡法將上面的數(shù)據(jù)按從大到小的順序排列嗎？,完成所有的排序需要多少步比較？,你還有其他的排序方法將上面的數(shù)據(jù)按從大到小的

13、順序排列嗎？,練習(xí),請(qǐng)你設(shè)計(jì)一個(gè)數(shù)據(jù)列為R1,R2,,R10,要求從小到大的順序排列？,1.畫(huà)出一次冒泡排序的算法流程圖,2.畫(huà)出整個(gè)冒泡排序的算法流程圖,整個(gè)排序流程圖如圖所示,說(shuō)明,,1.冒泡法排序完成n個(gè)數(shù)據(jù)的一次排序需要n-1次比較，完成整個(gè)排序需要(n-1)！次比較，對(duì)于數(shù)據(jù)較多時(shí)，計(jì)算量很大。,2.有些數(shù)據(jù)的冒泡法排序可能用更少的步驟可以完成，后面的步驟可能毫無(wú)意義，但計(jì)算機(jī)必須完成。,3.交換數(shù)據(jù)時(shí)注意引入第三方變量。,案例4.進(jìn)位制,,,將 也加到和N上，這樣a、b、c就在每一位上都恰好出現(xiàn)兩次，所以有,分析：,,,你知道它的原理嗎？,從而 3194<222(a+b+c)<3

14、194+1000，而a、b、c是整數(shù) 所以 15a+b+c18 因 22215-3194=136， 22216-3194=358， 22217-3194=580， 22218-3194=802 其中只有3+5+8=16能滿足式,事實(shí)上，這里面應(yīng)用到了一個(gè)知識(shí)： 進(jìn)位制,進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的計(jì)數(shù)系統(tǒng)，約定滿二進(jìn)一，就是二進(jìn)制；滿十進(jìn)一，就是十進(jìn)制，等等，也就是說(shuō)滿幾進(jìn)一就是幾進(jìn)制，幾進(jìn)制的基數(shù)就是幾,大于1的整數(shù),由于自然數(shù)有無(wú)限多個(gè)，對(duì)于每一個(gè)自然數(shù)如果都用一個(gè)獨(dú)立的名稱或符號(hào)來(lái)讀出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一種讀數(shù)、寫(xiě)數(shù)制度--進(jìn)位制,,,

15、十進(jìn)制數(shù) 表示實(shí)際數(shù)值為：,K進(jìn)制數(shù) 實(shí)際表示數(shù)為：,在日常生活中，我們最熟悉的還是十進(jìn)制數(shù)，據(jù)說(shuō)這和古人曾以手指計(jì)數(shù)有關(guān),為了區(qū)別進(jìn)制，我們就用下標(biāo)（k）表示k進(jìn)制數(shù),a n是09的數(shù)子,下面我們來(lái)用一個(gè)具體的例子來(lái)分析：,例4.將二進(jìn)制數(shù)110 011(2)化成十進(jìn)制數(shù),解 根據(jù)k進(jìn)制數(shù)的實(shí)際意義，我們可以這樣來(lái)轉(zhuǎn)換：,INPUT a,b,c i=1 b=0 WHILE i<=n t=GET ai b=b+t*k(i-1) i=i+1 WEND PRINT b END,GET函數(shù)用于取出a的有數(shù)第i位,例5.不89化為二進(jìn)制數(shù),分析：89=2(2(2(2(22+1)+1)+0)+0)+1 = =1 011 001(2),,所以上式可以表示為：1 011 001,綜合：上述方法叫做k進(jìn)制數(shù)的除k取余法,練一練,5.把89化為五進(jìn)制數(shù),思考：1如何將十六進(jìn)制數(shù)A1F721化為二進(jìn)制數(shù),一般方法：,k進(jìn)制數(shù),十進(jìn)制數(shù),n進(jìn)制數(shù),,,1010 0001 1111 0111 0010 0001,算法,程序圖框,算法語(yǔ)句,輾轉(zhuǎn)相除與更相減損術(shù),秦 九 韶 算 法,排 序,進(jìn) 位 制,