人教A數(shù)學(xué)必修三教案學(xué)案1.3 算法案例

1.3算法案例

【教學(xué)目標(biāo)】：

i.理解輾轉(zhuǎn)相除法與更相減損術(shù)中蘊含的數(shù)學(xué)原理，并能根據(jù)這些原理進行算法分析。

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

【教學(xué)重難點】：

重點：理解輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法。

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

【教學(xué)過程】：

情境導(dǎo)入：

L教師首先提出問題：在初中，我們已經(jīng)學(xué)過求最大公約數(shù)的知識，你能求出18與30

的公約數(shù)嗎？

2.接著教師進一步提出問題，我們都是利用找公約數(shù)的方法來求最大公約數(shù)，如果公約數(shù)

比較大而且根據(jù)我們的觀察又不能得到一些公約數(shù)，我們又應(yīng)該怎樣求它們的最大公約數(shù)？

比如求8251與6105的最大公約數(shù)？這就是我們這一堂課所要探討的內(nèi)容。

新知探究：

1.輾轉(zhuǎn)相除法

例1求兩個正數(shù)8251和6105的最大公約數(shù)。

（分析：8251與6105兩數(shù)都比較大，而且沒有明顯的公約數(shù)，如能把它們都變小一點，

根據(jù)已有的知識即可求出最大公約數(shù)）

解:8251=6105X1+2146

顯然8251的最大公約數(shù)也必是2146的約數(shù)，同樣6105與2146的公約數(shù)也必是8251的

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

6105=2146X2+1813

2146=1813X1+333

1813=333X5+148

333=148X2+37

148=37X4+0

則37為8251與6105的最大公約數(shù)。

以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公

元前300年左右首先提出的。利用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：

第一步：用較大的數(shù)m除以較小的數(shù)n得到一個商q。和一個余數(shù)r。；

第二步：若r0=0,則n為m,n的最大公約數(shù)；若r°￥0,則用除數(shù)n除以余數(shù)r0得到一

個商卬和一個余數(shù)n；

第三步：若n=0,貝為m,n的最大公約數(shù)；若nWO,則用除數(shù)r。除以余數(shù)n得到一

個商qz和一個余數(shù)r2;

依次計算直至r,.=0,此時所得到的r,rl即為所求的最大公約數(shù)。

練習(xí)：利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù)（答案：53）

2.更相減損術(shù)

我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。

-2-

更相減損術(shù)求最大公約數(shù)的步驟如下：可半者半之，不可半者，副置分母?子之?dāng)?shù)，以少

減多，更相減損，求其等也，以等數(shù)約之。

翻譯出來為：

第一步：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第

二步。

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

繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)(等數(shù))就是所求的最大公約數(shù)。

例2用更相減損術(shù)求98與63的最大公約數(shù).

解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減，即：98-63=35

63—35=28

35-28=7

28—7=21

21-7=14

14-7=7

所以，98與63的最大公約數(shù)是7。

練習(xí)：用更相減損術(shù)求兩個正數(shù)84與72的最大公約數(shù)。(答案：12)

比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：

(1)都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主,

計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別

較明顯。

(2)從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損

術(shù)則以減數(shù)與差相等而得到

3.秦九韶算法

秦九韶計算多項式的方法

_,

/(x)=a,x*+a,_1x*+…+叱+。0

=+??+(jj)x+a0

=((%x"7+仇_/7+-+a2)x+4])x+4

=(…((％x+%、)x++…+&)+%

令v*=(??((%X+4z)X+a7)X+…則有[先=打_11+44,

其中上=L2「叱這樣，我們便可由力依次求出匕.馬,匕；

%=3+4-1,

V2=匕不+%-2，

v3=v2x+a_j.

七=%/+%

顯然，用秦九韶算法求n次多項式的值時只需要做n次乘法和n次加法運算

4.進位制

-3-

進位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值.可使用數(shù)字符

號的個數(shù)稱為基數(shù)，基數(shù)為n,即可稱n進位制，簡稱n進制.現(xiàn)在最常用的是十進制，通常

使用10個阿拉伯?dāng)?shù)字0-9進行記數(shù).

對于任何一個數(shù)，我們可以用不同的進位制來表示.比如：十進數(shù)57,可以用二進制

表示為111001,也可以用八進制表示為71、用十六進制表示為39,它們所代表的數(shù)值都是一

樣的.

表示各種進位制數(shù)一般在數(shù)字右下腳加注來表示，如111001(2)表示二進制數(shù),34(5)表示

5進制數(shù).

(1).k進制轉(zhuǎn)換為十進制的方法：

a3

a；1aAia…a,.氣入)=ux上H------l-a3xJt+atxi4-a0

(2).十進制轉(zhuǎn)化為k進制數(shù)b的步驟為：

第一步，將給定的十進制整數(shù)除以基數(shù)k,余數(shù)便是等值的k進制的最低位；

第二步，將上一步的商再除以基數(shù)k,余數(shù)便是等值的k進制數(shù)的次低位；

第三步，重復(fù)第二步，直到最后所得的商等于0為止，各次所得的余數(shù)，便是k進

制各位的數(shù)，最后一次余數(shù)是最高位，即除k取余法.

要點詮釋：

1、在k進制中，具有k個數(shù)字符號.如二進制有0,1兩個數(shù)字.

2、在k進制中，由低位向高位是按“逢k進一”的規(guī)則進行計數(shù).

3、非k進制數(shù)之間的轉(zhuǎn)化一般應(yīng)先轉(zhuǎn)化成十進制，再將這個十進制數(shù)轉(zhuǎn)化為另一種

進制的數(shù)，有的也可以相互轉(zhuǎn)化.

【反饋測評】：

1.求324、243、135這三個數(shù)的最大公約數(shù)。

求三個數(shù)的最大公約數(shù)可以先求出兩個數(shù)的最大公約數(shù)，第三個數(shù)與前兩個數(shù)的最大公約

數(shù)的最大公約數(shù)即為所求。

2.用更相減損術(shù)求98與63的最大公約數(shù)

解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減

98-63=35

63-35=28

35-28=7

28-7=21

21-7=21

14-7=7

所以，98和63的最大公約數(shù)等于7

3.已知一個五次多項式為f(x)=5X5+2X4+3.5/-2.6/+1.7x-0.8用秦九韶算法求

這個多項式當(dāng)x=5的值。

解：將多項式變形：/(x)=((((5x+2)x+3.5)x—2.6)x+1.7)x—0.8按由里到外的順序,

依此計算一次多項式當(dāng)x=5時的值：

%=5,匕=5x5+2=27,v2=27x5+3.5=138.5,v3=138.5x5—2.6=689.9

為=689.9x5+1.7=3451.2,%=%51.2x5—0.8=17255.2所以，當(dāng)x二5時，多

-4-

項式的值等于17255.2

4.將二進制數(shù)110011⑵化成十進制數(shù)

解：根據(jù)進位制的定義可知

110011(2)=1X25+1X24+0X23+0X22+1X2'+1X2()

=1x32+1x16+1x2+1

=51

所以，110011⑵=51。

【板書設(shè)計】：

1.3算法案例

一、輾轉(zhuǎn)相除法三、秦九韶算法五、反饋測評：小結(jié)

例1

作業(yè)

二、更相減損術(shù)四、進位制

例2

-5-

1.3算法案例

課前預(yù)習(xí)學(xué)案

一、預(yù)習(xí)目標(biāo)

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

2、理解秦九韶算法的思想。

二、預(yù)習(xí)內(nèi)容

什么是進位制？最常見的進位制是什么？除此之外還有哪些常見的進位制？請舉例說

明.

三、提出疑惑

思考：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？

課內(nèi)探究學(xué)案

一、學(xué)習(xí)目標(biāo)

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

2.會利用秦九韶算法求多項式的值。

3.各進位制之間能靈活轉(zhuǎn)化。

二、學(xué)習(xí)重難點：

重點：輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的方法和秦九韶算法求多項式的值。

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

三、學(xué)習(xí)過程

輾轉(zhuǎn)相除法思路：可以利用除法將大數(shù)化小,找兩數(shù)的最大公約數(shù).（適于兩數(shù)較大時）

⑴用較大的數(shù)m除以較小的數(shù)n得到一個商S。和一個余數(shù)R。；

⑵若a=0,則n為m,n的最大公約數(shù)；若9W0,則用除數(shù)n除以余數(shù)凡得到一個?

和一個余數(shù)飛；（3）若凡=0,則叫為m,n的最大公約數(shù);若4#0,則用除數(shù)&除以余數(shù)曷得

到一個商52和一個余數(shù)R2；……依次計算直至R“=0,此時所得到的即為所求的最大公

約數(shù).

例題1：求兩個正數(shù)1424和801的最大公約數(shù).

①以上我們求最大公約數(shù)的方法就是輾轉(zhuǎn)相除法，也叫歐幾里德算法.

②由上述步驟可以看出，輾轉(zhuǎn)相除法中的除法是一個反復(fù)執(zhí)行的步驟，且執(zhí)行次數(shù)由余數(shù)

是否等于0來決定,所以可把它看成一循環(huán)體,寫出輾轉(zhuǎn)相除法完整的程序框圖和程序語言.

教學(xué)更相減損術(shù)：我國早期也有求最大公約數(shù)問題的算法，就是更相減損術(shù).在《九章

算術(shù)》中有更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母?子之?dāng)?shù)，

以少減多，更相減損，求其等也，以等數(shù)約之.

-6-

翻譯為：(1)任意給出兩個正數(shù)；判斷它們是否都是偶數(shù).若是，用2約簡；若不是，

執(zhí)行第二步.

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

數(shù).繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)(等數(shù))就是所求的最

大公約數(shù).

例題2.用更相減損術(shù)求91和49的最大公約數(shù).

秦九韶算法：

(1)設(shè)計求多項式一5——4/+3--6x+7當(dāng)x=5時的值的算法，并寫出

程序。

(2)有沒有更高效的算法？能否探求更好的算法，來解決任意多項式的求解問題？

引導(dǎo)學(xué)生把多項式變形為：

/(X)=2x5-5x4-4x3+3x2-6x-7

—((((2x-5)A?—4)x+3)x—6)x+7

并提問：從內(nèi)到外，如果把每一個括號都看成一個常數(shù)，那么變形后的式子中有哪些“一

次式”？x的系數(shù)依次是什么？

用秦九韶算法求多項式的值，與多項式組成有直接關(guān)系嗎？用秦九韶算法計算上述多項式

的值，需要多少次乘法運算和多少次加法運算？秦九韶算法適用于一般的多項式

nn

/(x)=anx+an_tx-'+■■■+a,x+a0的求值問題嗎？

怎樣用程序框圖表示秦九韶算法？觀察秦九韶算法的數(shù)學(xué)模型，計算也時要用到的值,

若令"。=,我們可以得到下面的遞推公式：

v=a

<_0〃n(4=1,2,??⑼

\yk=vk_}x+an_k這是一個在秦九韶算法中反復(fù)執(zhí)行的步驟，可以用循環(huán)結(jié)

構(gòu)來實現(xiàn)。請畫出程序框圖。

例題3.已知一個五次多項式為/(幻=5/+2d+3.5/-2.6/+1.7尤一0.8用秦九韶

-7-

算法求這個多項式當(dāng)x=5的值。

進位制：

我們了解十進制嗎？所謂的十進制，它是如何構(gòu)成的？其它進位制的數(shù)又是如何的呢？

進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的記數(shù)系統(tǒng)。進位制是一種記數(shù)方式，用有限的數(shù)

字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為n,即可稱n進位

制，簡稱n進制。

例題4.將二進制數(shù)110011⑵化成十進制數(shù)

精講點撥：

1.求兩個正數(shù)8251和2146;228和1995;5280和12155的最大公約數(shù).

2.求兩個正數(shù)8251和2146的最大公約數(shù).

3.用秦九韶算法計算多項式/(x)=12+35x-8xa+79x}+6x*+5jr5+3x6

在x=-4時的值時,V3的值為：

反思總結(jié)：

比