高一数学 131(算法案例——辗转相除法与更相减损术) 课件VIP免费

1.3 算法案例 第一课时 问题提出t57301p2 1. 研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开 . 在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？ 2.“ 求两个正整数的最大公约数”是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究 .知识探究（一） : 辗转相除法思考 1:18 与 30 的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数 . 思考 2: 对于 8251 与 6105 这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难 . 注意到8251=6105×1+2146 ，那么 8251 与 6105这两个数的公约数和 6105 与 2146 的公约数有什么关系？ 思考 3: 又 6105=2146×2+1813 ，同理， 6105 与 2146 的公约数和 2146 与1813 的公约数相等 . 重复上述操作，你能得到 8251 与 6105 这两个数的最大公约数吗？2146=1813×1+333 ，148=37×4+0.333=148×2+37 ，1813=333×5+148 ，8251=6105×1+2146 ，6105=2146×2+1813 ， 辗转相除法是一个反复执行直到余数等于 0 停止的步骤，这实际上是一个循环结构。8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m = n × q ＋ r用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否思考 5: 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法 . 一般地，用辗转相除法求两个正整数 m ， n 的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数 m ， n(m>n).第二步，计算 m 除以 n 所得的余数 r. 第三步， m=n ， n=r.第四步，若 r=0 ，则 m ， n 的最大公约数等 于 m ；否则，返回第二步 . 思考 5: 该算法的程序框图如何表示？开始输入 m ， n求 m 除以 n 的余数rm=nn=rr=0 ？是输出 m结束否思考 6: 该程序框图对应的程序如何表述？INPUT m ， nDOr=m MODnm=nn=rLOOP UNTIL r=0PRINT mEND开始输入 m ， n求 m 除以 n 的余数rm=nn=rr=0 ？是输出 m结束否思考 7: 如果用当型循环结构构造算法，则用辗转相除法求两个正整数 m ， n 的最大公约数的程序...