辗转相除法与更相减损术.ppt
《辗转相除法与更相减损术.ppt》由会员分享,可在线阅读,更多相关《辗转相除法与更相减损术.ppt(14页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1 算 法 案 例23 学习目标学习目标 1.通过辗转相除法与更相减损术的学习通过辗转相除法与更相减损术的学习,进一步体会算法思进一步体会算法思想想 2.通过古代著名的算法通过古代著名的算法,理解掌握辗转相除法与更相减损术理解掌握辗转相除法与更相减损术算法的含义算法的含义;了解其计算过程了解其计算过程;了解其算法程序框图和程序了解其算法程序框图和程序41.1.回顾算法的三种表述:回顾算法的三种表述:自然语言自然语言程序框图程序框图程序语言程序语言(三种逻辑结构)(三种逻辑结构)(五种基本语句)(五种基本语句)2.2.思考:思考:小学学过的求两个数最大公约数的方法?小学学过的求两个数最大公约数的
2、方法?先用两个公有的质因数连续去除,一直除到所得的商是互为先用两个公有的质因数连续去除,一直除到所得的商是互为质数为止,然后把所有的除数连乘起来质数为止,然后把所有的除数连乘起来.复复 习习52525(1 1)5 55 535357 7所以,所以,2525和和3535的的最大公约数为最大公约数为5 54949(2 2)7 77 763639 9所以,所以,4949和和6363的的最大公约数为最大公约数为7 72 2、除了用这种方法外还有没有其它方法?、除了用这种方法外还有没有其它方法?算出算出82518251和和61056105的最大公约数的最大公约数.1 1、求两个正整数的最大公约数、求两个
3、正整数的最大公约数(1 1)求)求2525和和3535的最大公约数的最大公约数 (2 2)求)求4949和和6363的最大公约数的最大公约数61 1、辗转相除法(欧几里得算法)、辗转相除法(欧几里得算法)所谓辗转相除法所谓辗转相除法,就是对于给定的两个数就是对于给定的两个数,用较大的数除以较用较大的数除以较小的数小的数.若余数不为零若余数不为零,则将余数和较小的数构成新的一对数则将余数和较小的数构成新的一对数,继续继续上面的除法上面的除法,直到大数被小数除尽直到大数被小数除尽,则这时较小的数就是原来两个则这时较小的数就是原来两个数的最大公约数数的最大公约数.例例1.用辗转相除法求用辗转相除法求
4、98与与63的最大公约数的最大公约数.98=1633563=1 352835=1 28728=4 70所以,所以,98与与63的最大公约数为的最大公约数为7 7新新 课课7辗转相除法的原理:辗转相除法的原理:如果如果q q和和r r是是m m除以除以n n的商及余数的商及余数,即即 m m=n nq+q+r r,则则gcd(m,ngcd(m,n)=)=gcd(n,rgcd(n,r).).证明证明:设设 a=a=gcd(m,n),bgcd(m,n),b=gcd(n,rgcd(n,r)则有则有a|a|m m 及及a|a|n n,因此因此a|(m-nqa|(m-nq),),即即 a|ra|r及及a|
5、na|n,所以所以a|ba|b又又 b|b|r r及及b|b|n n,所以所以b|(nq+rb|(nq+r),),即即b|mb|m及及b|nb|n,所以所以b|ab|a因为因为a|ba|b并且并且b|ab|a,所以所以a=ba=b,即即gcd(m,ngcd(m,n)=)=gcd(n,rgcd(n,r).).如计算如计算 gcd(546,429)gcd(546,429)546=1 546=1429+117,429+117,429=3 429=3117+78,117+78,117=1 117=178+39,78+39,78=2 78=23939882518251=610561051+1+21462
6、146 61056105=214621462+2+18131813 21462146=181318131+1+33333318131813=3333335+5+148148333333=1481482+2+3737148148=37374 4所以所以3737是是82518251和和61056105的的最大公约数最大公约数 求求82518251和和61056105的最大公约数的最大公约数.P P4545)练习练习1(1)1(1)用辗转相除法用辗转相除法求求225225和和135135的最大公约数的最大公约数225225=1351351+1+9090135135=90901+1+45459090=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 辗转 除法 减损
限制150内