人教版遼寧省北票市高中數(shù)學(xué) 第一章 算法初步 1.3 中國古代數(shù)學(xué)中的算法案例課件 新人教B必修3

1、2021/8/9 星期一11.3 中國古代數(shù)學(xué)中的算法案例第一章 算法初步2021/8/9 星期一2一、復(fù)習(xí)引入 下面我們舉一些我國古代代數(shù)學(xué)中“算法”的例子，讓同學(xué)們體會(huì)“算法”的概念，看一看中國古代數(shù)學(xué)在算法上的偉大成就。 我們在小學(xué)、中學(xué)學(xué)到的算術(shù)、代數(shù)，從計(jì)數(shù)到多元一次聯(lián)立方程組以及方程的求根方法，都是我國古代數(shù)學(xué)家最先創(chuàng)造的，有的比其他國家早幾百年甚至上千年。我國人民在長期的生活、生產(chǎn)和勞動(dòng)中，創(chuàng)造了很多數(shù)學(xué)的計(jì)算和思想方法。2021/8/9 星期一3二、提出問題本節(jié)主要介紹的內(nèi)容一、更相減損之術(shù)（又稱“等值算法”） -研究如何求二個(gè)正整數(shù)的最大公約數(shù)。二、割圓術(shù) -解決圓周率的近似

2、值問題。三、秦九韶算法 -解決求多項(xiàng)式函數(shù)值問題。2021/8/9 星期一4三、概念形成概念1.求兩個(gè)正整數(shù)的最大公約數(shù)你記得在小學(xué)里是如何求最大公約數(shù)嗎？對(duì)了，用短除法。例如求18和30的最大公約數(shù)：所以，18與30的最大公約數(shù)是23=6。 這個(gè)方法可以總結(jié)為：用兩個(gè)數(shù)連續(xù)除以他們的公約數(shù)，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來。2021/8/9 星期一5三、概念形成概念1.求兩個(gè)正整數(shù)的最大公約數(shù) 當(dāng)兩個(gè)數(shù)比較大時(shí)（如8610與6300），使用上述方法求最大公約數(shù)就比較困難。下面我們介紹兩種古老而有效的算法輾轉(zhuǎn)相除法與更相減損術(shù)。（1）輾轉(zhuǎn)相除法(*)例子:輾轉(zhuǎn)相除法求86

3、10和6300的最大公約數(shù)。為了簡潔，我們把8610和6300的最大公約數(shù)記作（8610，6300）。把8610變?yōu)橄率?8610 = 63001 + 2310 2021/8/9 星期一6三、概念形成概念1.求兩個(gè)正整數(shù)的最大公約數(shù)我們來看一下（8610，6300）和（6300，2310）之間的關(guān)系 它們有相同的公約數(shù)，因此也有相同的最大公約數(shù)。難道這只是巧合嗎? 可以證明它們有相同的公約數(shù)（略）。 2021/8/9 星期一7三、概念形成我們可以總結(jié)為：（被除數(shù)，除數(shù)）=（除數(shù)，余數(shù)）概念1.求兩個(gè)正整數(shù)的最大公約數(shù)據(jù)此，我們可以用如下辦法求8610和6300的最大公約數(shù)：被除數(shù) 除數(shù) 余數(shù)

4、（8610，6300）8610 = 63001 + 2310 =（6300，2310）6300 = 23102 + 1680 =（2310，1680）2310 = 16801 + 630 =（1680，630）1680 = 6302 + 420 =（630，420）630 = 4201 + 210 =（420，210）420 = 2102 + 0 =210最大公約數(shù)這就是輾轉(zhuǎn)相除法。由除法的性質(zhì)可知，對(duì)于任意兩個(gè)正整數(shù)，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉(zhuǎn)相除法求出最大公約數(shù)。 2021/8/9 星期一8三、概念形成輾轉(zhuǎn)相除法算法分析概念1.求兩個(gè)正整數(shù)的最大公約數(shù)從上面例子可

5、以看出，輾轉(zhuǎn)相除法中也包含重復(fù)的操作，因此可以用循環(huán)結(jié)構(gòu)來構(gòu)造算法。S1：給定兩個(gè)正數(shù)m，n。S2：計(jì)算m 除以n所得的余數(shù)r。S3：m=n，n=r。S4：若r=0，則m，n的最大公約數(shù)等于m；否則，返回S2。r = 0 ? n =rm =nr = m MOD n輸入：m，n輸出：m開始結(jié)束2021/8/9 星期一9三、概念形成輾轉(zhuǎn)相除法的Siclab程序概念1.求兩個(gè)正整數(shù)的最大公約數(shù)r = 0 ? n =rm =nr = m MOD n輸入：m，n輸出：m開始結(jié)束m=input(m=);n=input(n=);if mn x=m;m=n;n=x;endr=n;while r0 r=modu

6、lo(m,n); m=n; n=r;endprint(%io(2),m)2021/8/9 星期一10三、概念形成概念1.求兩個(gè)正整數(shù)的最大公約數(shù)（2）更相減損術(shù)九章算術(shù)是中國古代的數(shù)學(xué)專著，其中有這樣一段論述：“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。”。這是一個(gè)求最簡分式的算法，可以用它來求最大公約數(shù)， 我們稱為“更相減損術(shù)”。 翻譯為現(xiàn)代語言如下 2021/8/9 星期一11三、概念形成概念1.求兩個(gè)正整數(shù)的最大公約數(shù)（2）更相減損術(shù)第一步：任意給兩個(gè)正整數(shù)，如果它們都是偶數(shù)，用2約簡；若不是，執(zhí)行第二步。 第二步：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小

7、的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到它們相等為止，則這個(gè)“相等的數(shù)”就是所求的最大公約數(shù)；如果操作過程中有約分，還要在“等數(shù)”上乘以約掉的因數(shù)。2021/8/9 星期一12三、概念形成概念1.求兩個(gè)正整數(shù)的最大公約數(shù)（2）更相減損術(shù)例如：求78和36的最大公約數(shù)。解：（78，36）（6，36）（42，36）（6，30）（6，18）（6，12）（6，24）（6，6）所以，78和36的最大公約數(shù)為6。此種算法稱為“等值算法”。2021/8/9 星期一13N三、概念形成概念1.求兩個(gè)正整數(shù)的最大公約數(shù)開 始輸入m、n輸出m、nmnmnm=m-nn=n-m結(jié) 束yyNm=input(m=);n

8、=input(n=);while mn if mn m=m-n; else n=n-m; endendprint(%io(2),m,n);（2）更相減損術(shù)2021/8/9 星期一14三、概念形成概念2.割圓術(shù) 所謂“割圓術(shù)”，是用圓內(nèi)接正多邊形的周長去無限逼近圓周并以此求取圓周率的方法。這個(gè)方法，是我國魏晉時(shí)期劉徽在批判總結(jié)了數(shù)學(xué)史上各種舊的計(jì)算方法之后，經(jīng)過深思熟慮才創(chuàng)造出來的一種嶄新的方法。 劉徽從圓內(nèi)接正六邊形把圓周等分為六條弧的基礎(chǔ)上，再繼續(xù)等分，把每段弧再分割為二，做出一個(gè)圓內(nèi)接正十二邊形，這個(gè)正十二邊形的周長不就要比正六邊形的周長更接近圓周了嗎？如果把圓周再繼續(xù)分割，做成一個(gè)圓內(nèi)接

9、正二十四邊形，那么這個(gè)正二十四邊形的周長必然又比正十二邊形的周長更接近圓周。2021/8/9 星期一15三、概念形成概念2.割圓術(shù)先分析割圓術(shù)的算法oAB1Chnxn設(shè)圓o的面積為S，其內(nèi)接正n邊形的面積為Sn.D所以正2n邊形的面積等于：S2n=Sn+nxn(1-hn)/2.從而有S2nSS2n+(S2n-Sn).計(jì)算圓周率的不足近似值計(jì)算圓周率的過剩近似值由于2021/8/9 星期一16三、概念形成概念2.割圓術(shù)oAB1ChnxnD割圓術(shù)的Siclab程序n=6;x=1;s=6*sqrt(3)/4;for i=1:1:5 h=sqrt(1-(x/2)2); s=s+n*x*(1-h)/2;

10、 n=2*n; x=sqrt(x/2)2+(1-h)2);endprint(%io(2),n,s);由于2021/8/9 星期一17三、概念形成概念3.秦九韶算法已知 求當(dāng) 時(shí)的函數(shù)值，要用多少次乘法，多少次加法？ 乘法：4+3+2+1= 。加法： 。乘法和加法的次數(shù)能減少嗎？ 聰明的同學(xué)們一定想到了，如果我們計(jì)算出了x2，當(dāng)我們計(jì)算x3時(shí)根本不用從頭算起，利用x2用一次乘法就可以算出x3了。同理x4可由x3算出，x5可由x4算出，這樣我們只用了4次乘法即可。計(jì)算過程大大簡化。對(duì)于計(jì)算機(jī)來說，做一次乘法運(yùn)算所用的時(shí)間比一次加法運(yùn)算要長的多，所以減少乘法運(yùn)算次數(shù)，計(jì)算機(jī)能更快的得到結(jié)果。 202

11、1/8/9 星期一18三、概念形成概念3.秦九韶算法比如一個(gè)5次多項(xiàng)式為 求當(dāng) 時(shí)的函數(shù)值，要用多少次乘法，多少次加法？ 還有更快速的算法嗎？分析：用剛才的方法，計(jì)算 共用4次乘法，乘上它們的系數(shù)需要5次乘法，共需要9次乘法和5次加法。2021/8/9 星期一19三、概念形成概念3.秦九韶算法比如一個(gè)5次多項(xiàng)式為 求當(dāng) 時(shí)的函數(shù)值，要用多少次乘法，多少次加法？ 解：原式可化為多項(xiàng)式的系數(shù)分別為：先計(jì)算最內(nèi)層括號(hào)里 的值，然后由內(nèi)向外逐層計(jì)算。2021/8/9 星期一20三、概念形成概念3.秦九韶算法比如一個(gè)5次多項(xiàng)式為 求當(dāng) 時(shí)的函數(shù)值，要用多少次乘法，多少次加法？ 多項(xiàng)式的系數(shù)分別為：共用了

12、5次乘法和5次加法，減少了4次乘法。2021/8/9 星期一21三、概念形成概念3.秦九韶算法用秦九韶算法求n次多項(xiàng)式的值時(shí)，需要n次乘法運(yùn)算，n次加法運(yùn)算，共2n次運(yùn)算。2021/8/9 星期一22三、概念形成概念3.秦九韶算法開始結(jié)束i=i-1 i=n-1輸出v輸入n，an，x輸入ain=input(n=);an=input(an=);x=input(x=);v=an;i=n-1;while i=0 print(%io(2),i) a=input(ai=); v=v*x+a;i=i-1;endprint(%io(2),v)用秦九韶算法框圖及程序2021/8/9 星期一23四、應(yīng)用舉例例1.

13、用更相減損術(shù)求132與143的最大公約數(shù)（132，143）（132，11）（121，11）（110，11）（99，11）（88，11）（77，11）（66，11）（55，11）（44，11）（33，11）（22，11）（11，11）故，132與143的最大公約數(shù)是11。思考：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約數(shù)。（1）8251，6105 （2）1480，4802021/8/9 星期一24四、應(yīng)用舉例例2.用秦九韶算法求多項(xiàng)式 在x=2時(shí)的函數(shù)值。 算法程序可參照前面的秦九韶算法程序。2021/8/9 星期一25五、課堂練習(xí)思考?1、用秦九韶算法求多項(xiàng)式f（x）=2+0.35x+1.8x23.66x3+6x45.2x5+x6在x=1.3的值時(shí)，令v0=a6；v1=v0 x+a5； ；v6=v5x+a0時(shí)，v3的值為（）A.9.8205 B.14.25C.22.445 D.30.9785C2.數(shù)4557、1953、5115的最大公約數(shù)是（）A.31B.93C.217D.651B2021/8/9 星期一263.用等值算法求下列各數(shù)的最大公約數(shù).（1）63，84； （2）351，513.答案：(1)21 (2)