![高中数学 第1章 算法初步 1.3 算法案例 新人教版必修3_第1页](http://file1.renrendoc.com/fileroot_temp2/2021-1/16/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c1.gif)
![高中数学 第1章 算法初步 1.3 算法案例 新人教版必修3_第2页](http://file1.renrendoc.com/fileroot_temp2/2021-1/16/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c2.gif)
![高中数学 第1章 算法初步 1.3 算法案例 新人教版必修3_第3页](http://file1.renrendoc.com/fileroot_temp2/2021-1/16/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c3.gif)
![高中数学 第1章 算法初步 1.3 算法案例 新人教版必修3_第4页](http://file1.renrendoc.com/fileroot_temp2/2021-1/16/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c4.gif)
![高中数学 第1章 算法初步 1.3 算法案例 新人教版必修3_第5页](http://file1.renrendoc.com/fileroot_temp2/2021-1/16/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c/828576e4-b93c-4cbe-8d75-ac3fbeb9dc0c5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第一章算法初步,1.3算法案例,学习目标,1.理解辗转相除法与更相减损术的含义,了解其执行过程. 2.理解秦九韶算法的计算过程,并了解它提高计算效率的实质. 3.理解进位制的概念,能进行不同进位制间的转化. 4.了解进位制的程序框图和程序,知识梳理 自主学习,题型探究 重点突破,当堂检测 自查自纠,栏目索引,知识梳理 自主学习,知识点一辗转相除法与更相减损术,1.辗转相除法 (1)辗转相除法,又叫欧几里得算法,是一种求两个正整数的 的古老而有效的算法. (2)辗转相除法的算法步骤 第一步,给定 . 第二步,计算 . 第三步, . 第四步,若r0,则m,n的最大公约数等于 ;否则,返回,最大公约
2、数,两个正整数m,n,m除以n所得的余数r,mn,nr,m,第二步,答案,2.更相减损术 第一步,任意给定两个正整数,判断它们是否都是 .若是,用 约简;若不是,执行 . 第二步,以 的数减去 的数,接着把所得的差与 的数比较,并以大数减小数.继续这个操作,直到所得的数 为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数,偶数,2,第二步,较大,较小,较小,相等,答案,3.辗转相除法和更相减损术的区别与联系,思考实际应用更相减损术时要做的第一步工作是什么,答先判断a,b是否为偶数,若是,都除以2再进行,答案,知识点二秦九韶算法,1.秦九韶算法简介 (1)秦九韶算法要解决的问题是
3、求多项式的值. (2)秦九韶算法的特点: 通过一次式的反复计算,逐步得到高次多项式的值,即将一个n次多项式的求值问题归结为重复计算n个一次多项式的值的问题,3)秦九韶算法的原理: 将f(x)anxnan1xn1a1xa0改写为: f(x)(anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0,先计算最内层括号内一次多项式的值,即v1anxan1,再由内向外逐层计算一次多项式vk的值,2.秦九韶算法的操作方法 (1)算法步骤如下: 第一步,输入多项式次数n、最高次项的系数an和x的值. 第二步,将v的值初始化为an,将i的值初始化为n1. 第三步,输入i次项的系数ai
4、. 第四步,vvxai,ii1. 第五步,判断i是否大于或等于0.若是,则返回第三步;否则,输出多项式的值v,2)程序框图如图所示,3)程序如下,知识点三进位制,1.进位制的概念 进位制是为了计数和运算方便而约定的记数系统,约定“满几进一”就是几进制,几进制的基数(大于1的整数)就是几. 2.常见的进位制 (1)二进制: 只使用0和1两个数学; 满二进一,即1110(2). (2)八进制; 使用0,1,2,3,4,5,6,7这八个不同数学; 满八进一,即7110(8,思考任何进位制中都要用到的数字是什么,答0和1,返回,答案,题型探究 重点突破,题型一求两个正整数的最大公约数,例1分别用辗转相
5、除法和更相减损术求261和319的最大公约数,解方法一(辗转相除法) 3192611(余58), 261584(余29), 58292(余0), 所以319与261的最大公约数为29,方法二(更相减损术) 31926158, 26158203, 20358145, 1455887, 875829, 582929, 29290, 所以319与261的最大公约数是29,解析答案,反思与感悟,反思与感悟,1)利用辗转相除法求给定的两个数的最大公约数,即利用带余除法,用数对中较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,再利用带余除法,直到大数被小数除尽,则这时的较小数就是原来两
6、个数的最大公约数. (2)利用更相减损术求两个正整数的最大公约数的一般步骤是:首先判断两个正整数是否都是偶数.若是,用2约简.也可以不除以2,直接求最大公约数,这样不影响最后结果,跟踪训练1用辗转相除法求80与36的最大公约数,并用更相减损术检验你的结果,解803628,36844,8420, 即80与36的最大公约数是4. 验证: 80240,36218;40220,1829; 20911,1192;927,725; 523,321;211,1224; 所以80与36的最大公约数为4,解析答案,题型二秦九韶算法的应用,例2用秦九韶算法求多项式f(x)x55x410 x310 x25x1当x2
7、时的值,解f(x)x55x410 x310 x25x1(x5)x10)x10)x5)x1. 当x2时,有v01; v1v0 xa41(2)53; v2v1xa33(2)104; v3v2xa24(2)102; v4v3xa12(2)51; v5v4xa01(2)11. 故f(2)1,解析答案,反思与感悟,反思与感悟,1)先将多项式写成一次多项式的形式,然后运算时从里到外,一步一步地做乘法和加法即可.这样比直接将x2代入原式大大减少了计算量.若用计算机计算,则可提高运算效率. (2)注意:当多项式中n次项不存在时,可将第n次项看作0 xn,跟踪训练2用秦九韶算法计算多项式f(x)x612x560
8、 x4160 x3240 x2192x64当x2时的值,解根据秦九韶算法,把多项式改写成如下形式: f(x)(x12)x60)x160)x240)x192)x64. 由内向外依次计算一次多项式当x2时的值; v01;v1121210; v21026040;v340216080; v480224080;v580219232; v6322640. 所以当x2时,多项式的值为0,解析答案,题型三进位制之间的互化,例3(1)把二进制数1110011(2)化为十进制数,解1110011(2)1261251240230221211115,2)将8进制数314706(8)化为十进制数,解314706(8)3
9、85184483782081680104902. 所以,化为十进制数是104902,解析答案,反思与感悟,反思与感悟,1)将k进制转化为十进制的方法是:先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式,再按照十进制的运算规则计算出结果. (2)十进制转化为k进制,采用除k取余法,也就是除基数,倒取余,跟踪训练3将53(8)转化为二进制数,解先将八进制数53(8)转化为十进制数: 53(8)58138043; 再将十进制数43转化为二进制数,所以53(8)101011(2,解析答案,转化与化归思想,思想方法,例4下列各数中,最小的数是() A.85(9) B.210(6)C.1000
10、(4)D.111111(2,分析先将它们转化为十进制数,再进行比较,解析85(9)89577, 210(6)26216078, 1000(4)14364, 111111(2)12512412312212163. 故最小的是63,D,解析答案,解后反思,分析,解后反思合理的转化是解题的关键.对于进位制之间的转化问题,一般要先把k进制数转化为十进制数,再转化为其他进制数,数制转化方法掌握不牢致错,易错点,例5把十字进制数49化为二进制数,分析对进位制间的换算,要弄清解题的办法,将十进制数转化为k进制数用“除k取余法,解,所以49110 001(2,解后反思本例常出现的错误是把上式中各步所得的余数从
11、上到下排列,这是基本方法掌握不牢造成的,应加以注意,分析,解析答案,解后反思,返回,当堂检测,1,2,3,4,5,1.1 337与382的最大公约数是() A.3 B.382 C.191 D.201,解析利用辗转相除法,1 3373823191,3821912, 故两数的最大公约数为191,C,解析答案,1,2,3,4,5,2.把189化为三进制数,则末位数字是() A.0 B.1 C.2 D.3,解析采用“除k取余法”,得,即18921 000(3,A,解析答案,1,2,3,4,5,3.用秦九韶算法求n次多项式f(x)anxnan1xn1a1xa0当xx0时的值,求f(x0)需要乘方、乘法、
12、加法的次数分别为(,A. ,n,n B.n,2n,n C.0,2n,n D.0,n,n,解析因为f(x)(anxan1)xan2)xa1)xa0, 所以乘方、乘法、加法的次数分别为0,n,n,D,解析答案,1,2,3,4,5,4.用秦九韶算法求多项式f(x)7x66x53x22,当x4时的值时,先算的是() A.4416 B.7428 C.44464 D.74634,解析因为f(x)anxnan1xn1a1xa0 (anxan1)xan2)xa1)xa0, 所以用秦九韶算法求多项式f(x)7x66x53x22当x4时的值时,先算的是74634,D,解析答案,1,2,3,4,5,5.用更相减损术求36与134的最大公约数,第一步应为_ _,解析36与134都是偶数, 第一步应为:先除以2,得到18与67,先除以2,得到,18与67,解析答案,课堂小结,返回,1.求两个正整数的最大公约数的问题,可以用辗转相除法,也可以用更相减损术.用辗转相除法,即根据anbr这个式子,反复相除,直到r0为止;用更相减损术,即根据r|ab|这个式子,反复相减,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【大学课件】大学生职业生涯规划课件
- 小学英语五年级上册教学计划
- 2024年代理商业务协议样式
- 《欧洲旧石器》课件
- 五年级下册数学人教版第四单元 分数的意义和性质 单元测试
- 工作计划之学习计划书例文
- 高一物理下学期教材 高一物理第一学期教学计划
- 下半年妇委会工作计划
- 《光纤传感概论》课件
- 2024年广告位租赁协议
- 消费者调查访谈提纲模板
- 野菜文案策划方案
- 消化道肿瘤的诊断和治疗
- 嵌入式基础实训报告
- 软件定义网络(SDN)应用
- 我国农村土地承包经营权纠纷及其解决
- 《项目的范围管理》课件
- 《好作文的标准》课件
- 《华为投资控股公司财务风险防范的案例分析》15000字
- 林果产业发展实施方案
- 部编版六年级语文上册期末复习计划教案
评论
0/150
提交评论