必修3-1-8 辗转相除法与更相减损术.pptVIP

欢迎同学们！ 重庆市鱼洞中学校 ------杜在华 辗转相除法与更相减损术 动手实践: 例1 深入理解: P34-35 辗转相除法 合作学习: 例2 合作学习: P35思考 合作学习: P35思考 合作学习: P36思考 深入理解: P36-37更相减损术 合作学习:例3. 勇攀高峰: P37思考 勇攀高峰: P37思考 小结: 学后反思: 谢谢同学们认真上课！ 积极思考！ * * * 请同学们作好课前准备！ 请大家保持安静！ 理解辗转相除法和更相减损术,能够利用辗转相除法和更相减损术求两个数的最大公约数,通过辗转相除法和更相减损术案例,进一步体会算法思想. 学习重点: 辗转相除法(欧几里德算法),更相减损术. 学习目标: 必修3 P34～37 自主学习: P34-35 例1.求18和30的最大公约数. 解法一:(分解质因数) 18=2×9=2×3×3, 30=5×6=5×2×3, ∴18和30的最大公约数为 gcd(18,30)=2×3=6. 解法二:(短除法:先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来即为最大公约数.) 18 30 2 9 15 3 3 5 ∴18和30的最大公约数为 gcd(18,30)=2×3=6. 模仿学习: 例2.用辗转相除法求下列两个数的最大公约数: 1.带余除法: 被除数=除数×商＋余数 结论:如果n和r的最大公约数为x,那么x一定也是m的约数. 故n,r的最大公约数也是m,n的最大公约数. gcd(m,n)=gcd(n,r) 例如: 48=6×7＋6, 48=42＋6, 42与6的最大公约数6也是48的约数, 即 gcd(48,42)=gcd(42,6)=6. 2.辗转相除法: 被除数和除数的最大公约数也是除数和余数的最大公约数. (1)225与135; (2)72与168; (3)119与153. m=n×q＋r 即 ,(0≤r＜n) 例2.用辗转相除法求下列两个数的最大公约数: (1)225与135; (2)72与168; (3)119与153. 解: 225=135×1＋90, 135=90×1＋45, 90=45×2＋0, ∴ gcd(225,135)= gcd(135,90) =gcd(90,45) =45 注意:用较大的整数除以较小的整数,直到余数为0. 解: 168=72×2＋24, 72=24×3＋0, ∴ gcd(72,168)= gcd(72,24) =24 解: 153=119×1＋34, 119=34×3＋17, 34=17×2＋0, ∴ gcd(119,153)= gcd(119,34) =gcd(34,17) =17 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法. 思考:你能把辗转相除法求两个正整数m,n的最大公约数编成一个计算机程序吗? 第一步,给定两个正整数m,n(mn). 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. 第四步,若r=0,则m,n的最大公约数等于m,否则,返回第二步. 算法: 思考:你能把辗转相除法求两个正整数m,n的最大公约数编成一个计算机程序吗? 程序框图: 开始 输入m，n 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束 否 INPUT m，n DO r=m MODn m=n n=r LOOP UNTIL r=0 PRINT m END 程序: 自主学习: P36-37 思考:你能用当型循环结构构造算法,求两个正整数m,n的最大公约数?试写出算法步骤、程序框图和程序. 程序框图: 开始 输入m，n 求m除以n的余数r m=n n0？ 否 输出m 结束 是 n=r 程序: INPUT m，n WHILE n0 r=m MODn m=n n=r WEND PRINT m END 模仿学习: 例3 1.减法: 被减数－减数＝差, 即 ,(a＞b). a-b=c 结论:如果a与b的最大公约数为x,那么x也是c的约数. 即x是a,b,c的公约数. 故 a,b的最大公约数也是b,c的最大公约数. 2.更相减损术: 被减数与减数的最大公约数也是减数与差的最大公约数. gcd(a,b)=gcd(b,c) 了解:“更相减损术”在中国古代数学专著《九章算术》中记述为:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之. 例3.用更相减损术求下列两个