山东省高中数学(新课标人教A版)必修三《1.3算法案例》

《山东省高中数学(新课标人教A版)必修三《1.3算法案例》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【课标要求】1．理解辗转相除法与更相减损术的含义，了解其执行过程．2．理解秦九韶算法的计算过程，并了解它提高计算效率的实质．3．理解进位制的概念，能进行不同进位制间的转化．4．了解进位制的程序框图和程序．【核心扫描】1．三种算法的原理及应用．(重难点)2．三种算法的框图表示及程序．(难点)3．不同进位制之间的相互转化．(重点)4．秦九韶算法中多项式的改写．(易错点)1.3算法案例辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的___________的古老而有效的算法．(2)辗转相除法的算法步骤第一步，给定_________

2、_______.第二步，计算___________________.第三步，____________.第四步，若r＝0，则m、n的最大公约数等于___；否则，返回________.自学导引1．最大公约数两个正整数m，nm除以n所得的余数rm＝n，n＝rm第二步更相减损术第一步，任意给定两个正整数，判断它们是否都是_____．若是，用_______；若不是，执行_______．第二步，以_____的数减去_____的数，接着把所得的差与_____的数比较，并以大数减小数，继续这个操作，直到所得的数_____为止，则这个数(等数)或这个数与约简

3、的数的乘积就是所求的最大公约数．任意给定两个正整数，用辗转相除法和更相减损术是否都可以求它们的最大公约数？提示是．更相减损术与辗转相除法都能在有限步内结束，故均可以用来求两个正整数的最大公约数．2．偶数2约简第二步较小较小相等较大秦九韶算法把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算_____________一次多项式的值，即v1＝__________，然后由内向外逐层计算一次多项式的值，即v2＝________

4、__，v3＝__________，…vn＝__________.这样，求n次多项式f(x)的值就转化为求________________的值．3．最内层括号内anx＋an－1v1x＋an－2v2x＋an－3vn－1x＋a0n个一次多项式进位制进位制是人们为了_____和_________而约定的记数系统，“满k进一”就是k进制，k进制的基数是k.把十进制转化为k进制数时，通常用除k取余法．不同进制间的数不能比较大小，对吗？提示不对．不同的进位制是人们为了计数和运算方便而约定的记数系统，不同进位制的数照样可比较大小，不过一般要转化到十进制下比

5、较大小更方便一些．4．计数运算方便1．辗转相除法与更相减损术的区别和联系名师点睛名称辗转相除法更相减损术区别①以除法为主．②两个整数差值较大时运算次数较少．③相除余数为零时得结果①以减法为主．②两个整数的差值较大时，运算次数较多．③相减，两数相等得结果．④相减前要做是否都是偶数的判断联系①都是求两个正整数的最大公约数的方法．②二者的实质都是递推的过程．③二者都要用循环结构来实现秦九韶算法(1)特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可．(2)算法步骤：设Pn(x)＝anxn＋an－1

6、xn－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，即从最内层的括号到最外层．括号的值

7、依次赋予变量v1，v2，…，vk，…，vn，第n步所求值vn＝vn－1x＋a0即为所求多项式的值．(3)秦九韶算法有以下几个优点：①大大减少了乘法的次数，使计算量减小．在计算机上做一次乘法所需要的时间是做加法、减法的几倍到十几倍，减少做乘法的次数也就加快了计算的速度；②规律性强，便于利用循环语句来实现算法；③避免了对自变量x单独做幂的计算，每次都是计算一个一次多项式的值，从而可以提高计算的精度．关于进位制应注意的问题(1)十进制的原理是满十进一．一个十进制正整数N可以写成an×10n＋an－1×10n－1＋…＋a1×101＋a0×100的形

8、式，其中an，an－1，…，a1，a0都是0至9中的数字，且an≠0.例如365＝3×102＋6×10＋5.(2)一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注(k