人教A版必修三 1.3 算法案例 教案.doc

1.3 算法案例教学目标 1理解掌握辗转相除法与更相减损术、秦九韶算法的含义； 2会用理解掌握辗转相除法与更相减损术求两个正整数的最大公约数； 3.掌握秦九韶算法求多项式的值的方法； 4.理解进位制的概念，掌握不同进位制数之间的转化。学习重点 1. 通过古代著名的算法,理解掌握辗转相除法与更相减损术、秦九韶算法的含义； 2. 初步学会几种进位制之间地转换，初步理解几种进位制之间地转换的算法思想。学习难点 1.了解辗转相除法与更相减损术、秦九韶算法计算过程;了解其算法程序框图和程序 2. 能运用几种进位制之间地转换，解决一些有关的问题。基础回扣一.辗转相除法 1.含义 所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数.若余数不为 零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则 这时较小的数就是原 两个数的最大公约数.2、作用 辗转相除法是用于求两个正整数_的一种算法，这种算法是由欧几里得 在公元前300年左右首先提出的，因此又叫_3、算法步骤 第一步,输入两个正整数m,n(mn).第二步,计算m除以n所得的余数r.第三步, .第四步,若r0,则m,n的最大公约数等于m；否则转到第 步. 第五步,输出最大公约数m.二、更相减损术 1、算理 所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差 和较小的数构成新的一对数，再用 的数，反复执行此步骤，直到差数 和较小的数相等，此时相等的两数便为原 两个数的最大公约数.2、作用 更相减损术是我国古代数学专著_中介绍的一种求两个正整数最大公 约数的方法3、算法步骤 第一步,输入两个正整数a,b(ab);第二步,若a不等于b ,则执行第三步；否则转到第五步； 第三步,把a-b的差赋予r;第四步,如果br, 那么把b赋给a,把r赋给b;否则把r赋给 a，执行第二步；第五步,输出最大公约数b. 三、秦九韶算法 1、秦九韶算法的是通过一次式的反复计算，逐步求出n次多项式的值因此对于一个n次 多项式，利用秦九韶算法求多项式的值，只要做 运算和 运算即可2、作用 用秦九韶算法求n次多项式， 当x=时的值.3、基本原理 首先将多项式改写成如下形式 = _， 求多项式的值时，首先计算最内层括号内的一次多项式的值，即= _，然后由内 向外逐层计算一次多项式的值，即， = _. 学 这样，求n次多项式f(x)的值就转化为求_4、算法步骤 第一步 输入多项式的次数n，最高次项的系数an和x的值. 第二步 令v=an，i=n-1. 第三步 输入i次项的系数ai. 第四步 v=vx+ai，i=i-1.第五步 判断i0是否成立.若是，则返回第三步；否则，输出多项式的值v. 四、二进制1、进位制的概念 进位制是人们为计数和运算方便而约定的计数系统，约定满二进一，就 是_进制；满十进一，就是_进制；,也就是说，“满几进一”就是_进制，几进制 的基数就是_.2、 表示 一般地，若 是一个大于1的整数，那么以 为基数的 进制数可以表示为一串 数字连写在一起的形式 3、进位制之间的转化 (1) 进制的数转化为十进制 若表示一个 进制的数，则转化为十进制数 为 =_.(2) 将十进制化为 进制用除 取余法，用 连续去除_，直到_ 为止，然后将所得的余数_，即为相应的 进制数. 问题探讨与解题研究类型一、 求最大公约数例1.分别用辗转相除法和更相减损术求779与209的最大公约数. 【练习】 用辗转相除法和更相减损术求1 515与600的最大公约数，需要运算的次数分别为 ()a4,15 b5,14 c5,13 d4,12解析 选b辗转相除法 1 5156002315；6003151285,315285130,28530915,30152，故最大公约数为15，且需计算5次用更相减损术 1 515600915,915600315,600315285，31528530,28530255,25530225，22530195,19530165,16530135, 13530105，1053075,753045,453015,301515.故最大公约数为15，且需计算14次. 【小结】辗转相除法与更相减损术的比较 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式 看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到. 类型二、 利用秦九韶算法求多项式的值例2、已知f(x)=5+10+10+5x+1，用秦九韶算法求x=2时f(x)的值【练习】已知一个5次多项式为f(x)4x52x435x326x217x08，用秦九韶算法求这个多项式当x5时的值【解析】将f(x)改写为f(x)(4x2)x35)x26)x17)x08，由内向外依次计算一次多项式，当x5时的值 v04；v145222；v2225351135；v311355265649；v456495172 8262；v52 826250814 1302所以当x5时，多项式的值等于14 1302 【小结】秦九韶算法是求一元多项式的值的一种方法.它的特点是 把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率. 类型三、 利用秦九韶算法求多项式的值 例1.已知一个 进制数132与十进制数30相等,那么 等于( ) (a)-7或4 (b)-7 (c)4 (d)都不对例2.把十进制数111化为五进制数是( ) (a)421 (b)521 (c)423 (d)332【练习】210(6)化成十进制数为_，85化成七进制数为_【解析】210(6)2621678，所以85151(7)【答案】78151(7) 当堂检测1二进制数算式1 010(2)10(2)的值是 ()a1 011(2) b1 100(2)c1 101(2) d1 000(2) 2.490和910的最大公约数为()a2b10c30d70【解析】9104901420，490420170，420706，故最大公约数为70【答案】d3.利用秦九韶算法求当时，的值时， 下列说法正确的是( ) a.先求 b.先求， 第二步求 c.直接运算求解 d. 以上皆错 【解析】b. 4将五进制数30 241(5)转化为七进制数 课堂小结1.比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时，计算次数的区别较明显.（2）从结果体现形式 看，辗转相