2015高中數學1.3 算法案例

1.3算法案例

第1課時輾轉相除法與更相減損術、秦九韶算法

敖苧教法分析明謀標分條解讀觀"效法”安

?三維目標

1.知識與技能

(1)理解輾轉相除法與更相減損術中蘊含的數學原理，并能根據這些原理進

行算法分析.

(2)基本能根據算法語句與程序框圖的知識設計完整的程序框圖并寫出算法

程序.

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

提高計算效率的實質.

2.過程與方法

(1)在輾轉相除法與更相減損術求最大公約數的學習過程中對比我們常見的

約分求公因式的方法，比較它們在算法上的區(qū)別，并從程序的學習中體會數學的

嚴謹，領會數學算法計算機處理的結合方式，初步掌握把數學算法轉化成計算機

語言的一般步驟.

(2)模仿秦九韶算法，體會古人計算構思的巧妙.

(3)通過對秦九韶算法的學習，了解中國古代數學家對數學的貢獻，充分認

識到我國文化歷史的悠久.通過對排序法的學習，領會數學計算與計算機計算的

區(qū)別，充分認識信息技術對數學的促進.

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

(1)通過閱讀中國古代數學中的算法案例，體會中國古代數學對世界數學發(fā)

展的貢獻.

(2)在學習古代數學家解決數學問題的方法的過程中培養(yǎng)嚴謹的邏輯思維能

力，在利用算法解決數學問題的過程中培養(yǎng)理性的精神和動手實踐的能力.

?重點難點

重點：理解輾轉相除法與更相減損術求最大公約數的方法及秦九韶算法的特

點.

難點：把輾轉相除法與更相減損術的方法轉換成程序框圖與程序語言.

褓希自主持學理數材自查自測畫"基礎”n上學

習區(qū)i

1.通過案例，進一步體會算法的思想.

2.理解輾轉相除法、更相減損術、秦九韶算法的原

課標解讀

理.（重點）

3.三種算法的框圖及程序應用.（難點）

知識”輾轉相除法

【問題導思】

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

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

23660

2|1830

31915

為止，然后把所有的除數連乘起來即為最大公約數.由于35,

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

2.觀察下列等式8251=6105X1+2146,那么8251與6105這兩個數的

公約數和6105與2146的公約數有什么關系？

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

也是8251的約數，故8251與6105的最大公約數也是6105與2146的最大公

約數.

輾轉相除法的算法步驟

第一步，給定兩個正整數〃八〃.

第二步，計算〃?除以〃所得的余數匚

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

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

--2|更相減損術

【問題導思】

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

最大公約數相等，反復利用這個原理，可求得98與63的最大公約數是多少？

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

=7,98與63的最大公約數為7.

更相減損術的算法步驟

第一步，任意給定兩個正整數，判斷它們是否都是偶數.若是,用復約簡；

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

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

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

這個數與約簡的數的乘積就是所求的最大公約數.

3j秦九韶算法

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

具體算法如下：

⑴計算最內層括號內一次多項式的值，即初=。/內斯T.

(2)由內向外逐層計算多項式的值，即

=

V2ViX~t~dn-2)

。3=。2》+即-3，

作?；犹骄亢献魈?/p>

破城雄師生互動提“知然"

究區(qū)I

用輾轉相除法求最大公約數

》例用輾轉相除法求228與1995的最大公約數.

【思路探究】使用輾轉相除法可根據m=nq+r,反復相除直到r=0為止.

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

228=1X171+57,

171=3X57,

???228與1995的最大公約數為57.

I規(guī)律方法I

利用輾轉相除法求給定的兩個數的最大公約數，即利用帶余除法，用數對中

較大的數除以較小的數，若余數不為零，則將余數和較小的數構成新的數對，再

利用帶余除法，直到大數被小數除盡，則這時的較小數就是原來兩個數的最大公

約數.

〉變武訓練

用輾轉相除法求779和209的最大公約數.

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

209=152X1+57,

152=57X2+38,

57=38X1+19,

38=19X2,

??.779與209的最大公約數為19.

：＜用更相減損術求最大公約數

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

【思路探究】解答本題可先將兩數約簡然后按更相減損術的步驟反復相減

直至得出結果.

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

的最大公約數.

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的最大公約數為11,則154與484的最大公約數為11X2=22.

I規(guī)律方法I

1.更相減損術進行的是減法運算，即輾轉相減，其步驟為若兩數同為偶數,

則可用2約簡后求最大公約數，也可不用2約簡直接求最大公約數.

2.由輾轉相除法求最大公約數的步驟較少，而更相減損術使用的是遞減運

算，運算簡易，便于操作，但步驟較多，兩種算法各有所長.

＞變直訓練

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

【解】用2約簡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的最大公約數為3X2=6.

秦九韶算法的應用

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

5,當x=3時的值.

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

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

。2,…，。7分別是多少，最后進行計算.

【自主解答】/(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.

當x=3時，多項式的值為11320.

I規(guī)律方法I

利用秦九韶算法計算多項式的值的關鍵是能正確地將所給多項式改寫，然后

由內向外逐次計算，由于后項計算用到前項的結果，故應認真、細心，確保中間

結果的準確性，若在多項式中有幾項不存在，可將這些項的系數看成0,即把這

些項看成0.Z.

＞變式訓練

用秦九韶算法計算多項式

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

【解】將?r)改寫為

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

由內向外依次計算一次多項式當x=2時的值，

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時，原多項式的值為0.

易辨易設辨析技能提

巧分辨解找辨誤圖“P3阱

升區(qū)I

對秦九韶算法中的運算次數理解錯誤

上典例

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

多項式當x=2時的值時，做了兒次乘法？兒次加法?

【錯解】根據秦九韶算法，把多項式改寫成如下形式式x)=((((x+2)x+3)x

+4)x+5)x+6.

按照從內到外的順序，依次計算一次多項式當x=2時的值：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次加法.

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

"2Xl+2=4”.因為用秦九韶算法計算多項式外)=?￡'+即一似…+

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

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

+3無論“是不是1，這次的乘法都是要進行的.

【防范措施】1.將多項式寫成一次多項式的形式時，如果多項式中〃次項

不存在，可將"次項看作0.Z.

2.直接法乘法運算的次數最多可達(〃；1〃,加法最多〃次,秦九韶算法通

過轉化把乘法運算的次數減少到最多n次，加法最多n次.

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

c

c

c

c

^

^

c

c

c

c

c

^

€

1.輾轉相除法與更相減損術都是求兩數最大公約數的方法.

輾轉相除法計算次數少，步驟簡捷，更相減損術計算次數多，步驟復雜，但

是更相減損術每一步的計算都是減法，比做除法運算要簡單一些，一般當數較小

時可以考慮用更相減損術，當數較大時可以考慮用輾轉相除法.

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

求值，關鍵是正確地將所給多項式改寫，然后由內向外計算，由于后項計算需用

到前項結果，故應認真、細心，確保結果的準確性.

當《雙基達標陵堂練生生互動達"雙標"uj/[

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

A.2B.10

C.30D.70

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

為70.

【答案】D

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

A.2B.3

C.4D.5

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

【答案】C

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

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

=2;

0=2X3+0=6;

02=6X3+1=19.

【答案】19

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

【解】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的最大公約數為9.

彳史后知能檢測部下測自我評估提“考舷,,整整個

一、選擇題

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

①輾轉相除法也叫歐幾里得算法；

②輾轉相除法的基本步驟是用較大的數除以較小的數；

③求最大公約數的方法，除輾轉相除法之外，沒有其他方法；

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

A.1個B.2個

C.3個D.4個

【解析】本題考查對輾轉相除法和更相減損術的理解與認識.③不正確，

因為除了輾轉相除法，還有其他方法，如更相減損術.

【答案】C

2.設計程序框圖，用秦九韶算法求多項式的值，主要用哪種結構實現

（）

A.順序結構B.條件結構

C.循環(huán)結構D.條件、順序結構

【解析】該種算法主要是由內到外計算

Vo=a,

<lt

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

故在求值時用到循環(huán)結構.

【答案】C

3.用秦九韶算法求多項式式幻=4/一?+2當x=3時的值時，需要進行的

乘法運算和加法運算的次數分別為（）

A.4,2B.5,3

C.5,2D.6,2

【解析】兒丫）=4/-f+2=（（（（4x）x）x-l）x）x+2,需5次乘法運算和2次

加法運算.

【答案】C

4.225與135的最大公約數是（）

A.5B.9

C.15D.45

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

135的最大公約數.

【答案】D

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

INPUTm,n

WHILFm<>n

IFm>nTHEN

m=m-n

ELSE

n=n-m

ENDIF

WEND

PRINTm

END

A.求m,n的最小公倍數

B.求m,n的最大公約數

C.求m被n除的商

。.求n除以m的余數

【解析】本程序當m,n不相等時，總是用較大的數減去較小的數，直到

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

【答案】B

二、填空題

6.464與272的最大公約數為.

【解析】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,最大公約數為1X16=16.

【答案】16

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

【解析】；152與92都是偶數，.??先兩次用2約簡得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.已知多項式函數f(x)=2x5—5x4—4X3+3X2—6X+7,當x=5時由秦九韶

算法v