9299.net
大学生考试网 让学习变简单
赞助商链接
当前位置:首页 >> 数学 >>

1.3算法案例(一)辗转相除法

1.3算法案例(一)辗转相除法


1.3算法案例(一)
辗转相除法

复习提问:
小学学过的求两个数的最大公约数的方法:

先用两个数公有的 质因数 连续去除,
一直除到所得的商是 互质数 为止,

然后把所有的除数 连乘 起来.

例如:求18与30的最大公约数.
2 3 18 9 3 30 15 5

所以18与30的最大公约数是2×3=6

1、辗转相除法
例1、用辗转相除法 求8251与6105的最大公因数
8251=6105×1+2146 6105=2146×2+1813

2146=1813×1+333 1813=333×5+148
333=148×2+37 148=37×4 8251与6105的最大公因数是37

辗转相除法:
给定两个正数,用 较大的数 除以 较小的数 ,
求得 商 和 余数 ,若余数不为零,则将

较小数 和 余数

构成新的一对数继续上面

的除法,直到大数被小数除尽,这时的 较小数

就是原来两数的最大公约数。

练习:
? 教材:45页——1

2、辗转相除法计算的程序框图及程序
算法步骤: ? 第一步,给定两个正整数m,n. ? 第二步,比较m,n的大小,若n>m则交换 m,n,否则直接执行下一步. ? 第三步,计算m除以n所得的余数r. ? 第四步,m=n,n=r. ? 第五步,若r=0,则m,n的最大公约数等于m; 否则,返回第三步.

程序框图

开始 输入m,n





求m除以n的余数r

m<n? 是
m=n t=m n=r

m=n n=t
r=0? 是 输出m




结束

程序语言

INPUT m,n IF n>m THEN t=m m=n n=t END IF DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END

练习:
? 教材48页——1



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com