辗转相除法和更相减损术.ppt
《辗转相除法和更相减损术.ppt》由会员分享,可在线阅读,更多相关《辗转相除法和更相减损术.ppt(16页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、算法案例之辗转相除法与更相减损术“古 今 中 外”数学大风暴大同一中高一数学计琳自主学习成果检验分别用辗转相除法和更相减损术求470和282的最大公约数。更相减损术由于282和470都是偶数,则需用2约简得:141和235辗转相除法(1)辗转相除法,又叫欧几里得法,提出于公元前300年左右,是一种求两个正整数的最大公约数的古老而有效的算法。(2)辗转相除法是指对于给定的两个数,用大数除以小数,若余数不为零,则将余数和较小数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时小数就是原来两个数的最大公约数。更相减损术更相减损术是我国古代数学专著九章算术中介绍的一种求两个数的最大公约数的算法
2、.提出于公元一世纪左右。“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之”问题一:辗转相除法的关键步骤是做带余除法:被除数=除数商+余数。其中被除数、除数和除数、余数有相同的最大公约数,即:gcd(被除数,除数)=gcd(除数,余数),为什么呢?gcd(470,282)=gcd(282,188)=gcd(188,94)=94已知,求证:下面说明c为最大公约数,即:与b互质令,则设,故c也为n和r的约数。与有公约数cd,且cdc。与产生矛盾(反证法)假设,则假设不成立,原结论成立问题二:两种算法中,带余除法和减法分别进行到什么时候为止?为什么?辗转相除法中,带余
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 辗转 除法 减损
限制150内