高中数学《算法案例》导学案

K第7算法初/________

DIYlZHANG1.3算法案例

卜课前白主预习

一、辗转相除法与更相减损术

i.辗转相除法

(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的回最大公约数

的古老而有效的算法.

(2)辗转相除法的算法步骤

第一•步，给定理两个正整数加，〃.

第二步，计算理二除以「所得的余数r.

第三步，国〃？=〃,〃=r.

第四步，若;•=(),则必，〃的最大公约数等于回四否则，返回场第二步.

2.更相减损术

(1)更相减损术是我国古代数学专著《九章算术》中介绍的一种求眄两个正

整数的最大公约数的算法.

(2)基本过程

第一步，任意给定两个正整数，判断它们是否都是园偶数.若是,国用2

约简;若不是，执行园.第二步.

第二步，以四较大的数减去理较小的数,接着把所得的差与型较不的数

比较，并以大数减小数，继续这个操作，直到所得的数回1笠为止，则这个数

(等数)或这个数与约简的数的乘积就是所求的最大公约数.

3.辗转相除法与更相减损术的区别与联系

两种方法辗转相除法更相减损术

计算法则除法减法

终止条件余数为0减数与差相等

最大公约

最后一步中的除数最后一步中的减数

数的选取

步骤较多，运算简

计算特点步骤较少，运算复杂

单

相同点同为求两个正整数最大公约数的方法，都是递归过程

二、秦九韶算法

1.秦九韶算法是我国南宋数学家秦九韶在他的代表作《数书九章》中提出

的一种用于计算圜一元〃次多项式的值的方法.

2.把一个n次多项式八幻=小炉+。〃一3cH---Pmx+ao改写成如下形式：

fix）=呸（…（（。庆+。〃—1）x4-。〃二2）XH---Pai）x+ao.

求多项式的值时，首先计算口最内层括号内一次多项式的值,即01=&式

+的二_|,

然后由内向外逐层计算一次多项式的值，即

V2=^y\x+an-2，

V3=区0汽+劭二3，

Vn=^Vn-\x+ao,

这样，求〃次多项式/U）的值就转化为求国〃个一次多项式的值.

三、进位制

进位制是人们为了园计数和四运算方便而约定的记数系统,“满女进一”

就是明左进制,々进制的基数是k.把十进制数化为％进制数时，通常用除工取余

法.

H自诊小测

1.判一判（正确的打“J”，错误的打“义”）

（1）五进制的基数是5,用0,123,4,5六个数字表示.（）

（2）秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率.（）

（3）用秦九韶算法可以求两个正整数的最大公约数.（）

（4）不同进位制中，十进制的数比二进制的数大.（）

答案(l)x(2)V(3)x(4)X

2.做一做

(1)用更相减损术求98与63的最大公约数时，需做减法的次数为()

A.4B.5

C.6D.7

答案C

解析(98,63)f(35,63)-*(35,28)f(7,28)f(7,21)f(7,14)f(7,7),.•.共进行6

次减法.

(2)用“辗转相除法”求得168与486的最大公约数是()

A.3B.4

C.6D.16

答案C

解析486=168X2+150,168=150X1+18,150=18X8+6,18=3X6,故

168与486的最大公约数为6.

(3)下列关于利用更相减损术求156和72的最大公约数的说法中正确的是

()

A.都是偶数必须约简

B.可以约简，也可以不约简

C.第一步作差为156—72=84；第二步作差为72—84=—12

D.以上都不对

答案B

解析约简是为了使运算更加简捷，故不一定要约简，A错误.C中第二步

应为84-72=12,故选B.

(4)秦九韶算法是中国南宋时期的数学家秦九韶提出的一种求多项式值的简

化算法，其求一个〃次多项式/(》)=斯炉+。”-3厂1+…+aix+ao值的算法是：vo

=an,01=0(仄+。”-1,V2=Vix+an-2,V3=V2X-\~an-3,…，Vn为所

求/(X)的值，利用秦九韶算法，计算./0)=22+》4+3/+2%2+》+1当*=2时的

值时，02的值为()

A.2B.5

C.13D.115

答案C

3

解析计算“1)=2/+%4+3%+2/+%+1时，当x=2时，vo=afl=2,v\=

uor+an-i=2X2+1=5,02=0ix+a”-2=5X2+3=13.

卜课堂互动探究

探究1求最大公约数

例1如图所示的程序框图的算法思想源于数学名著《几何原本》中的“辗

转相除法”，执行该程序框图(图中“〃?MOD〃”表示根除以〃的余数)，若输入的

m,〃分别为495,135,则输出的加=()

A.0B.5

C.45D.90

［答案］C

［解析］该程序框图是求495与135的最大公约数，由495=135X3+90,135

=90X1+45,90=45X2,知495与135的最大公约数是45,所以输出的m=45,

故选C.

拓展提升

辗转相除法与更相减损术两种算法比较

(1)使用辗转相除法，我们可依据。=浦+「这个式子，反复执行，直到r=0

为止，用更相减损术就依据这个式子，反复执行，直到/为止.

(2)由该题可以看出，用辗转相除法求最大公约数步骤较少，而用更相减损术

运算较易，解题时要灵活运用.

【跟踪训练1】求612,396,264的最大公约数.

解这三个整数都比较大，适合用辗转相除法，具体步骤如下：

612=396X1+216；396=216X1+180；216=180X1+36；180=36X5.

所以612和396的最大公约数为36.

又264=36X7+12；36=12X3.

所以264和36的最大公约数为12,

综上可得，612,396,264的最大公约数是12.

探究2秦九韶算法及应用

例2已知兀0二炉+炉+^2+无+1,求人3)的值.

［解］原多项式可化为“x)=((((x+0)x+l)x+l)x+1)x+1,

当x=3时，优=1,

oi=1义3=3,

02=3X3+1=10,

5=10X3+1=31,

04=31X3+1=94,

05=94X3+1=283,

所以43)的值为283.

［变式探究］本例在求.*3)的值过程中，加法、乘法运算的次数分别为多少？

解加法4次，乘法5次.

拓展提升

用秦九韶算法计算多项式的值时应注意的问题

当多项式中出现空项时，利用秦九韶算法求多项式的值，要补上系数为0的

相应项，例如本题中的0/这一项.当一个多项式空项很多时，用一般的计算方

法可能更简单一些，如对于-"+5,求人2)的值，就没有必要再利用秦

九韶算法了，直接将x=2代入计算即可.

【跟踪训练2］用秦九韶算法求多项式.*%)=7r+3/—5%+11在x=23时

的值，在运算过程中下列数值不会出现的是()

A.164B.3767

C.86652D.85169

答案D

解析火工)=7尸+3幺-5x+ll=x［x(7x+3)—5］+11,则a=7,s=7X23+

3=164,s=164X23—5=3767,w=3767X23+11=86652,故在运算过程中不

会出现的数值是D.

探究3进位制

例3(1)把二进制数1101⑵化为十进制数为；

(2)将十进制数458转化为四进制数为；

(3)比较85(9)和210⑹的大小.

［答案］(1)13(2)13022(4)(3)见解析

［解析］(1)1101(2)=1X23+1X22+OX21+1X20=13,

所以二进制数1101⑵转化为十进制的数为13.

(2)

4458余数、

41142

4282

470

413

0I

所以458=13022(4).

(3)因为85(9)=5+8X9=77,

210(6)=0+1X6+2X62=78,

而78〉77,所以210(6)>85(9).

拓展提升

十进制数转化为其他进制数的方法步骤

【跟踪训练3】⑴将101111011(2)转化为十进制的数;

⑵将235⑺转化为十进制的数；

(3)将137(io)转化为六进制的数;

(4)将53(8)转化为二进制的数.

解(1)101111011(2)=1X28+OX27+1X26+1X25+1X24+1X23+OX22

+1X21+1X20=379(IO).

(2)235⑺=2X72+3X71+5X70=124(io).

(3)

6137余数

6225

634

03

/.137(10)=345(6).

(4)53(8)=5X81+3X80=43(io).

243余数

2211

2101

250

221

/110

01

.,.53(8)=101011(2),

I挈窈提加

1.辗转相除法与更相减损术的区别和联系

名称辗转相除法更相减损术

①以减法为主

①以除法为主

②两个整数的差值较大时，运算次

②两个整数差值较大时运算次数较

区别数较多

少

③相减，两数相等得结果

③相除余数为零时得结果

④相减前要做是否都是偶数的判断

①都是求最大公约数的方法

联系

②二者的实质都是递归的过程

③二者都要用循环结构来实现

注意：应用更相减损术时，相减之前先判断两个数是否为偶数，若都是偶数则

要反复除2,直至至少出现一个奇数为止.最后的公约数也是相减之后的数乘

以约简数.

2.秦九韶算法的特点

秦九韶算法的特点在于把求一个n次多项式的值转化为求〃个一次多项式的

值，即把求/(x)=a"廿----\-a\x+ao的值转化为求递推公式：

VO~~Cln，

<

Vk=Vk-ix-]-cin-k(^k=1,2,,,,,n).

这样可以最多计算n次乘法和n次加法即可得多项式的值，和直接代入多项式

相比减少了乘法的运算次数，提高了运算效率.

3.十进制与其他进制的转化

(1)将k进制转化为十进制的方法：先把k进制数写成各位上的数字与k的幕的

乘积的形式，再按十进制的运算规则计算.

⑵将十进制化成人进制的方法：用除左取余法，用攵连续去除十进制数所得的

商，直到商为零为止，然后将各步所得的余数倒序写出，即为相应的上进制数.

注意：两个非十进制的数之间的转化，可以先化成十进制数，再化成另一进

制的数，即将十进制作为“桥梁”.

卜随堂达标自测

1.三位四进制数中的最大数等于十进制数的()

A.63B.83

C.189D.252

答案A

解析三位四进制数中的最大数为333g),则333(4)=3X42+3X41+3=63.

2.把389化为四进制数，则该数的末位是()

A.1B.2

C.3D.4

答案A

解析

4389余数

4971

4241

460

412

01

故389=12011(4),末位为1.

3.用秦九韶算法计算多项式««)=31+4%5—5d+6x3—712+8x+l,当x=

2时的值时，需要做乘法和加法的次数分别是()

A.6,6B.5,6

C.5,5D.6,5

答案A

解析由秦九韶算法将多项式改成如下形式：

.x)=(((((3x+4)x-5)x+6)x-7)x+8)x+1,

按由内到外的顺序，依次计算x=2时的值.

00=3,5=3X2+4=10,

s=10X2—5=15,

5=15X2+6=36,

04=36X2—7=65,

05=65X2+8=138,

06=138X2+1=277.

这样求多项式的值时，是通过求6个一次多项式的值得到的，故进行了6次

乘法和6次加法.

4.若175(.)=125,则「=.

答案8

解析由题意可得，lX/+7Xr+5X/=125,

整理得，+7r—120=0,

解得尸=8或「=一15(舍去)，/.r=8.

5.用辗转相除法求294,84两数的最大公约数，并用更相减损术检验你的结

果.

解辗转相除法求解如下:

294=84X3+42,

84=42X2.

所以294与84的最大公约数是42.

更相减损术验证如下：

因为294与84都是偶数，可同时除以2,得147与42.

因为147-42=105,

105-42=63,

63-42=21,

42-21=21,

所以294与84的最大公约数为21X2=42.

卜课后课时精练

A级：基础巩固练

一、选择题

1.4830与3289的最大公约数为（）

A.23B.35C.11D.13

答案A

解析4830=1X3289+1541；

3289=2X1541+207；

1541=7X207+92；

207=2X92+23；92=4X23.

，23是4830与3289的最大公约数.

2.用辗转相除法计算56和264的最大公约数时，需要做的除法次数是（）

A.3B.4C.6D.7

答案B

解析:264+56=4...40,56+40=1...16,40+16=2....8,16^8=2,：.264

与56的最大公约数是8,需要做的除法次数是4.故选B.

3.用更相减损术求459与357的最大公约数，需要做减法的次数为（）

A.4B.5C.6D.7

答案B

解析459-357=102,357-102=255,255-102=153,153-102=51,102-

51=51,所以459与357的最大公约数为51,共做减法5次.

4.下列各数，化为十进制后，最大的为（）

A.101010⑵B.111（5）

C.32⑻D.54（6）

答案A

54321O

解析101（W）=1X2+OX2+1X2+0X2+1X2+OX2=42,111（5）=

1X52+1X5I+1X50=31,32（8）=3X81+2X80=26,54（6）=5X61+4X60=34.

故转化为十进制后，最大的是101010（2）,

5.《周易》历来被人们视作儒家群经之首，它表现了古代中华民族对万事万

物的深刻而又朴素的认识，是中华人文文化的基础，它反映出中国古代的二进制

计数的思想方法.我们用近代术语解释为：把阳爻“——”当作数字“1”，把阴

爻“——”当作数字“0”，则八卦所代表的数表示如下：

卦名符号表示的二进制数表示的十进制数

坤----------0000

震----------0011

坎0102

----------

----------

兑0113

X_________________________

依此类推，则六十四卦中的“屯”卦，符号“二二”表示的十进制数是

（）

A.18B.17C.16D.15

答案B

解析由题意类推，可知六十四卦中的“屯”圭卜，符号"二=’表示的

二进制数为010001,转化为十进制数，为1X20+OX21+OX22+OX23+1X24+

0X25=17.

二'填空题

6.阅读程序框图，利用秦九韶算法计算多项式/W=a优，+。,一炉-+…

+ao,当x=xo时，框图中A处应填入.

/输;|||//

（A1

答案alt-k

,

解