伤城文章网 > 数学 > 人教A版高中数学必修三 1.3 算法案例 课件 (共14张PPT)_图文

人教A版高中数学必修三 1.3 算法案例 课件 (共14张PPT)_图文


第一章 算法初步 1.3 算法案例 〖创设情景,揭示课题〗 案例1 辗转相除法与更相减损术 [问题1]:在小学,我们已经学过求最大公约数 的知识,你能求出18与30的最大公约数吗? 2 18 30 3 9 15 3 5 ∴18和30的最大公约数是2×3=6. 先用两个数公有的质因数连续去除,一直除到所 得的商是互质数为止,然后把所有的除数连乘起 来. 〖创设情景,揭示课题〗 [问题2]:我们都是利用找公约数的方法来求 最大公约数,如果两个数比较大而且根据我 们的观察又不能得到一些公约数,我们又应 该怎样求它们的最大公约数?比如求8251与 6105的最大公约数? 1.辗转相除法: 例1 求两个正数8251和6105的最大公约数。 解:8251=6105×1+2146; 6105=2146×2+1813; 2146=1813×1+333; 1813=333×5+148; 333=148×2+37; 148=37×4+0. 则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相 除法。也叫欧几里德算法,它是由欧几里德在 公元前300年左右首先提出的。 求18与30的最大公约数 ? 解∵30=18×1+12 ? 18=12×1+6 ? 12=6×2 ? ∴18与30的最大公约数是6 练习 ? 用辗转相除法求下列两个正整数的最大公约数 ? ①225 135 ②98 196 ③72 168 ④153 119 ? 答案:45 98 24 17 总结辗转相除法方法 ? 用大数除以小数得到商和余数,接着用除数除以 余数得到商和余数,依次计算下去,直到余数为 零,最后式子的除数是所求的最大公约数。 2.更相减损术: 我国早期也有解决求最大公约数问题的算 法,就是更相减损术。 更相减损术求最大公约数的步骤如下:可 半者半之,不可半者,副置分母、子之数,以 少减多,更相减损,求其等也,以等数约之。 翻译出来为:第一步:任意给出两个正数; 判断它们是否都是偶数。若是,用2约简;若不是, 执行第二步。 第二步:以较大的数减去较小的数,接着把 较小的数与所得的差比较,并以大数减小数。继 续这个操作,直到所得的数相等为止,则这个数 (等数)就是所求的最大公约数。 例题 ? 用更相减损术求两个正整数的最大公约数 ? 18与30 ? 解 ∵18÷2=9 30÷2=15 ? 15-9=6 ? 9-6=3 ? 6-3=3 ? ∴18与30的最大公约数是3×2=6 例2 用更相减损术求98与63的最大公约数. 解:由于63不是偶数,把98和63以大数 减小数,并辗转相减, 即:98-63=35; 63-35=28; 35-28=7; 28-7=21; 21-7=14; 14-7=7. 所以,98与63的最大公约数是7。 练习2:用更相减损术求两个正数84与72的最大 公约数。 (12) 练习 ? 用更相减损术法求下列两个正整数的最大公约数 ? ①225 135 ②98 196 ③72 168 ④153 119 辗转相除法求最大公约数算法步骤: ? 第一步,给定两个正整数m,n(m>n) ? 第二步,计算m除以n所得到余数r ? 第三步,m=n,n=r ? 第四步,若r=0,则m,n的最大公约数等于m;否则 返回第二步 程序框图 开始 输入两个正数m,n r=m MOD n m=n n=r 否 r=0? 是 输出m 结束 小结 ? 1、辗转相除法方法 ? 2、更相减损术的步骤: ? 第一步 任意给

搜索更多“人教A版高中数学必修三 1.3 算法案例 课件 (共14张PPT)_图文”

网站地图

All rights reserved Powered by 伤城文章网 5xts.com

copyright ©right 2010-2021。
伤城文章网内容来自网络,如有侵犯请联系客服。zhit325@126.com