仅供学习与交流
第一课时 1.3.1 算法案例---辗转相除法与更相减损术
教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.
教学重点：理解辗转相除法与更相减损术求最大公约数的方法.
教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 教学过程： 一、复习准备：
1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.
2. 提问：①小学学过的求两个数最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数. ②除了用这种方法外还有没有其它方法？64?36?1?28，?36和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至8?4?2，得出4即是36和64的最大公约数. 二、讲授新课：
1. 教学辗转相除法：
例1：求两个正数1424和801的最大公约数.
分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两数较大时）
①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下： （1）用较大的数m除以较小的数n得到一个商S0和一个余数R0；（2）若R0＝0，则n为m，n的最大公约数；若R0≠0，则用除数n除以余数R0得到一个商S1和一个余数R1；（3）若R1＝0，则R1为m，n的最大公约数；若R1≠0，则用除数R0除以余数R1得到一个商S2和一个余数R2；……依次计算直至Rn＝0，
此时所得到的Rn?1即为所求的最大公约数.
②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图如右图：（师生共析，写出辗转相除法完整的程序框图和程序语言）
练习：求两个正数8251和2146的最大公约数. （乘法格式、除法格式） 2. 教学更相减损术：
我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母?子之数，以少减多，更相减损，求其等也，以等数约之. 翻译为：（1）任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.
例2：用更相减损术求91和49的最大公约数.
分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数）就是所求的最大公约数. （反思：辗转相除法与更相减损术是否存在相通的地
收集于网络，如有侵权请联系管理员删除
仅供学习与交流
方）
练习：用更相减损术求72和168的最大公约数.
3. 小结：辗转相除法与更相减损术及比较①都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少；②结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到.
三、巩固练习：1、练习：教材P35第1题 2、作业：教材P38第1题 第二课时 1.3.2 算法案例---秦九韶算法
教学要求：了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数、提高计算效率的实质；理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用.
教学重点：秦九韶算法的特点及其程序设计.
教学难点：秦九韶算法的先进性理解及其程序设计. 教学过程： 一、复习准备：
1. 分别用辗转相除法和更相减损术求出两个正数623和1513的最大公约数. 2. 设计一个求多项式f(x)?2x5?5x4?4x3?3x2?6x?7当x?5时的值的算法. （学生自己提出一般的解决方案：将x?5代入多项式进行计算即可）
提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？此方案有何优缺点？(上述算法一共做了5＋4＋3＋2＋1＝15次乘法运算，5次加法运算. 优点是简单、易懂；缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高.) 二、讲授新课：
1. 教学秦九韶算法：
① 提问：在计算x的幂值时，可以利用前面的计算结果，以减少计算量，即先计算x2，然后依次计算x2?x，(x2?x)?x，((x2?x)?x)?x的值，这样计算上述多项式的值，一共需要多少次乘法，多少次加法?（上述算法一共做了4次乘法运算，5次加法运算）
② 结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法能更快地得到结果. ③ 更有效的一种算法是： 将多项式变形为：f(x)?2x5?5x4?4x3?3x2?6x?7?((((2x?5)x?4)x?3)x?6)x?7，
依次计算2?5?5?5，5?5?4?21，21?5?3?108，108?5?6?534，534?5?7?2677
故f(5)?2677. ――这种算法就是“秦九韶算法”. （注意变形，强调格式） ④ 练习：用秦九韶算法求多项式f(x)?2x4?x3?3x2?5x?1当x?4时的值. （学生板书?师生共评?教师提问：上述算法共需多少次乘法运算？多少次加法运算？）
⑤ 如何用秦九韶算法完成一般多项式f(x)?anxn?an?1xn?1??a1x?a0的求值问题？
改写：f(x)?anxn?an?1xn?1??a1x?a0?((anx?an?1)x?an?2)x??a1)x?a0.
收集于网络，如有侵权请联系管理员删除
仅供学习与交流
首先计算最内层括号内一次多项式的值，即v1?anx?an?1，然后由内向外逐层计算一次多项式的值，即v2?v1x?an?2，v3?v2x?an?3，，vn?vn?1x?a0.
⑥ 结论：秦九韶算法将求n次多项式的值转化为求n个一次多项式的值，整个过程只需n次乘法运算和n次加法运算；观察上述n个一次式，可发出vk的计算要用到vk?1的值，若令v0?an，可得到下列递推公式：
?v0?an,??vk?vk?1x?an?k(k?1,2,,n). 这是一个反复执行的步骤，因此可用循环结构来
实现.
⑦ 练习：用秦九韶算法求多项式f(x)?5x5?2x4?3.5x3?2.6x2?1.7x?0.8当x?5时的值并画出程序框图.
2. 小结：秦九韶算法的特点及其程序设计
三、巩固练习：1、练习：教材P35第2题 2、作业：教材P36第2题 第三课时 1.3.3 算法案例---进位制
教学要求：了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换；学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k去余法，并理解其中的数学规律.
教学重点：各种进位制之间的互化.
教学难点：除k取余法的理解以及各进位制之间转换的程序框图及其程序的设计.
教学过程： 一、复习准备：
1. 试用秦九韶算法求多项式f(x)?4x5?x2?2当x?3时的值，分析此过程共需多少次乘法运算？多少次加法运算？
2. 提问：生活中我们常见的数字都是十进制的，但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制，旧式的秤是十六进制的，计算一打数值时是12进制的......那么什么是进位制？不同的进位制之间又有什么联系呢？ 二、讲授新课：
1. 教学进位制的概念：
① 进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几. 如：“满十进一”就是十进制，“满二进一”就是二进制. 同一个数可以用不同的进位制来表示，比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的. 表示各种进位制数一般在数字右下脚加注来表示，如上例中：111001(2)?71(8)?39(16)
② 一般地，任意一个k进制数都可以表示成不同位上数字与基数的幂的乘积之和的形式，即anan?1...a1a0(k)(0?an?k,0?an?1,...,a1,a0?k)?an?kn?an?1?kn?1?a1?k1?a0?k0. 如
：
把
110011(2)化为十进制数，
110011(2)=1?25+1?24+0?23+0?22+1?21+1?20=32+16+2+1=51.
收集于网络，如有侵权请联系管理员删除
最新人教版高中数学必修三(教案)1.3-算法案例(4课时)-.doc
