文档介绍：第3讲算法案例
★知识梳理★
,这种算法由欧几里得在公元前年左右首先提出,因而又叫欧几里得算法.
,就是对于给定的两个数,,则将较小的数和余数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时的除数就是原来两个数的最大公约数.
:对于给定的两数, 用较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数就是所求的最大公约数.
.
.
.“满进一”,就是k进制, 进制的基数是k.
:先将进制数写成用各位上的数字与k的幂的乘积之和的形式,再按照十进制数的运算规则计算出结果.
:, 直到商为零为止,然后把每次所得的余数倒着排成一个数就是相应的进制数.
★重难点突破★
:理解辗转相除法与更相减损术的原理,会求两个数的最大公约数;理解秦九韶算法原理,会求一元多项式的值;会对一组数据按照一定的规则进行排序;理解进位制,能进行各种进位制之间的转化.
:秦九韶算法求一元多项式的值及各种进位制之间的转化.
:理解辗转相除法与更相减损术、秦九韶算法原理、排序方法、进位制之间的转化方法.
★热点考点题型探析★
考点1 求最大公约数
【例1】用辗转相除法求和的最大公约数,并用更相减损术检验所得结果.
【解题思路】将80作为大数,36作为小数,执行辗转相除法和更相减损术的步骤均可.
【解析】用辗转相除法: ,
, ,
,
,
故和的最大公约数是
用更相减损术检验: ∴和的最大公约数是
,
,
【名师指引】辗转相除法是当大数被小数除尽时,结束除法运算,较小的数就是最大公约数;更相减损术是当大数减去小数的差时等于小数时停止减法,较小的数就是最大公约数.
【新题导练】
1. 试求288和123的最大公约数.
【解析】,
,
,
.
∴和的最大公约数
考点2 进制间的转化
【例2】(1)把二进制数化为十进制数;(2)把化为二进制数.
【解题思路】(1)先把二进制数写成不同位上数字与2的幂的乘积之和的形式,再按照十进制的运算规则计算出结果;(2)根据二进制数“满二进一”的原则,可以用连续去除或所得商,然后取余数.
【解析】
(1)
(2) ,,,,.
所以.
.
这种算法叫做除2余法,还可以用下面的除法算式表示;把上式中各步所得的余数从下到上排列,
得到
【名师指引】直接插入排序和冒泡排序是两种常用的排序方法,通过该例,我们对比可以发现, 直接插入排序比冒泡排序更有效一些,执行的操作步骤更少一些..
【新题导练】
2. 把化为进制的数.
【解析】
,,
∴
.
所以,.
考点3 用秦九韶算法求多项式的值
【例3】用秦九韶算法求多项式
在的值.
【解题思路】