學(xué)案7中國(guó)古代數(shù)學(xué)中的算法案例

1、開(kāi)始學(xué)案學(xué)案7 7中國(guó)古代數(shù)學(xué)中的中國(guó)古代數(shù)學(xué)中的算法案例算法案例學(xué)點(diǎn)一學(xué)點(diǎn)二 1. 1.用兩數(shù)中較大的數(shù)減去較小的數(shù)用兩數(shù)中較大的數(shù)減去較小的數(shù), ,再用再用 和和 構(gòu)成新的一對(duì)數(shù)構(gòu)成新的一對(duì)數(shù), ,再用大數(shù)減小數(shù)再用大數(shù)減小數(shù), ,以同樣的操以同樣的操作一直做下去作一直做下去, ,直到產(chǎn)生直到產(chǎn)生 , ,這個(gè)數(shù)就是最這個(gè)數(shù)就是最大公約數(shù)大公約數(shù). . 2. 2.古希臘求兩個(gè)正整數(shù)的最大公約數(shù)的方法是古希臘求兩個(gè)正整數(shù)的最大公約數(shù)的方法是: : 用較大的數(shù)除以較小的數(shù)所得用較大的數(shù)除以較小的數(shù)所得的的 和和 構(gòu)成新的一對(duì)數(shù)構(gòu)成新的一對(duì)數(shù), ,繼續(xù)做上面的繼續(xù)做上面的除法除法, ,直到大數(shù)被小

2、數(shù)除盡直到大數(shù)被小數(shù)除盡, ,這個(gè)較小的數(shù)就是最大公約數(shù)這個(gè)較小的數(shù)就是最大公約數(shù). . 3. 3.割圓術(shù)是我國(guó)魏晉時(shí)期的數(shù)學(xué)家割圓術(shù)是我國(guó)魏晉時(shí)期的數(shù)學(xué)家 在注九章在注九章算術(shù)中采用算術(shù)中采用 . . 的一種方法的一種方法. . 返回目錄返回目錄差數(shù)差數(shù)較小的數(shù)較小的數(shù)一對(duì)相等的數(shù)一對(duì)相等的數(shù)輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法( (歐幾里得算法歐幾里得算法) )余數(shù)余數(shù)較小的數(shù)較小的數(shù)劉徽劉徽正多邊形面積逐漸逼近圓面積的算法計(jì)算正多邊形面積逐漸逼近圓面積的算法計(jì)算圓周率圓周率3.3.把一個(gè)把一個(gè)n n次多項(xiàng)式次多項(xiàng)式f f( (x x)=)=a an nx xn n a an nx xn na a1 1x

3、 x a a0 0改寫(xiě)成如下形式改寫(xiě)成如下形式: : f f( (x x)= )= a an nx xn na an nx xn na a1 1x xa a0 0= = . .= = . . = = . . 求多項(xiàng)式的值時(shí)求多項(xiàng)式的值時(shí), ,首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值的值, ,即即v v1 1= = . . 然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值, ,即即 v v2 2= = , , v v3 3= = , , v vn n= = , ,( (a an nx xn n-1-1a an nx xn n2 2a a1 1) )x

4、xa a0 0 (a an nx xn n-2-2a an nx xn n3 3+a a2 2) )x xa a1 1) )x xa a0 0 v v0 0 x xa an nv v2 2x xa an n3 3v v1 1x xa an n2 2v vn n-1-1x xa a0 0返回目錄返回目錄(（( (a an nx xa an n) )x x a an n2 2 ) )x xa a1 1) )x xa a0 0 返回目錄返回目錄這樣這樣, ,求求n n次多項(xiàng)式次多項(xiàng)式f f( (x x) )的值就轉(zhuǎn)化為的值就轉(zhuǎn)化為. .上述方法稱為秦九韶算法上述方法稱為秦九韶算法. .觀察上述秦九韶

5、算法中的觀察上述秦九韶算法中的n n個(gè)一次式個(gè)一次式, ,可見(jiàn)可見(jiàn)v vk k的計(jì)算要的計(jì)算要用到用到v vk k-1-1的值的值. .若令若令v v0 0= =a an n, ,我們可以得到公式我們可以得到公式: : . .這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟, ,因此可用因此可用 來(lái)實(shí)現(xiàn)來(lái)實(shí)現(xiàn). .求求n n個(gè)一次多項(xiàng)式的值個(gè)一次多項(xiàng)式的值 v vo o=a=an nv vk k=v=vk-k-1 1x+ax+an-kn-k( (k=k=1,2,1,2,n n) )循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 返回目錄返回目錄學(xué)點(diǎn)一學(xué)點(diǎn)一 求最大公約數(shù)求最大公約數(shù) 用更相減損之術(shù)求

6、用更相減損之術(shù)求9898和和6363的最大公約數(shù)的最大公約數(shù). . 【分析】【分析】由于由于6363不是偶數(shù)不是偶數(shù), ,把把9898和和6363以大數(shù)減小數(shù)以大數(shù)減小數(shù), ,并并輾轉(zhuǎn)相減輾轉(zhuǎn)相減. . 【解析】【解析】98-63=35,63-35=28,35-28=7,28-7=14,14-98-63=35,63-35=28,35-28=7,28-7=14,14-7=77=7，所以，所以9898和和6363的最大公約數(shù)為的最大公約數(shù)為7.7. 【評(píng)析】等值算法是當(dāng)大數(shù)減去小數(shù)的差等于小數(shù)時(shí)【評(píng)析】等值算法是當(dāng)大數(shù)減去小數(shù)的差等于小數(shù)時(shí)停止減法停止減法, ,較小的數(shù)就是所求的最大公約數(shù)較小的數(shù)

7、就是所求的最大公約數(shù). .設(shè)計(jì)程序設(shè)計(jì)程序, ,求兩正整數(shù)求兩正整數(shù)m m, ,n n的最小公倍數(shù)的最小公倍數(shù). . 解：由于解：由于m m, ,n n的最小公倍數(shù)的最小公倍數(shù), ,即為即為m m與與n n的乘積除以的乘積除以m m與與n n的最大公約數(shù)的最大公約數(shù). .因此因此, ,可先求出可先求出m m與與n n的最大公約數(shù)的最大公約數(shù), ,再用再用m m n n去除以這個(gè)最大公約數(shù)即可去除以這個(gè)最大公約數(shù)即可. . 程序如下程序如下: : m=input(“m=”) m=input(“m=”) n=input(“n=”) n=input(“n=”) S=m S=m* *n;n; whil

8、e mn while mn if mn if mn m=m-n; m=m-n; else else n=n-m; n=n-m; end end end end T= T= print(%io(2),T) print(%io(2),T);ms返回目錄返回目錄返回目錄返回目錄學(xué)點(diǎn)二學(xué)點(diǎn)二 秦九韶算法秦九韶算法用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式f f( (x x)=7)=7x x7 7+6+6x x6 6+5+5x x5 5+4+4x x4 4+3+3x x3 3+2+2x x2 2+ +x x在在x x=3=3時(shí)的值時(shí)的值. . 【分析】【分析】明確項(xiàng)數(shù)與次數(shù)明確項(xiàng)數(shù)與次數(shù)正確改寫(xiě)所給多項(xiàng)式

9、正確改寫(xiě)所給多項(xiàng)式從從內(nèi)向外逐次求值內(nèi)向外逐次求值. . 【解析】【解析】f f( (x x)=(7)=(7x x+6)+6)x x+5)+5)x x+4)+4)x x+3)+3)x x+2)+2)x x+1)+1)x x, , v v0 0=7=7， v v1 1=7=73+6=27,3+6=27, v v2 2=27=273+5=86,3+5=86, v v3 3=86=863+4=262,3+4=262, v v4 4=262=2623+3=789,3+3=789, v v5 5=789=7893+2=2 369,3+2=2 369, v v6 6=2 369=2 3693+1=7 10

10、8,3+1=7 108, v v7 7=7 108=7 1083=21 324,3=21 324, f f(3)=21 324.(3)=21 324.返回目錄返回目錄 【評(píng)析】利用秦九韶算法計(jì)算多項(xiàng)式的值關(guān)鍵是能正【評(píng)析】利用秦九韶算法計(jì)算多項(xiàng)式的值關(guān)鍵是能正確地將所給多項(xiàng)式改寫(xiě)確地將所給多項(xiàng)式改寫(xiě), ,然后由內(nèi)向外逐次計(jì)算然后由內(nèi)向外逐次計(jì)算, ,由于后項(xiàng)由于后項(xiàng)計(jì)算需用到前項(xiàng)的結(jié)果計(jì)算需用到前項(xiàng)的結(jié)果, ,故應(yīng)認(rèn)真、細(xì)心故應(yīng)認(rèn)真、細(xì)心, ,確保中間結(jié)果的確保中間結(jié)果的準(zhǔn)確性準(zhǔn)確性. .返回目錄返回目錄求多項(xiàng)式求多項(xiàng)式f f( (x x)=)=x x5 5+5+5x x4 4+10+10 x

11、 x3 3+10+10 x x2 2+5+5x x+1+1當(dāng)當(dāng)x x=-2=-2時(shí)的值時(shí)的值. . 解：先改寫(xiě)多項(xiàng)式解：先改寫(xiě)多項(xiàng)式, ,再由內(nèi)向外計(jì)算再由內(nèi)向外計(jì)算. . f f( (x x)=)=x x5 5+5+5x x4 4+10+10 x x3 3+10+10 x x2 2+5+5x x+1+1=(=(x x+5)+5)x x+10)+10)x x+10)+10)x x+5)+5)x x+1.+1.而而x x=-2,=-2,所以有所以有: :v v0 0=1,=1,v v1 1= =v v0 0 x x+ +a a4 4=1=1(-2)+5=3,(-2)+5=3,v v2 2= =v

12、 vx x+ +a a3 3=3=3(-2)+10=4,(-2)+10=4,v v3 3= =v v2 2x x+ +a a2 2=4=4(-2)+10=2,(-2)+10=2,v v4 4= =v v3 3x x+ +a a1 1=2=2(-2)+5=1,(-2)+5=1,v v5 5= =v v4 4x x+ +a a0 0=1=1(-2)+1=-1.(-2)+1=-1. 1. 1.如何理解三個(gè)算法案例如何理解三個(gè)算法案例? ? (1)(1)更相減損之術(shù)更相減損之術(shù) 所謂更相減損之術(shù)所謂更相減損之術(shù), ,就是對(duì)于給定的兩個(gè)數(shù)就是對(duì)于給定的兩個(gè)數(shù), ,以兩數(shù)中以兩數(shù)中較大的數(shù)減去較小的數(shù)較大

13、的數(shù)減去較小的數(shù), ,然后將所得的差和較小的數(shù)構(gòu)成一然后將所得的差和較小的數(shù)構(gòu)成一對(duì)新數(shù)對(duì)新數(shù), ,再用這對(duì)新數(shù)中的較大的數(shù)減去較小的數(shù)再用這對(duì)新數(shù)中的較大的數(shù)減去較小的數(shù), ,反復(fù)執(zhí)反復(fù)執(zhí)行此步驟直到差數(shù)和較小的數(shù)相等為止行此步驟直到差數(shù)和較小的數(shù)相等為止, ,此時(shí)相等的數(shù)便為此時(shí)相等的數(shù)便為原來(lái)兩個(gè)數(shù)的最大公約數(shù)原來(lái)兩個(gè)數(shù)的最大公約數(shù). . 所謂輾轉(zhuǎn)相除法所謂輾轉(zhuǎn)相除法, ,就是對(duì)于給定的兩個(gè)數(shù)就是對(duì)于給定的兩個(gè)數(shù), ,用較大的數(shù)用較大的數(shù)除以較小的數(shù)除以較小的數(shù), ,若余數(shù)不為零若余數(shù)不為零, ,則將余數(shù)和較小的數(shù)構(gòu)成新則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)的一對(duì)數(shù), ,繼續(xù)上面的除法繼續(xù)上面

14、的除法, ,直到大數(shù)被小數(shù)除盡直到大數(shù)被小數(shù)除盡, ,這時(shí)較小這時(shí)較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù). . 返回目錄返回目錄返回目錄返回目錄 (2) (2)割圓術(shù)割圓術(shù) 是數(shù)學(xué)上最重要的常數(shù)之一是數(shù)學(xué)上最重要的常數(shù)之一, ,我國(guó)古代數(shù)學(xué)家在割圓我國(guó)古代數(shù)學(xué)家在割圓術(shù)上取得了巨大的成就術(shù)上取得了巨大的成就. .通過(guò)學(xué)習(xí)割圓術(shù)通過(guò)學(xué)習(xí)割圓術(shù), ,同學(xué)們可以嘗試同學(xué)們可以嘗試著計(jì)算著計(jì)算的近似值的近似值. .特別將不足近似值和過(guò)剩近似值相結(jié)合特別將不足近似值和過(guò)剩近似值相結(jié)合, ,通過(guò)近似值的上下限通過(guò)近似值的上下限S S2 2n n S S S S2 2n n+(+(

15、S S2 2n n- -S Sn n)()(n n=6,12,).=6,12,). (3) (3)秦九韶算法秦九韶算法 秦九韶算法是求一元秦九韶算法是求一元n n次多項(xiàng)式的一種算法次多項(xiàng)式的一種算法, ,通過(guò)一次通過(guò)一次多項(xiàng)式的反復(fù)計(jì)算多項(xiàng)式的反復(fù)計(jì)算, ,逐步得出高次多項(xiàng)式的值逐步得出高次多項(xiàng)式的值, ,對(duì)于一個(gè)對(duì)于一個(gè)n n次次多項(xiàng)式多項(xiàng)式, ,只需做只需做n n次乘法和次乘法和n n次加法即可次加法即可. .返回目錄返回目錄 2. 2.中國(guó)古代數(shù)學(xué)中的算法案例學(xué)習(xí)的意義是什么中國(guó)古代數(shù)學(xué)中的算法案例學(xué)習(xí)的意義是什么? ? 我國(guó)古代數(shù)學(xué)中算法的內(nèi)容十分豐富我國(guó)古代數(shù)學(xué)中算法的內(nèi)容十分豐富,

16、 ,成就輝煌成就輝煌. .課本課本中的更相減損之術(shù)、割圓術(shù)、秦九韶算法，就是很好的代中的更相減損之術(shù)、割圓術(shù)、秦九韶算法，就是很好的代表表. .我國(guó)古代數(shù)學(xué)主要特征是算法化我國(guó)古代數(shù)學(xué)主要特征是算法化, ,現(xiàn)代信息技術(shù)的發(fā)展現(xiàn)代信息技術(shù)的發(fā)展也使算法煥發(fā)了生機(jī)也使算法煥發(fā)了生機(jī). .通過(guò)本部分的學(xué)習(xí)通過(guò)本部分的學(xué)習(xí), ,體會(huì)中國(guó)古代數(shù)體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界數(shù)學(xué)發(fā)展的貢獻(xiàn)學(xué)對(duì)世界數(shù)學(xué)發(fā)展的貢獻(xiàn), ,增強(qiáng)民族自豪感增強(qiáng)民族自豪感, ,努力學(xué)習(xí)努力學(xué)習(xí), ,為國(guó)為國(guó)家的發(fā)展貢獻(xiàn)力量家的發(fā)展貢獻(xiàn)力量. . 1. 1.學(xué)習(xí)更相減損之術(shù)與輾轉(zhuǎn)相除法時(shí)學(xué)習(xí)更相減損之術(shù)與輾轉(zhuǎn)相除法時(shí), ,要注意兩種方要注意兩

17、種方法的相通之處法的相通之處. . 2. 2.要深切體會(huì)劉徽的要深切體會(huì)劉徽的“割之彌細(xì)，所失彌少割之彌細(xì)，所失彌少”的思想的思想方法方法, ,利用正多邊形面積隨邊數(shù)增多利用正多邊形面積隨邊數(shù)增多, ,逐漸逼近圓面積來(lái)計(jì)逐漸逼近圓面積來(lái)計(jì)算圓周率算圓周率. 3. 3.學(xué)習(xí)秦九韶算法時(shí)學(xué)習(xí)秦九韶算法時(shí), ,注意通過(guò)分析秦九韶算法的運(yùn)注意通過(guò)分析秦九韶算法的運(yùn)算次數(shù)算次數(shù), ,感悟算法思想的優(yōu)越性和先進(jìn)性感悟算法思想的優(yōu)越性和先進(jìn)性, ,算法的關(guān)鍵是采算法的關(guān)鍵是采用逐步提出因式用逐步提出因式x x的方法對(duì)多項(xiàng)式進(jìn)行改寫(xiě)的方法對(duì)多項(xiàng)式進(jìn)行改寫(xiě). . 學(xué)習(xí)過(guò)程中應(yīng)注意研究分析教材中三個(gè)例子的算法設(shè)學(xué)習(xí)過(guò)程中應(yīng)注意研究分析教材中三個(gè)例子的算法設(shè)計(jì)思路計(jì)思路, ,體會(huì)算法的道理所在體會(huì)算法的道理所在. .比較一下第二個(gè)和第三個(gè)例