1.3.1算法案例---辗转相除法与更相减损术

1、第一课时1.3.1算法案例-辗转相除法与更相减损术教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序教学重点：理解辗转相除法与更相减损术求最大公约数的方法教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言教学过程：一、复习准备：1.回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）2.提问：小学学过的求两个数最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出3

2、6和64的最大公约数.除了用这种方法外还有没有其它方法？64 =36 1 28，. 36和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至8=42，得出4即是36和64的最大公约数.二、讲授新课：1.教学辗转相除法：例1:求两个正数1424和801的最大公约数.分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数.（适用于两数较大时）1以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：（1）用较大的数m除以较小的数n得到一个商S0和一个余数Ro; （2）若RQ=0,则n为m n

3、的最大公约数；若RQ工0,则用除数n除以余数Ro得到一个商S1和一个余数R; （3）若R=0，则R1为m n的最大公约数；若R工0,则用除数RQ除以余数R得到一个商S2和一个余数R2；依次计算直至R=0,此时所得到的Rn即为所求的最大公约数2由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次 数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图 如右图：（师生共析，写出辗转相除法完整的程序框图和程序语言）练习：求两个正数8251和2146的最大公约数.（乘法格式、除法格式）2.教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术.在九章算术中有

4、更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母？子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：（1）任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数例2:用更相减损术求91和49的最大公约数.分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数）就是所求的最大公约数.（反思：辗转相除法与更相减损术是否存在相通的地方）练习：用更相减损术求72和168的最大公约数.3.小结：辗转相除

5、法与更相减损术及比较都是求最大公约数的方法，辗转相除法以除法为主,更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少；结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到三、巩固练习：1、练习：教材P35第1题2、作业：教材P38第1题第二课时1.3.2算法案例-秦九韶算法教学要求：了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数、提高计算 效率的实质；理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用 教学重点：秦九韶算法的特点及其程序设计教学难点：秦九韶算法的先进性理解及其程序设计教学过程：一、复习准备：1分别用辗转相除法和更相减

6、损术求出两个正数623和1513的最大公约数.2.设计一个求多项式f (x) =2x5-5x4-4x33X2-6X7当x = 5时的值的算法(学生自己 提出一般的解决方案：将x=5代入多项式进行计算即可)提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？此方案有何优缺点？(上述算法一共做了5+4+3+2+1=15次乘法运算，5次加法运算优点是简单、易懂；缺点是不 通用，不能解决任意多项式的求值问题，而且计算效率不高)二、讲授新课：1.教学秦九韶算法：1提问：在计算x的幕值时，可以利用前面的计算结果，以减少计算量，即先计算x2，然后2 2 2依次计算x x,(x x) x,(x x)

7、x) x的值，这样计算上述多项式的值，一共需要多少次 乘法，多少次加法？(上述算法一共做了4次乘法运算，5次加法运算)2结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法能更快地得到结果3更有效的一种算法是：将多项式变形为：f (x) =2x5-5x4-4x33x2-6x 7 = (2 x _5)x _4)x 3)x-6)x 7, 依次计算2 5 -5 =5,55-4 =21 ,21 5 3 = 108,108 5-6=534,534 5 7 = 2677故f (5) =2677.这种算法

8、就是“秦九韶算法”(注意变形，强调格式)4练习：用秦九韶算法求多项式f (x2x4x3x25x 1当x = 4时的值(学生板书、师生共评 教师提问：上述算法共需多少次乘法运算？多少次加法运算？)5如何用秦九韶算法完成一般多项式f(x)二anXn anxn J|l a1x ao的求值问题？改写：f (x)二anXn anxn a。=(川(anX - a)x a./x ajx a.首先计算最内层括号内一次多项式的值，即= anx an,然后由内向外逐层计算一次多项式的值，即V2=wx an,V3=V2X anJS，w=Vnx a。6结论：秦九韶算法将求n次多项式的值转化为求n个一次多项式的值， 整

9、个过程只需n次乘 法运算和n次加法运算；观察上述n个一次式，可发出vk的计算要用到vk4的值，若令v0an,循环结构来实现 练习：用秦九韶算法求多项式f (x5x52x4，3.5x3-2.6x247X-0.8当x = 5时的值并画出程序框图2.小结：秦九韶算法的特点及其程序设计三、巩固练习：1、练习：教材P35第2题2、作业：教材P36第2题第三课时133算法案例-进位制可得到下列递vvk4x an*(k =1,2l(,n)这是一个反复执行的步骤，因此可用教学要求：了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换；学习各种进位制转换成十进制的计算

10、方法，研究十进制转换为各 种进位制的除k去余法，并理解其中的数学规律.教学重点：各种进位制之间的互化教学难点：除k取余法的理解以及各进位制之间转换的程序框图及其程序的设计教学过程：一、复习准备：1试用秦九韶算法求多项式f (x) = 4X5- X2 2当x = 3时的值，分析此过程共需多少次乘法运算？多少次加法运算？2.提问：生活中我们常见的数字都是十进制的， 但是并不是生活中的每一种数字都是十进制的比如时间和角度的单位用六十进位制，电子计算机用的是二进制， 旧式的秤是十六进制的， 计算 一打数值时是12进制的 那么什么是进位制？不同的进位制之间又有什么联系呢？二、讲授新课：1.教学进位制的概

11、念：1进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几女口：“满十进一”就是十进制，“满二进一”就是二进制 .同一个数可以用不同 的进位制来表示，比如：十进数57,可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39,它们所代表的数值都是一样的表示各种进位制数一般在数字右下脚加注来表示，如上例中：111001(2)=71(8)=39(16)2一般地，任意一个k进制数都可以表示成不同位上数字与基数的幕的乘积之和的形式，即anan“.a1ao(k)(O：an：k,0a.，印咼：k)=anknakn，|印k1a。k0.如:把1100

12、11(2)化为十进制数，110011(2)=1 X25+1 H24+0 x23+0 x22+1 x21+1 x20=32+16+2+1=51.把八进制数7348(8)化为十进制数，7348(8)= 7 833 824 818 83816.2.教学进位制之间的互化：1例1：把二进制数1001101(2)化为十进制数.(学生板书 教师点评 师生共同总结将非十进制转为十进制数的方法)分析此过程的算法过程，编写过程的程序语言见P342练习：将2341(5)121(3)转化成十进制数.3例2、把89化为二进制数.分析：根据进位制的定义，二进制就是“满二进一”，可以用2连续去除89或所得商，然后取余数.(

13、教师板书)上述方法也可以推广为把十进制化为k进制数的算法，这种算法成为除k取余法.4练习：用除k取余法将89化为四进制数、六进制数.5例3、把二进制数11011.101(2)化为十进制数.解：11011.101(2)=1 241 230 221 211 201 2 0 2T21 2 = 27.625.(小数也可利用上述方法化进行不同进位制之间的互化.)变式：化为八进制 一；方法：进制互化3.小结：进位制的定义；进位制之间的互化.三、 巩固练习：1、练习：教材P35第3题2、作业：教材P38第3题第四课时1.3.4生活中的算法实例教学要求：通过生活实例进一步了解算法思想.教学重点：生活实例的算法

14、分析.教学难点：算法思想的理解 教学过程：一、复习准备：1.前面学习了哪几种算法案例？每种算法的作用及操作方法是怎样的？2.算法思想在我们的生活中无处不在，如何利用我们所学习的知识解决生活中的实际问题？二、讲授新课：1.霍奇森算法：提问：同学们经常会面对一个共同的问题，就是有时有太多的事情要做例如，你可能要面临好几门课的作业的最后期限，你如何合理安排以确保每门课的作业都能如期完成？如果根本不 可能全部按期完成，你该怎么办？（霍奇森算法可以使得迟交作业的数目减到最小这一算法已经广泛应用于工业生产安排的实践中.）例如：当你拿到下面这组数据后， 你会如何安排你的时间， 以确保每门课的作业都能如期完成

15、？ 若不能全部按期完成，也能尽量使迟交作业的数目减到最小？学科数学语文历史夕卜语物理化学期限/小时252421所需时间/小时120.510.50.5若知道各项作业的到期日，并且知道或能估计出完成每项作业将花费的时间，那么霍奇森算法 可用自然语言描述为：把这些作业按到期日的顺序从左到右排列，从最早到期的到最晚到期 的；假设从左到右一项一项做这些作业的话，计算出从开始到完成某一项作业时所花的时间依次做此计算直到完成了所列表中的全部作业而没有一项作业会超期，停止；或你算出某项作 业将会超期，继续第三步；考虑第一项将会超期的作业以及它左边的所有作业，从中取出花 费时间最长的那项作业，并把它从表中去掉；回到第二步，并重复第二到四步，直到做完2.孙子问题：韩信是秦末汉初的著名军事家据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦 问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数韩信先令士兵排成了3列纵队进行操练，结果有2人多余；接着他立刻下令将队形改为5列纵 队，这一改又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整行由 此得出共有士兵2333人.如何用现在的算法思想分析这一过程？孙子算经中给出了它的具体解法，其步骤是：选定5 7的倍数，被3除余1,即70；选定3 7的一个倍数， 被5除余1,即21； 选定3 5的一个倍数， 被7