广东省佛山市中大附中三水实验中学高三数学《辗转相除法与更相减损术》基础复习课件 新人教A版.ppt_第1页
广东省佛山市中大附中三水实验中学高三数学《辗转相除法与更相减损术》基础复习课件 新人教A版.ppt_第2页
广东省佛山市中大附中三水实验中学高三数学《辗转相除法与更相减损术》基础复习课件 新人教A版.ppt_第3页
广东省佛山市中大附中三水实验中学高三数学《辗转相除法与更相减损术》基础复习课件 新人教A版.ppt_第4页
广东省佛山市中大附中三水实验中学高三数学《辗转相除法与更相减损术》基础复习课件 新人教A版.ppt_第5页
已阅读5页，还剩9页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法案例 第一课时 辗转相除法与更相减损术 学习目标 掌握辗转相除法与更相减损术求最大公约数 1 求两个正整数的最大公约 1 求25和35的最大公约数 2 求49和63的最大公约数 2 求8251和6105的最大公约数 所以 25和35的最大公约数为5 所以 49和63的最大公约数为7 辗转相除法 欧几里得算法 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数 求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的公约数就可以了 第二步对6105和2146重复第一步的做法6105 2146 2 1813同理6105和2146的最大公约数也是2146和1813的最大公约数 为什么呢 思考 从上述的过程你体会到了什么 完整的过程 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 例2用辗转相除法求225和135的最大公约数 225 135 1 90 135 90 1 45 90 45 2 显然37是148和37的最大公约数 也就是8251和6105的最大公约数 显然45是90和45的最大公约数 也就是225和135的最大公约数 思考1 从上面的两个例子可以看出计算的规律是什么 s1 给定两个正整数m n s2 用大数除以小数 计算m除以n所得的余数 s3 除数变成被除数 余数变成除数 即m n n r s4 重复s2 直到余数为0 即若r 0 则m n的最大公约数为m 否则返回s2 辗转相除法是一个反复执行直到余数等于0停止的步骤 这实际上是一个循环结构 m n q r 用程序框图表示出右边的过程 r mmodn m n n r r 0 是 否 思考2 辗转相除法中的关键步骤是哪种逻辑结构 练习1 利用辗转相除法求两数153与119的最大公约数 思考 你能用当型循环结构构造算法 求两个正整数的最大公约数吗 写出算法步骤 程序框图和程序 九章算术 更相减损术 算理 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 第一步 任意给定两个正整数 判断他们是否都是偶数 若是 则用2约简 若不是则执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的减数和差相等为止 则这个等数就是所求的最大公约数 例3用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7 所
人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论