1、§1.3算法案例(一)【明目標(biāo)、知重點(diǎn)】1理解輾轉(zhuǎn)相除法與更相減損術(shù)中的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)行算法分析2了解秦九韶算法及利用它計(jì)算提高計(jì)算效率的本質(zhì)3對(duì)簡(jiǎn)單的案例能設(shè)計(jì)程序框圖并寫出算法程序【填要點(diǎn)、記疑點(diǎn)】1輾轉(zhuǎn)相除法(1)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個(gè)正整數(shù)的最大公約數(shù)的古老而有效的算法(2)輾轉(zhuǎn)相除法的算法步驟第一步，給定兩個(gè)正整數(shù)m，n(m>n)第二步，計(jì)算m除以n所得的余數(shù)r.第三步，mn，nr.第四步，若r0，則m，n的最大公約數(shù)等于m；否則，返回第二步2更相減損術(shù)的運(yùn)算步驟第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)若是，用2約簡(jiǎn)；若不是，

2、執(zhí)行第二步第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)3秦九韶算法把一個(gè)n次多項(xiàng)式f(x)anxnan1xn1a1xa0改寫成如下形式：(anxan1)xan2)xa1)xa0，求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即v1anxan1，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即v2v1xan2，v3v2xan3，vnvn1xa0這樣，求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值【探要點(diǎn)、究所然】情境導(dǎo)學(xué)在小學(xué)，我們已經(jīng)學(xué)過(guò)求最大公約數(shù)的知識(shí)，利用找

3、公約數(shù)的方法來(lái)求最大公約數(shù)如果公約數(shù)比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它 們的最大公約數(shù)？比如求8 251與6 105的最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容探究點(diǎn)一輾轉(zhuǎn)相除法思考118與30的最大公約數(shù)是多少？你是怎樣得到的？答先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來(lái)即為最大公約數(shù)由于，所以，18與30的最大公約數(shù)是2×36.問(wèn)題如何求兩個(gè)正數(shù)8 251和6 105的最大公約數(shù)？思考2對(duì)于8 251與6 105這兩個(gè)數(shù)，由于其公有的質(zhì)因數(shù)較大，利用小學(xué)的方法求最大公約數(shù)就比較困難注意到8 2516 10

4、5×12 146，那么8 251與6 105這兩個(gè)數(shù)的公約數(shù)和6 105與2 146的公約數(shù)有什么關(guān)系？答顯然8 251的最大公約數(shù)也必是2 146的約數(shù)，同樣6 105與2 146的公約數(shù)也必是8 251的約數(shù)，所以8 251與6 105的最大公約數(shù)也是6 105與2 146的最大公約數(shù)思考3又6 1052 146×21 813，同理，6 105與2 146的公約數(shù)和2 146與1 813的公約數(shù)相等重復(fù)上述操作，你能得到8 251與6 105這兩個(gè)數(shù)的最大公約數(shù)嗎？答8 2516 105×12 146，6 1052 146×21 813，2 1461

5、 813×1333，1 813333×5148，333148×237，14837×40.最后的除數(shù)37是148和37的最大公約數(shù)，也是8 251與6 105的最大公約數(shù)反思與感悟上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法思考4(1)用輾轉(zhuǎn)相除法可以求兩個(gè)正整數(shù)m，n的最大公約數(shù)，那么用什么邏輯結(jié)構(gòu)來(lái)設(shè)計(jì)算法？其算法步驟如何設(shè)計(jì)？(2)該算法的程序框圖如何表示？該程序框圖對(duì)應(yīng)的程序如何表述？(3)如果用當(dāng)型循環(huán)結(jié)構(gòu)設(shè)計(jì)算法，正整數(shù)m，n的最大公約數(shù)的程序框圖和程序分別如何表示？答(1)用循環(huán)結(jié)構(gòu)設(shè)計(jì)算法，算法如下：第一步，給定兩個(gè)正整數(shù)

6、m，n(m>n)第二步，計(jì)算m除以n所得的余數(shù)r.第三步，mn，nr.第四步，若r0，則m，n的最大公約數(shù)等于m；否則，返回第二步(2)程序框圖：程序：input m,ndor=m mod nm=nn=rloop until r=0print mend探究點(diǎn)二更相減損術(shù)思考1設(shè)兩個(gè)正整數(shù)m>n，若mnk，則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等反復(fù)利用這個(gè)原理，可求得98與63的最大公約數(shù)為多少？答由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，得986335，633528，35287，28721，21714，1477.可知98與63的最大公約數(shù)為7.小結(jié)上述求兩個(gè)正整

7、數(shù)的最大公約數(shù)的方法稱為更相減損術(shù)思考2(1)用更相減損術(shù)可以求兩個(gè)正整數(shù)m，n的最大公約數(shù)，那么用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟如何設(shè)計(jì)？答(1)用循環(huán)結(jié)構(gòu)設(shè)計(jì)算法，算法如下：第一步，任意給定兩個(gè)正整數(shù)m，n(m>n)第二步，計(jì)算mn所得的差k.第三步，比較n與k的大小，其中大者用m表示，小者用n表示第四步，若mn，則m，n的最大公約數(shù)等于m；否則，返回第二步(2)該算法的程序框圖如何表示？該程序框圖對(duì)應(yīng)的程序如何表述？答程序框圖：程序：input m,nwhile m<>nk=m-nif n>k thenm=nn=kelsem=kend ifwendprint

8、mend例1分別用輾轉(zhuǎn)相除法和更相減損術(shù)求261和319的最大公約數(shù)解輾轉(zhuǎn)相除法：319÷2611(余58)，261÷584(余29)，58÷292(余0)，所以319與261的最大公約數(shù)為29.更相減損術(shù)：31926158，26158203，20358145，1455887，875829，582929，29290，所以319與261的最大公約數(shù)是29.反思與感悟1.利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì)，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來(lái)兩個(gè)數(shù)的

9、最大公約數(shù)2利用更相減損術(shù)求兩個(gè)正整數(shù)的最大公約數(shù)的一般步驟是首先判斷兩個(gè)正整數(shù)是否都是偶數(shù)若是，用2約簡(jiǎn)也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結(jié)果跟蹤訓(xùn)練1用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更相減損術(shù)檢驗(yàn)?zāi)愕慕Y(jié)果解8036×28，368×44,84×20，即80與36的最大公約數(shù)是4.驗(yàn)證：80÷24036÷21840÷22018÷292091111929277255233212111×2×24所以80與36的最大公約數(shù)為4.探究點(diǎn)三秦九韶算法的基本思想思考1怎樣計(jì)算多項(xiàng)式f(x)x5

10、x4x3x2x1當(dāng)x5時(shí)的值呢？統(tǒng)計(jì)所做的計(jì)算的種類及計(jì)算次數(shù)分別是什么？答f(5)55545352513 906.根據(jù)我們的計(jì)算統(tǒng)計(jì)可以得出我們共需要10次乘法運(yùn)算，5次加法運(yùn)算思考2我們把多項(xiàng)式變形為f(x)(x1)x1)x1)x1)x1，再統(tǒng)計(jì)一下計(jì)算當(dāng)x5時(shí)的計(jì)算的種類及計(jì)算次數(shù)分別是什么？答從里往外計(jì)算僅需4次乘法和5次加法運(yùn)算即可得出結(jié)果小結(jié)思考2中的計(jì)算比問(wèn)題1中的計(jì)算顯然少了6次乘法運(yùn)算這種算法就叫秦九韶算法一般地，f(x)anxnan1xn1an2xn2a1xa0(anxn1an1xn2an2xn3a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan

11、2)xa1)xa0.求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即v1anxan1，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即v2v1xan2，v3v2xan3，vnvn1xa0，這樣，求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值例2已知一個(gè)5次多項(xiàng)式為f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x5時(shí)的值解將f(x)改寫為f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由內(nèi)向外依次計(jì)算一次多項(xiàng)式當(dāng)x5時(shí)的值：v04；v14×5222；v222×53.5113.5；v3113.5×52.6564.9；v4

12、564.9×51.72 826.2；v52 826.2×50.814 130.2.當(dāng)x5時(shí)，多項(xiàng)式的值等于14 130.2.反思與感悟秦九韶算法步驟：跟蹤訓(xùn)練2用秦九韶算法求多項(xiàng)式f(x)7x76x65x54x43x32x2x當(dāng)x3時(shí)的值解f(x)(7x6)x5)x4)x3)x2)x1)x所以有v07，v17×3627，v227×3586，v386×34262，v4262×33789，v5789×322 369，v62 369×317 108，v77 108×321 324.故當(dāng)x3時(shí)，多項(xiàng)式f(x)7x

13、76x65x54x43x32x2x的值為21 324.【當(dāng)堂測(cè)、查疑缺】1輾轉(zhuǎn)相除法與更相減損術(shù)是求最大公約數(shù)的常用方法，從計(jì)算結(jié)果形式上看，輾轉(zhuǎn)相除法以_得到結(jié)果，更相減損術(shù)則以_而得到結(jié)果答案相除余數(shù)為零減數(shù)與差相等2用輾轉(zhuǎn)相除法求85與51的最大公約數(shù)時(shí)，需要做除法的次數(shù)為_(kāi)答案3解析8551×134，5134×117，3417×20.3已知f(x)2x3x3，用秦九韶算法求當(dāng)x3時(shí)v2的值解f(x)2x3x32x30·x2x3(2x0)x1)x3，v02，v12×306，v26×3119.【呈重點(diǎn)、現(xiàn)規(guī)律】1輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用