2015高中數(shù)學(xué)1.3 算法案例

1.3算法案例

第1課時(shí)輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法

敖苧教法分析明謀標(biāo)分條解讀觀"效法”安

?三維目標(biāo)

1.知識(shí)與技能

(1)理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊(yùn)含的數(shù)學(xué)原理，并能根據(jù)這些原理進(jìn)

行算法分析.

(2)基本能根據(jù)算法語(yǔ)句與程序框圖的知識(shí)設(shè)計(jì)完整的程序框圖并寫(xiě)出算法

程序.

(3)了解秦九韶算法的計(jì)算過(guò)程，并理解利用秦九韶算法可以減少計(jì)算次數(shù)

提高計(jì)算效率的實(shí)質(zhì).

2.過(guò)程與方法

(1)在輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的學(xué)習(xí)過(guò)程中對(duì)比我們常見(jiàn)的

約分求公因式的方法，比較它們?cè)谒惴ㄉ系膮^(qū)別，并從程序的學(xué)習(xí)中體會(huì)數(shù)學(xué)的

嚴(yán)謹(jǐn)，領(lǐng)會(huì)數(shù)學(xué)算法計(jì)算機(jī)處理的結(jié)合方式，初步掌握把數(shù)學(xué)算法轉(zhuǎn)化成計(jì)算機(jī)

語(yǔ)言的一般步驟.

(2)模仿秦九韶算法，體會(huì)古人計(jì)算構(gòu)思的巧妙.

(3)通過(guò)對(duì)秦九韶算法的學(xué)習(xí)，了解中國(guó)古代數(shù)學(xué)家對(duì)數(shù)學(xué)的貢獻(xiàn)，充分認(rèn)

識(shí)到我國(guó)文化歷史的悠久.通過(guò)對(duì)排序法的學(xué)習(xí)，領(lǐng)會(huì)數(shù)學(xué)計(jì)算與計(jì)算機(jī)計(jì)算的

區(qū)別，充分認(rèn)識(shí)信息技術(shù)對(duì)數(shù)學(xué)的促進(jìn).

3.情感、態(tài)度與價(jià)值觀

(1)通過(guò)閱讀中國(guó)古代數(shù)學(xué)中的算法案例，體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界數(shù)學(xué)發(fā)

展的貢獻(xiàn).

(2)在學(xué)習(xí)古代數(shù)學(xué)家解決數(shù)學(xué)問(wèn)題的方法的過(guò)程中培養(yǎng)嚴(yán)謹(jǐn)?shù)倪壿嬎季S能

力，在利用算法解決數(shù)學(xué)問(wèn)題的過(guò)程中培養(yǎng)理性的精神和動(dòng)手實(shí)踐的能力.

?重點(diǎn)難點(diǎn)

重點(diǎn)：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法及秦九韶算法的特

點(diǎn).

難點(diǎn)：把輾轉(zhuǎn)相除法與更相減損術(shù)的方法轉(zhuǎn)換成程序框圖與程序語(yǔ)言.

褓希自主持學(xué)理數(shù)材自查自測(cè)畫(huà)"基礎(chǔ)”n上學(xué)

習(xí)區(qū)i

1.通過(guò)案例，進(jìn)一步體會(huì)算法的思想.

2.理解輾轉(zhuǎn)相除法、更相減損術(shù)、秦九韶算法的原

課標(biāo)解讀

理.（重點(diǎn)）

3.三種算法的框圖及程序應(yīng)用.（難點(diǎn)）

知識(shí)”輾轉(zhuǎn)相除法

【問(wèn)題導(dǎo)思】

1.36與60的最大公約數(shù)是多少？你是如何得到的？

【提示】先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)

23660

2|1830

31915

為止，然后把所有的除數(shù)連乘起來(lái)即為最大公約數(shù).由于35,

故36與60的最大公約數(shù)為2X2X3=12.

2.觀察下列等式8251=6105X1+2146,那么8251與6105這兩個(gè)數(shù)的

公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？

【提示】8251的最大約數(shù)是2146的約數(shù)，同樣6105與2146的公約數(shù)

也是8251的約數(shù)，故8251與6105的最大公約數(shù)也是6105與2146的最大公

約數(shù).

輾轉(zhuǎn)相除法的算法步驟

第一步，給定兩個(gè)正整數(shù)〃八〃.

第二步，計(jì)算〃?除以〃所得的余數(shù)匚

第三步，m=n,n=r.

第四步，若r=。，則加、”的最大公約數(shù)等于如否則返回第三步.

--2|更相減損術(shù)

【問(wèn)題導(dǎo)思】

設(shè)兩個(gè)正整數(shù)”?>〃(/">〃)，若m—n=k,則加與"的最大公約數(shù)和〃與k的

最大公約數(shù)相等，反復(fù)利用這個(gè)原理，可求得98與63的最大公約數(shù)是多少？

【提示198-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7

=7,98與63的最大公約數(shù)為7.

更相減損術(shù)的算法步驟

第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù).若是,用復(fù)約簡(jiǎn)；

若不是，執(zhí)行第二步.

第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以

大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直到所得的差與減數(shù)相等為止,則這個(gè)數(shù)(等數(shù))或

這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù).

3j秦九韶算法

將/(x)改寫(xiě)成如下形式：/(x)=(-"((a?x+a?-i)x+a?-2)xH---\-a^x+ao.

具體算法如下：

⑴計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即初=。/內(nèi)斯T.

(2)由內(nèi)向外逐層計(jì)算多項(xiàng)式的值，即

=

V2ViX~t~dn-2)

。3=。2》+即-3，

作?；?dòng)探究合作探

破城雄師生互動(dòng)提“知然"

究區(qū)I

用輾轉(zhuǎn)相除法求最大公約數(shù)

》例用輾轉(zhuǎn)相除法求228與1995的最大公約數(shù).

【思路探究】使用輾轉(zhuǎn)相除法可根據(jù)m=nq+r,反復(fù)相除直到r=0為止.

【自主解答】1995=8X228+171,

228=1X171+57,

171=3X57,

???228與1995的最大公約數(shù)為57.

I規(guī)律方法I

利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中

較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì)，再

利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來(lái)兩個(gè)數(shù)的最大公

約數(shù).

〉變武訓(xùn)練

用輾轉(zhuǎn)相除法求779和209的最大公約數(shù).

【解】?“鄉(xiāng):209X3+152,

209=152X1+57,

152=57X2+38,

57=38X1+19,

38=19X2,

??.779與209的最大公約數(shù)為19.

：＜用更相減損術(shù)求最大公約數(shù)

，例用更相減損術(shù)求154,484的最大公約數(shù).

【思路探究】解答本題可先將兩數(shù)約簡(jiǎn)然后按更相減損術(shù)的步驟反復(fù)相減

直至得出結(jié)果.

【自主解答】154+2=77,484+2=242,下面用更相減損術(shù)，求77與242

的最大公約數(shù).

242-77=165,165-77=88,88-77=11,77-11=66,66-11=55,55-11=

44,44-11=33,33-11=22,22-11=11,

故77與242的最大公約數(shù)為11,則154與484的最大公約數(shù)為11X2=22.

I規(guī)律方法I

1.更相減損術(shù)進(jìn)行的是減法運(yùn)算，即輾轉(zhuǎn)相減，其步驟為若兩數(shù)同為偶數(shù),

則可用2約簡(jiǎn)后求最大公約數(shù)，也可不用2約簡(jiǎn)直接求最大公約數(shù).

2.由輾轉(zhuǎn)相除法求最大公約數(shù)的步驟較少，而更相減損術(shù)使用的是遞減運(yùn)

算，運(yùn)算簡(jiǎn)易，便于操作，但步驟較多，兩種算法各有所長(zhǎng).

＞變直訓(xùn)練

用更相減損術(shù)求576與246的最大公約數(shù).

【解】用2約簡(jiǎn)576和246得288與123.

288-123=165,165-123=42,

123-42=81,81-42=39,

42-39=3,39-3=36,36-3=33,

33-3=30,30-3=27,

27-3=24,24-3=21,

21-3=18,18-3=15,

15-3=12,12-3=9,

9-3=6,6-3=3.

.'.576與246的最大公約數(shù)為3X2=6.

秦九韶算法的應(yīng)用

，例用秦九韶算法求多項(xiàng)式f(x)=lx1—6x6+4x4+3x3—2X2+X—

5,當(dāng)x=3時(shí)的值.

【思路探究】解答本題首先要將原多項(xiàng)式化成

f(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+l)x-5的形式.其次再弄清v。，V\,

。2,…，。7分別是多少，最后進(jìn)行計(jì)算.

【自主解答】/(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+l)x-5,

伙)=7,01=7X3-6=15;15X3+0=45;03=45X3+4=139;%=

139X3+3=420；05=420X3-2=1258；v6=1258X3+1=3775；07=3775X3

-5=11320.

當(dāng)x=3時(shí)，多項(xiàng)式的值為11320.

I規(guī)律方法I

利用秦九韶算法計(jì)算多項(xiàng)式的值的關(guān)鍵是能正確地將所給多項(xiàng)式改寫(xiě)，然后

由內(nèi)向外逐次計(jì)算，由于后項(xiàng)計(jì)算用到前項(xiàng)的結(jié)果，故應(yīng)認(rèn)真、細(xì)心，確保中間

結(jié)果的準(zhǔn)確性，若在多項(xiàng)式中有幾項(xiàng)不存在，可將這些項(xiàng)的系數(shù)看成0,即把這

些項(xiàng)看成0.Z.

＞變式訓(xùn)練

用秦九韶算法計(jì)算多項(xiàng)式

f(x)=x6-12?+60x4-160?+240x2-192x+64,當(dāng)x=2時(shí)的值.

【解】將?r)改寫(xiě)為

f(x)=(((((x-12)x+60)x-160)x+240)x-192)x+64,

由內(nèi)向外依次計(jì)算一次多項(xiàng)式當(dāng)x=2時(shí)的值，

00=1，

0=1X2-12=-10,

6=-10X2+60=40,

v3=40X2-160=-80,

。4=-80X2+240=80,

05=80X2-192=-32,

-32X2+64=0.

.\/(2)=0,即x=2時(shí)，原多項(xiàng)式的值為0.

易辨易設(shè)辨析技能提

巧分辨解找辨誤圖“P3阱

升區(qū)I

對(duì)秦九韶算法中的運(yùn)算次數(shù)理解錯(cuò)誤

上典例

已知/(X)=X5+2X4+3X3+4X2+5X+6,用秦九韶算法求這個(gè)

多項(xiàng)式當(dāng)x=2時(shí)的值時(shí)，做了兒次乘法？?jī)捍渭臃?

【錯(cuò)解】根據(jù)秦九韶算法，把多項(xiàng)式改寫(xiě)成如下形式式x)=((((x+2)x+3)x

+4)x+5)x+6.

按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)x=2時(shí)的值：01=2+2=4;

。2=20+3=11；03=2勿+4=26；。4=2力+5=57;0=204+6=120.

顯然，在V\中未做乘法，只做了1次加法；在火，。3，。4，中各做了1

次加法，1次乘法.因此，共做了4次乘法，5次加法.

【錯(cuò)因分析】在⑦中雖然“0=2+2=4"，而計(jì)算機(jī)還是做了1次乘法

"2Xl+2=4”.因?yàn)橛们鼐派厮惴ㄓ?jì)算多項(xiàng)式外)=?￡'+即一似…+

“ix+“0當(dāng)x=xo時(shí)的值時(shí)，首先將多項(xiàng)式改寫(xiě)成/(x)=(…(4"X+a”-i)x+…+a\)x

+ao,然后再計(jì)算V\=anx+an-\,v^=v\x+an-2,V3=V2x+an-3,…，vn=vn-\x

+3無(wú)論“是不是1，這次的乘法都是要進(jìn)行的.

【防范措施】1.將多項(xiàng)式寫(xiě)成一次多項(xiàng)式的形式時(shí)，如果多項(xiàng)式中〃次項(xiàng)

不存在，可將"次項(xiàng)看作0.Z.

2.直接法乘法運(yùn)算的次數(shù)最多可達(dá)(〃；1〃,加法最多〃次,秦九韶算法通

過(guò)轉(zhuǎn)化把乘法運(yùn)算的次數(shù)減少到最多n次，加法最多n次.

【正解】由以上分析，共做了5次乘法，5次加法.

c

c

c

c

^

^

c

c

c

c

c

^

€

1.輾轉(zhuǎn)相除法與更相減損術(shù)都是求兩數(shù)最大公約數(shù)的方法.

輾轉(zhuǎn)相除法計(jì)算次數(shù)少，步驟簡(jiǎn)捷，更相減損術(shù)計(jì)算次數(shù)多，步驟復(fù)雜，但

是更相減損術(shù)每一步的計(jì)算都是減法，比做除法運(yùn)算要簡(jiǎn)單一些，一般當(dāng)數(shù)較小

時(shí)可以考慮用更相減損術(shù)，當(dāng)數(shù)較大時(shí)可以考慮用輾轉(zhuǎn)相除法.

2.用秦九韶算法可大大降低乘法的運(yùn)算次數(shù)，提高了運(yùn)算速度.用此方法

求值，關(guān)鍵是正確地將所給多項(xiàng)式改寫(xiě)，然后由內(nèi)向外計(jì)算，由于后項(xiàng)計(jì)算需用

到前項(xiàng)結(jié)果，故應(yīng)認(rèn)真、細(xì)心，確保結(jié)果的準(zhǔn)確性.

當(dāng)《雙基達(dá)標(biāo)陵堂練生生互動(dòng)達(dá)"雙標(biāo)"uj/[

1.490和910的最大公約數(shù)為()

A.2B.10

C.30D.70

【解析】910=490X1+420,490=420X1+70,420=70X6,故最大公約數(shù)

為70.

【答案】D

2.用更相減損術(shù)求294和84的最大公約數(shù)時(shí)，需做減法的次數(shù)是()

A.2B.3

C.4D.5

【解析】294-84=210,210-84=126,126-84=42,84-42=42.

【答案】C

3.用秦九韶算法求/(X)=2/+X—3當(dāng)x=3時(shí)的值必=.

【解析】/(x)=((2x+0)x+l)x-3,

=2;

0=2X3+0=6;

02=6X3+1=19.

【答案】19

4.用更相減損術(shù)求288與153的最大公約數(shù).

【解】288-153=135,153-135=18,135-18=117,117-18=99,99-18

=81,81-18=63,63-18=45,45-18=27,27-18=9,18-9=9.

???288與153的最大公約數(shù)為9.

彳史后知能檢測(cè)部下測(cè)自我評(píng)估提“考舷,,整整個(gè)

一、選擇題

1.下列說(shuō)法中正確的有()

①輾轉(zhuǎn)相除法也叫歐幾里得算法；

②輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)；

③求最大公約數(shù)的方法，除輾轉(zhuǎn)相除法之外，沒(méi)有其他方法；

④編寫(xiě)輾轉(zhuǎn)相除法的程序，要用到循環(huán)語(yǔ)句.

A.1個(gè)B.2個(gè)

C.3個(gè)D.4個(gè)

【解析】本題考查對(duì)輾轉(zhuǎn)相除法和更相減損術(shù)的理解與認(rèn)識(shí).③不正確，

因?yàn)槌溯氜D(zhuǎn)相除法，還有其他方法，如更相減損術(shù).

【答案】C

2.設(shè)計(jì)程序框圖，用秦九韶算法求多項(xiàng)式的值，主要用哪種結(jié)構(gòu)實(shí)現(xiàn)

（）

A.順序結(jié)構(gòu)B.條件結(jié)構(gòu)

C.循環(huán)結(jié)構(gòu)D.條件、順序結(jié)構(gòu)

【解析】該種算法主要是由內(nèi)到外計(jì)算

Vo=a,

<lt

??=以-「即+斯-《伙=1,2,…

故在求值時(shí)用到循環(huán)結(jié)構(gòu).

【答案】C

3.用秦九韶算法求多項(xiàng)式式幻=4/一?+2當(dāng)x=3時(shí)的值時(shí)，需要進(jìn)行的

乘法運(yùn)算和加法運(yùn)算的次數(shù)分別為（）

A.4,2B.5,3

C.5,2D.6,2

【解析】?jī)貉荆?4/-f+2=（（（（4x）x）x-l）x）x+2,需5次乘法運(yùn)算和2次

加法運(yùn)算.

【答案】C

4.225與135的最大公約數(shù)是（）

A.5B.9

C.15D.45

【解析】??,225=135X1+90,135=90X1+45,90=45X2,，45是225與

135的最大公約數(shù).

【答案】D

5.下面一段程序的目的是（）

INPUTm,n

WHILFm<>n

IFm>nTHEN

m=m-n

ELSE

n=n-m

ENDIF

WEND

PRINTm

END

A.求m,n的最小公倍數(shù)

B.求m,n的最大公約數(shù)

C.求m被n除的商

。.求n除以m的余數(shù)

【解析】本程序當(dāng)m,n不相等時(shí)，總是用較大的數(shù)減去較小的數(shù)，直到

相等時(shí)跳出循環(huán)，顯然是“更相減損術(shù)”.故選8.

【答案】B

二、填空題

6.464與272的最大公約數(shù)為.

【解析】464^16=29,2724-16=17,29-17=12,17-12=5,12-5=7,7-5=

2,5-2=3,3-2=1,2-1=1,最大公約數(shù)為1X16=16.

【答案】16

7.用更相減損術(shù)求152與92的最大公約數(shù)時(shí)，需要做減法的次數(shù)是

【解析】；152與92都是偶數(shù)，.??先兩次用2約簡(jiǎn)得38與23,又38-

23=15,

23-15=8,

15-8=7,

8-7=1,

7-1=6,

6-1=5,

5-1=4,

4-1=3,

3-1=2,

2-1=1,

故要用10次減法.

【答案】10

8.已知多項(xiàng)式函數(shù)f(x)=2x5—5x4—4X3+3X2—6X+7,當(dāng)x=5時(shí)由秦九韶

算法v