算法案例-辗转相除法与更相减损术秦九韶算法与进位制件数学高一必修3算法初步13人教A版.pptx
《算法案例-辗转相除法与更相减损术秦九韶算法与进位制件数学高一必修3算法初步13人教A版.pptx》由会员分享,可在线阅读,更多相关《算法案例-辗转相除法与更相减损术秦九韶算法与进位制件数学高一必修3算法初步13人教A版.pptx(48页珍藏版)》请在咨信网上搜索。
1、1.理解辗转相除法与更相减损术求最大公约数的方法理解辗转相除法与更相减损术求最大公约数的方法.2.理解秦九韶算法中求多项式的值的步骤原理理解秦九韶算法中求多项式的值的步骤原理.3.能利用除能利用除 k 取余法把十进制数化为取余法把十进制数化为 k 进制数进制数.1.辗转相除法的算法步骤第一步,给定两个正整数 m,n(mn).第二步,计算_除以_所得的_数 r.第三步,mn,nr.第四步,若 r0,则 m,n 的最大公约数等于_;否则,返回第二步.mn余n2.更相减损术的算法步骤第一步,任意给定两个正整数,判断它们是否都是偶数.若是用 2 约简;若不是,执行第二步.第二步,以较大的数减去较小的数
2、,接着把所得的差与_比较,并以大数减小数.继续这个操作,直到所得的数_为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.较小的数相等3.秦九韶算法把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式:(anxn1an1xn2a1)xa0f(x)anxnan1xn1a1xa0_(anxn2an1xn3a2)xa1)xa0_.(anxan1)xan2)xa1)xa0求多项式的值时,首先计算最内层括号内的一次多项式的值,即v1anxan1,然后由内向外逐层计算一次多项式的值,即:n这样,求 n 次多项式 f(x)的值就转化为求_个一次多项式的值.v1anxan1,v
3、2_,v3v2xan3,vn_,v1xan2vn1xa04.进位制(1)k进制数anan1a1a0(k)转化为十进制数为_.(2)把十进制数化为 k 进制数用“_”,即把所给的十进制数除以_,得到商数和余数,再用商数除以 k,得到商数和余数,直到商数为_,把上面各步所得的_从右到左排列,即得到 k 进制数.除 k 取余法k0余数anknan1kn1a1ka0【问题导思问题导思】1如何求如何求18与与54的最大公约数?的最大公约数?【提示提示】短除法短除法2要求要求6 750与与3 492的最大公约数,上述法还好用吗?的最大公约数,上述法还好用吗?【提示提示】数值太大,短除法不方便用数值太大,短
4、除法不方便用知识知识1 求两个正整数最大公约数的算法求两个正整数最大公约数的算法(1)更相减损之术更相减损之术(等值算法等值算法)用两个数中较大的数减去较小的数,再用用两个数中较大的数减去较小的数,再用和和构成新的一对数,对这一对数再用构成新的一对数,对这一对数再用减减,以同样的操作一直做下去,直,以同样的操作一直做下去,直到产生到产生,这个数就是最大公约数,这个数就是最大公约数(2)辗转相除法辗转相除法(欧几里得算法欧几里得算法)用较大的数除以较小的数所得的用较大的数除以较小的数所得的和和_构成新的一对数,继续做上面的除法,直到构成新的一对数,继续做上面的除法,直到,这个较小的数就是最大公约
5、数,这个较小的数就是最大公约数.差数差数较小的数较小的数大数大数小数小数一对相等的数一对相等的数余数余数较小的数较小的数大数被小数除尽大数被小数除尽【问题导思问题导思】1怎样计算多项式怎样计算多项式f(x)x5x4x3x2x1当当x5时时的值呢?统计所做的计算的种类及计算次数分别是什么?的值呢?统计所做的计算的种类及计算次数分别是什么?【提示提示】f(5)55545352513 906.根据我根据我们的计算统计可以得出我们共需要们的计算统计可以得出我们共需要10次乘法运算,次乘法运算,5次加法运次加法运算算知识知识2 秦九韶算法秦九韶算法2我们把多项式变形为我们把多项式变形为f(x)x2(1x
6、(1x(1x)x1,再统计一下计算当,再统计一下计算当x5时的计算的种类及计算次数分别是时的计算的种类及计算次数分别是什么?什么?【提示提示】从里往外计算仅需从里往外计算仅需4次乘法和次乘法和5次加法运算即次加法运算即可得出结果可得出结果(1)把一元把一元n次多项式次多项式P(x)anxnan1xn1a1xa0改写为改写为P(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0,令令vk(anxan1)xan(k1)xank,(2)计算计算P(x0)的方法的方法先计算先计算,然后,然后逐层计算
7、,逐层计算,直到直到,然后加上,然后加上最内层括号最内层括号由内向外由内向外最外层括号最外层括号常数项常数项知识知识3 进位制进位制 进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.使用数字符号的个数称为基数,基数为 n,即称为n 进位制,简称 n 进制.现在最常用的是十进制,通常使用 10 个阿拉伯数字 09 进行记数.例例1.分别用辗转相除法和等值算法求分别用辗转相除法和等值算法求319和和261的最大公的最大公约数约数【分析分析】使用辗转相除法可依据使用辗转相除法可依据mnqr,反复执行,反复执行,直到直到r0为止;用等值算法是根据为止;用等值算法是根据mnr,直到,直到n
8、1为止为止【解析解析】辗转相除法:辗转相除法:3192611(余余58),261584(余余29),58292(余余0)所以所以319与与261的最大公约数是的最大公约数是29.等值算法:等值算法:31926158,26158203,20358145,1455887,875829,582929.即即(319,261)(261,58)(203,58)(145,58)(87,58)(58,29)(29,29)所以所以319与与261的最大公约数是的最大公约数是29.1利用利用“等值算法等值算法”求给定的两个数的最大公约数,即求给定的两个数的最大公约数,即多次利用减法,用数对中较大的数减去较小的数,
9、直到相减多次利用减法,用数对中较大的数减去较小的数,直到相减的差与数对中较小的数相等为止的差与数对中较小的数相等为止2更相减损之术的步骤:更相减损之术的步骤:(1)判断两数是否都为偶数,若是,则都除以判断两数是否都为偶数,若是,则都除以2直到所得直到所得两数不全为偶数两数不全为偶数(2)用较大的数减去较小的数,将差和较小的数构成一对用较大的数减去较小的数,将差和较小的数构成一对新数,继续用较大数减去较小数,重复执行新数,继续用较大数减去较小数,重复执行(3)当差和较小数相等时,结束执行,此时差当差和较小数相等时,结束执行,此时差(或较小数或较小数)为不全为偶数的两数的最大公约数为不全为偶数的两
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 案例 辗转 除法 减损 术秦九韶 进位 制件 数学 必修 初步 13 人教
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
链接地址:https://www.zixin.com.cn/doc/4185361.html