文档介绍：【课标要求】
,了解其执行过程.
,并了解它提高计算效率的实质.
,能进行不同进位制间的转化.
.
【核心扫描】
.(重难点)
.(难点)
.(重点)
.(易错点)
算法案例
辗转相除法
(1)辗转相除法,又叫欧几里得算法,是一种求两个正整数的___________的古老而有效的算法.
(2)辗转相除法的算法步骤
第一步,给定________________.
第二步,计算___________________.
第三步, ____________.
第四步,若r=0,则m、n的最大公约数等于___;否则,返回________.
自学导引
1.
最大公约数
两个正整数m,n
m除以n所得的余数r
m=n,n=r
m
第二步
更相减损术
第一步,任意给定两个正整数,,用_______;若不是,执行_______ .
第二步,以_____的数减去_____的数,接着把所得的差与_____的数比较,并以大数减小数,继续这个操作,直到所得的数_____为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
任意给定两个正整数,用辗转相除法和更相减损术是否都可以求它们的最大公约数?
,故均可以用来求两个正整数的最大公约数.
2.
偶数
2约简
第二步
较小
较小
相等
较大
秦九韶算法
把一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0改写成如下形式:
(…((anx+an-1)x+an-2)x+…+a1)x+a0,
求多项式的值时,首先计算_____________一次多项式的值,即v1=__________,然后由内向外逐层计算一次多项式的值,即
v2=__________,
v3=__________,
…
vn=__________.
这样,求n次多项式f(x)的值就转化为求________________的值.
3.
最内层括号内
anx+an-1
v1x+an-2
v2x+an-3
vn-1x+a0
n个一次多项式
进位制
进位制是人们为了_____和_________而约定的记数系统,“满k进一”就是k进制,k进制的基数是k.
把十进制转化为k进制数时,通常用除k取余法.
不同进制间的数不能比较大小,对吗?
,不同进位制的数照样可比较大小,不过一般要转化到十进制下比较大小更方便一些.
4.
计数
运算方便
名师点睛
名称
辗转相除法
更相减损术
区别
①以除法为主.
②两个整数差值较大时运算次数较少.
③相除余数为零时得结果
①以减法为主.
②两个整数的差值较大时,运算次数较多.
③相减,两数相等得结果.
④相减前要做是否都是偶数的判断
联系
①都是求两个正整数的最大公约数的方法.
②二者的实质都是递推的过程.
③二者都要用循环结构来实现
秦九韶算法
(1)特点:通过一次式的反复计算,逐步得出高次多项式的值,对于一个n次多项式,只需做n次乘法和n次加法即可.
(2)算法步骤:
设Pn(x)=anxn+an-1xn-1+…+a1x+a0,将其改写为
Pn(x)=(anxn-1+an-1xn-2+…+a1)x+a0
=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0
=(…((anx+an-1)x+an-2)x+…+a1)x+a0.
第一步:计算最内层anx+an-1的值,将anx+an-1的值赋给一个变量v1(为方便将an赋予变量v0);
第二步:计算(anx+an-1)x+an-2的值,可以改写为v1x+an-2,将v1x+an-2的值赋给一个变量v2;
2.
依次类推,即每一步的计算之后都赋予一个新值vk,即从最内层的括号到最外层.
括号的值依次赋予变量v1,v2,…,vk,…,vn,第n步所求值vn=vn-1x+a0即为所求多项式的值.
(3)秦九韶算法有以下几个优点:
①大大减少了乘法的次数,、减法的几倍到十几倍,减少做乘法的次数也就加快了计算的速度;
②规律性强,便于利用循环语句来实现算法;
③避免了对自变量x单独做幂的计算,每次都是计算一个一次多项式的值,从而可以提高计算的精度.
关于进位制应注意的问题
(1)十