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

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

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

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

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

4、余數(shù)r1；,第三步：若r10，則r1為m，n的最大公約數(shù)；若r10，則用除數(shù)r0除以余數(shù)r1得到一個商q2和一個余數(shù)r2,第n步：依次計算直至rn0，此時所得到的rn1即為所求的最大公約數(shù),,程序圖框,帶余除法,INPUT “請輸入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ù) ，寫出它的流程框圖和BASIC程序,更相減損術(shù),我國早期也有解決求最大公

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

6、少減多，更相減損，求其等也，以等數(shù)約之。,翻譯出來為：,第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。,第二步：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。,第三部：繼續(xù)第二步，直到所得的數(shù)相等為止，則這個數(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、的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。,（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到,練習(xí),思考一.用輾轉(zhuǎn)相除法求下列各組數(shù)的最大公約數(shù)，并在自己編寫的BASIC程序中驗證。（1）225，135 （2）98，196 （3）72，168,思考二：用更相減損法可否求上述3組數(shù)的最大公約數(shù)？可否利用更相減損法設(shè)計出程序框圖及程序？若能，在電腦上測試自己的程序；若不能說明無法實現(xiàn)的理由。,思考三：利用輾轉(zhuǎn)相除法是否可以求兩數(shù)的最大公倍數(shù)？

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

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

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

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

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

13、順序排列嗎？,練習(xí),請你設(shè)計一個數(shù)據(jù)列為R1,R2,,R10,要求從小到大的順序排列？,1.畫出一次冒泡排序的算法流程圖,2.畫出整個冒泡排序的算法流程圖,整個排序流程圖如圖所示,說明,,1.冒泡法排序完成n個數(shù)據(jù)的一次排序需要n-1次比較，完成整個排序需要(n-1)！次比較，對于數(shù)據(jù)較多時，計算量很大。,2.有些數(shù)據(jù)的冒泡法排序可能用更少的步驟可以完成，后面的步驟可能毫無意義，但計算機必須完成。,3.交換數(shù)據(jù)時注意引入第三方變量。,案例4.進位制,,,將 也加到和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能滿足式,事實上，這里面應(yīng)用到了一個知識： 進位制,進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的計數(shù)系統(tǒng)，約定滿二進一，就是二進制；滿十進一，就是十進制，等等，也就是說滿幾進一就是幾進制，幾進制的基數(shù)就是幾,大于1的整數(shù),由于自然數(shù)有無限多個，對于每一個自然數(shù)如果都用一個獨立的名稱或符號來讀出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一種讀數(shù)、寫數(shù)制度--進位制,,,

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