人教A数学必修三教案学案1.3 算法案例

1.3算法案例

【教学目标】：

i.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。

2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。

【教学重难点】：

重点：理解辗转相除法与更相减损术求最大公约数的方法。

难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。

【教学过程】：

情境导入：

L教师首先提出问题：在初中，我们已经学过求最大公约数的知识，你能求出18与30

的公约数吗？

2.接着教师进一步提出问题，我们都是利用找公约数的方法来求最大公约数，如果公约数

比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？

比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容。

新知探究：

1.辗转相除法

例1求两个正数8251和6105的最大公约数。

（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，

根据已有的知识即可求出最大公约数）

解:8251=6105X1+2146

显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的

约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。

6105=2146X2+1813

2146=1813X1+333

1813=333X5+148

333=148X2+37

148=37X4+0

则37为8251与6105的最大公约数。

以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公

元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：

第一步：用较大的数m除以较小的数n得到一个商q。和一个余数r。；

第二步：若r0=0,则n为m,n的最大公约数；若r°¥0,则用除数n除以余数r0得到一

个商卬和一个余数n；

第三步：若n=0,贝为m,n的最大公约数；若nWO,则用除数r。除以余数n得到一

个商qz和一个余数r2;

依次计算直至r,.=0,此时所得到的r,rl即为所求的最大公约数。

练习：利用辗转相除法求两数4081与20723的最大公约数（答案：53）

2.更相减损术

我国早期也有解决求最大公约数问题的算法，就是更相减损术。

-2-

更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母•子之数，以少

减多，更相减损，求其等也，以等数约之。

翻译出来为：

第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第

二步。

第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。

继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约数。

例2用更相减损术求98与63的最大公约数.

解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98-63=35

63—35=28

35-28=7

28—7=21

21-7=14

14-7=7

所以，98与63的最大公约数是7。

练习：用更相减损术求两个正数84与72的最大公约数。(答案：12)

比较辗转相除法与更相减损术的区别：

(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主,

计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别

较明显。

(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损

术则以减数与差相等而得到

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-

进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符

号的个数称为基数，基数为n,即可称n进位制，简称n进制.现在最常用的是十进制，通常

使用10个阿拉伯数字0-9进行记数.

对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57,可以用二进制

表示为111001,也可以用八进制表示为71、用十六进制表示为39,它们所代表的数值都是一

样的.

表示各种进位制数一般在数字右下脚加注来表示，如111001(2)表示二进制数,34(5)表示

5进制数.

(1).k进制转换为十进制的方法：

a3

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

(2).十进制转化为k进制数b的步骤为：

第一步，将给定的十进制整数除以基数k,余数便是等值的k进制的最低位；

第二步，将上一步的商再除以基数k,余数便是等值的k进制数的次低位；

第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进

制各位的数，最后一次余数是最高位，即除k取余法.

要点诠释：

1、在k进制中，具有k个数字符号.如二进制有0,1两个数字.

2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.

3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种

进制的数，有的也可以相互转化.

【反馈测评】：

1.求324、243、135这三个数的最大公约数。

求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约

数的最大公约数即为所求。

2.用更相减损术求98与63的最大公约数

解：由于63不是偶数，把98和63以大数减小数，并辗转相减

98-63=35

63-35=28

35-28=7

28-7=21

21-7=21

14-7=7

所以，98和63的最大公约数等于7

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

这个多项式当x=5的值。

解：将多项式变形：/(x)=((((5x+2)x+3.5)x—2.6)x+1.7)x—0.8按由里到外的顺序,

依此计算一次多项式当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所以，当x二5时，多

-4-

项式的值等于17255.2

4.将二进制数110011⑵化成十进制数

解：根据进位制的定义可知

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

=1x32+1x16+1x2+1

=51

所以，110011⑵=51。

【板书设计】：

1.3算法案例

一、辗转相除法三、秦九韶算法五、反馈测评：小结

例1

作业

二、更相减损术四、进位制

例2

-5-

1.3算法案例

课前预习学案

一、预习目标

1、理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。

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

二、预习内容

什么是进位制？最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说

明.

三、提出疑惑

思考：辗转相除法中的关键步骤是哪种逻辑结构？

课内探究学案

一、学习目标

1.会用辗转相除法与更相减损术求最大公约数的方法。

2.会利用秦九韶算法求多项式的值。

3.各进位制之间能灵活转化。

二、学习重难点：

重点：辗转相除法与更相减损术求最大公约数的方法和秦九韶算法求多项式的值。

难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。

三、学习过程

辗转相除法思路：可以利用除法将大数化小,找两数的最大公约数.（适于两数较大时）

⑴用较大的数m除以较小的数n得到一个商S。和一个余数R。；

⑵若a=0,则n为m,n的最大公约数；若9W0,则用除数n除以余数凡得到一个?

和一个余数飞；（3）若凡=0,则叫为m,n的最大公约数;若4#0,则用除数&除以余数曷得

到一个商52和一个余数R2；……依次计算直至R“=0,此时所得到的即为所求的最大公

约数.

例题1：求两个正数1424和801的最大公约数.

①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法.

②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数

是否等于0来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.

教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术.在《九章

算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，

以少减多，更相减损，求其等也，以等数约之.

-6-

翻译为：(1)任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，

执行第二步.

(2)以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小

数.继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最

大公约数.

例题2.用更相减损术求91和49的最大公约数.

秦九韶算法：

(1)设计求多项式一5——4/+3--6x+7当x=5时的值的算法，并写出

程序。

(2)有没有更高效的算法？能否探求更好的算法，来解决任意多项式的求解问题？

引导学生把多项式变形为：

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

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

并提问：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一

次式”？x的系数依次是什么？

用秦九韶算法求多项式的值，与多项式组成有直接关系吗？用秦九韶算法计算上述多项式

的值，需要多少次乘法运算和多少次加法运算？秦九韶算法适用于一般的多项式

nn

/(x)=anx+an_tx-'+■■■+a,x+a0的求值问题吗？

怎样用程序框图表示秦九韶算法？观察秦九韶算法的数学模型，计算也时要用到的值,

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

v=a

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

\yk=vk_}x+an_k这是一个在秦九韶算法中反复执行的步骤，可以用循环结

构来实现。请画出程序框图。

例题3.已知一个五次多项式为/(幻=5/+2d+3.5/-2.6/+1.7尤一0.8用秦九韶

-7-

算法求这个多项式当x=5的值。

进位制：

我们了解十进制吗？所谓的十进制，它是如何构成的？其它进位制的数又是如何的呢？

进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的数

字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n,即可称n进位

制，简称n进制。

例题4.将二进制数110011⑵化成十进制数

精讲点拨：

1.求两个正数8251和2146;228和1995;5280和12155的最大公约数.

2.求两个正数8251和2146的最大公约数.

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

在x=-4时的值时,V3的值为：

反思总结：

比