1.3 算法案例 课件人教a版必修3.ppt

栏目导引 第一章　算法初步 新知初探 思维启动 典题例证 技法归纳 知能演练 轻松闯关 (湖南师大附中内部资料)高三化学习总复习课件：高三第五次周考试卷分析课0801(课件)(培训课件)班组建设与5S管理培训多媒体计算机系统常用硬件设备教材 1. 3　算法案例 学习导航 学习目标 重点难点　 重点: 引导学生理解算法思想. 难点: 学生对算法应用的掌握. 新知初探·思维启动 1. 辗转相除法 所谓辗转相除法, 就是对于任意给定的两个正整数, 用较大的数除以较小的数. 若余数不为零, 则将余数和较小的数构成一对新数, 继续上面的除法, 直到大数被小数除尽, 则这时的小数就是原来两个数的最大公约数. 做一做 1.用辗转相除法求288与123的最大公约数. 解: 由辗转相除法, 288＝123×2＋42, 123＝42×2＋39, 42＝39×1＋3, 39＝3×13, 故288与123的最大公约数是3. 2. 更相减损术 更相减损术是我国古代数学专著《九章算术》中介绍的任意一种求两个正整数最大公约数的方法. 其基本过程是: 对于给定的两个正整数, 判断它们是否都是偶数. 若是, 用2约简; 若不是, 则用___________________, 接着把所得的______与__________比较, 并以大数减小数. 继续这个操作, 直到所得的数________为止, 则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数. 较大数减去较小数 差 较小数 相等 想一想 实际应用更相减损术时要做的第一步工作是什么？ 提示: 先判断a, b是否全为偶数, 若是, 则先都除以2再进行. 3. 秦九韶算法 (1)算法原理 它是通过一次式的反复计算, 逐步得出高次多项式的值的一种求多项式函数值的算法. 设f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0, 将其改写为 f(x)＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0 ＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0 ＝…v 首先计算最内层括号内一次多项式的值, 即v1＝anx＋an－1, 然后由内向外逐层计算一次多项式的值. 这样, 求n次多项式f(x)的值就转化为求n个一次多项式的值. (2)算法步骤 第一步, 输入多项式次数n、最高次项的系数an和x的值. 第二步, 将v的值初始化为an, 将i的值初始化为n－1. 第三步, 输入i次项的系数ai. 第四步, v＝vx＋ai, i＝i－1. 第五步, 判断i是否大于或等于0.若是, 则返回第三步; 否则, 输出多项式的值v. (3)程序框图和程序 做一做 2.用秦九韶算法求x＝2时, f(x)＝x3＋3x2＋x＋1的值, 第一个一次多项式的值为多少？ 解: 由秦九韶算法知 f(x)＝[(x＋3)x＋1]x＋1. ∴由内到外第一个一次多项式的值为 2＋3＝5. 4. 进位制 (1)进位制的概述 进位制是人们为了计数和运算方便而约定的记数系统, 约定满二进一, 就是二进制; 满十进一, 就是十进制; 满十二进一, 就是十二进制; 满六十进一, 就是六十进制; 等等. 也就是说, “___________”就是几进制, 几进制的基数(大于1的整数)就是几. 满几进一 一般地, k进制数的原理是满k进一, k进制数一般在右下角处标注基数(k), 以示区别. 例如, 270(8)表示270是一个八进制数. 十进制数一般不标注基数. (2)常见的进位制 ①二进制: a: 只使用0和1两个数字; b: 满二进一, 如1＋1＝10. ②八进制: a: 使用0,1,2,3,4,5,6,7八个不同的数字; b: 满八进一, 如7＋1＝10. ③十六进制: a: 使用0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F这十六个不同的数码, 其中A, B, C, D, E, F分别代表十进制中的10,11,12,13,14,15; b: 满十六进一, 如 F＋1＝2＋E＝10. (3)不同进位制数之间的转化 ①k进制数转化为十进制数 把k进制数转化为十进制数, 写成不同位上数字与基数幂的乘积之和即可(简称幂积求和), 即anan－1…a1a0(k)＝an×kn＋an－1×kn－1＋…＋a1×k＋a0.例如, 将二进制数11001(2)化为十进制数: 11001(2)＝1×24＋1×23＋0×22＋0×21＋1×20＝16＋8＋1＝25. ②十进制数转化为k进制数 一般方法是除k取余法, 即先把十进制数a除以k, 商为a1, 余数为r1, 再把a1除以k, 商为a2, 余数为r2……反复进行这种除法, 直到商an小于k为止,