高中数学新课标人教A版必修3课件算法案例(辗转相除法)_图文

算 法 案 例 辗转相除法 (第一课时) 1、求两个正整数的最大公约数 (1)求25和35的最大公约数 (2)求49和63的最大公约数 5 25 35 ( 1) 5 7 所以,25和35的 最大公约数为5 7 49 63 ( 2) 7 9 所以,49和63的 最大公约数为7 2、求8251和6105的最大公约数 辗转相除法(欧几里得算法) 观察求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 例2 用辗转相除法求225和135的最大公约数 225=135×1+90 135=90×1+45 90=45×2 显然45是90和45的最大公约数,也就是 225和135的最大公约数 1813=333×5+148 333=148×2+37 148=37×4+0 思考1:从上面的两个例子可以 看出计算的规律是什么? S1:用大数除以小数 S3:重复S1,直到余数为0 显然37是148和37的最大 公约数,也就是8251和 6105的最大公约数 S2:除数变成被除数,余数变成除数 利用辗转相除法求两数4081与20723的最大公约数 思考:你能把辗转相除法编成程序吗? 算法1: 第一步:任意给定两个正整数; 第二步:用两数中较大那个除以较小那个,求得 商和余数; 第三步:比较上一步的余数与除数的大小关系, 继续用较大数除以较小数,并一直重复 上述步骤直到余数为0,则此时的除数即 为所求. 算法2: 第一步:任意给定两个正整数,大的数记为m, 小的记为n; 第二步:用m除以n,求得余数r; 第三步:判断r是否为0,若r=0,则输出n, 若r≠0,则令m=n,n=r,再返回第二步. 辗转相除法是一个反复执行直到余数等于0停止 的步骤,这实际上是一个循环结构。m = n × q + r 用程序框图表示出右边的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 r=m MOD n m=n n=r r=0? 否 是 333=148×2+37 148=37×4+0 算法2: 程序: INUPU m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 开始 输入m,n r=m MOD n m=n n=r r=0? 是 否 输出m 结束 算法1: 程序: INUPU m,n IF m<n THEN x=m m=n n=x END IF DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 开始 输入m,n 是 m<n? 否 x=m,m=n,n=x r=m MOD n m=n n=r r=0? 是 否 输出m 结束

相关文档

高中数学人教课标版必修三《算法案例:辗转相除法与更相减损术》教学课件
人教版高中数学必修三算法案例(辗转相除法和更相减损术)ppt课件
人教A版高中数学必修三课件:1-3算法案例 第8课时 辗转相除法与更相减损术
高中数学新课标人教A版必修3课件1.3案例(进位制)
百强名校人教高中数学精品课件_《算法案例--辗转相除法与更相减损术》课件(1)(新人教A版必修3)(整理版)
高中数学人教版A必修3课件:1.3算法案例 第1课时 辗转相除法与更相减损术、秦九韶算法
高中数学新课标人教版必修3课件: 算法的概念二
电脑版