高二数学必修3---13-算法案例.ppt

栏目导引 新知初探 思维启动 典题例证 技法归纳 知能演练 轻松闯关 精彩推荐典例展示 第一章　 算法初步 1．3　算法案例 第一章　 算法初步 学习导航 新知初探思维启动 1．辗转相除法 所谓辗转相除法，就是对于任意给定的两个正整数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个数的最大公约数． 想一想 1.辗转相除法中的关键步骤可用哪种逻辑结构来实现？ 提示：辗转相除法中带余数除法是一个反复执行、直到余数等于0停止的步骤，可用循环结构来实现． 2．更相减损术 更相减损术是我国古代数学专著《九章算术》中介绍的任意 一种求两个正整数最大公约数的方法．其基本过程是：对于 给定的两个正整数,判断它们是否都是偶数．若是,用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 ＝… 首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值．这样，求n次多项式f(x)的值就转化为求n个一次多项式的值． 想一想 3.怎样设计秦九韶算法，程序框图及程序呢？ 提示：算法步骤如下： 第一步，输入多项式次数n、最高次项的系数an和x的值． 第二步，将v的值初始化为an，将i的值初始化为n－1. 第三步，输入i次项的系数ai. 第四步，v＝vx＋ai，i＝i－1. 第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v. 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.例如，将二进制数11 001(2)化为十进制数：11 001(2)＝1×24＋1×23＋0×22＋0×21＋1×20＝16＋8＋1＝25. 典题例证技法归纳 题型探究 例1 【解】　辗转相除法： 80＝36×2＋8,36＝8×4＋4,8＝4×2＋0. 故80和36的最大公约数是4. 用更相减损术检验： 80－36＝44， 44－36＝8， 36－8＝28， 28－8＝20， 20－8＝12， 12－8＝4， 8－4＝4， ∴80和36的最大公约数是4. 【名师点评】　解决此类问题要弄清它们的理论依据，根据理论依据一步一步计算出80和36的最大公约数． 跟踪训练 1．求108与45的最大公约数． 解：法一：由辗转相除法，得 108＝45×2＋18， 45＝18×2＋9， 18＝9×2， 故108与45的最大公约数是9. 法二：由更相减损术，得 108－45＝63， 63－45＝18， 45－18＝27， 27－18＝9， 18－9＝9， 故108与45的最大公约数是9. 例2 题型二　秦九韶算法及应用 (2013·福州高一检测)用秦九韶算法写