《高中数学1.4算法案例第2课时教案苏教版必修3》由会员分享，可在线阅读，更多相关《高中数学1.4算法案例第2课时教案苏教版必修3（8页珍藏版）》请在金锄头文库上搜索。
1、高中数学1.4 算法案例第2 课时教案苏教版必修3 - 1 - / 8 1.4 算法案例第 2 课时 重点难点 重点 ：通过案例分析理解辗转相除法与更相减损术求最大公约数的方法，体会算法思想. 难点 ：把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 学习要求 1理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析. 2基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序. 【课堂互动】 问题： 写出求两个正整数a,b(ab) 的最大公约数的一个算法。 1. 辗转相除法 公元前 3 世纪，欧几里得介绍了求两个正整数a,b(ab) 的最大公约数的方法，求
2、出一列数： 0, 121nn rrrrba，这列数从第三项开始，每一项都是前两项相除所得的余数（即 ),( 12nnn rrModr） ， 余数等于 0 的前一项 n r， 即是 a 和 b 的最大公约数， 这种方法称为 “欧 几里得辗转相除法” 。 例 1 求两个正数8 251 和 6 105 的最大公约数 （分析： 8 251 与 6 105 两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根 据已有的知识即可求出最大公约数） 【解】 8 251 6 105 12 146 显然 8 251 和的 2 146 最大公约数也必是2 146 的约数，同样6 105 与 2 146 的公
3、约数也 必是 8 251 的约数，所以8 251 与 6 105 的最大公约数也是6 105 与 2 146 的最大公约数 6 105 214621813 2 146 18131333 1 813 3335 148 333148237 1483740 则 37 为 8 251 与 6 105 的最大公约数 【小结】以上我们求最大公约数的方法就是欧几里得辗转相除法其求最大公约数的步骤如 下： 第一步： 用较大的数m除以较小的数n, 得到一个商 0 q和一个余数 0 r； 第二步：若 0 0r， 则n为,m n的最大公约数；若 0 0r，则用除数n除以余数 0 r, 得到一个商 1 q和一个余数
4、1 r； 第三步：若 1 0r，则 1 r为,m n的最大公约数；若 1 0r，则用除数 0 r除以余数 1 r得到一 个商 2 q和一个余数 2 r； 依次计算直至0 n r，此时所得到的 1n r 即为所求的最大公约数. 【练习】求a=204，b=85 的最大公约数，步骤为： S1 20485 的余数为34， S2 8534 的余数为17， S3 3417 的余数为0。 所以它们的最大公约数为17。 算法描述：计算出ab 的余数 r，若 r=0，则 b 为 a，b 的最大公约数；若 r0，则把前 高中数学1.4 算法案例第2 课时教案苏教版必修3 - 2 - / 8 面的除数b 作为新的被
5、除数，把余数r 作为新的除数（a，b 要重新赋值， ab，br） ，继续 进行上述运算，直到余数为0(用 While 循环语句，循环的执行条件是r0，当 r=0 时，循环终 止)，此时的除数即为所求的最大公约数。 算法如下 : S1 输入两个正整数a,b(ab) ； S2 若 Mod(a，b)=0 ，则转 S3；否则， rMod(a,b)， ab， br，转 S2。 S3 输出最大公约数b. 【流程图】 【伪代码】 2.更相减损法 我国早期也有解决求最大公约数问题的算法，就是更相减损术更相减损术求最大公约数 的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以 等数
6、约之 翻译出来为： Read a,b While Mod(a,b) 0 rMod(a,b) ab br End While Print b 开始 br Y N 结束 输入 a，b ab rMod(a,b) Mod(a,b) 0 输出 b 高中数学1.4 算法案例第2 课时教案苏教版必修3 - 3 - / 8 第一步：任意给出两个正数, 判断它们是否都是偶数若是，用2 约简；若不是，执行第 二步 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数 继 续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数 再从这个角度看一下“求a=204，b=85 的最
7、大公约数”的问题，S1 步可以等价为等式： 34285204。S2 步可以等价为等式：1723485。这两步从减法的角度可以理解 为： 204-85 ，所得的差与减式中的较小数比较，再用大的数减小的数，循环执行以上步骤, 直 到结果为0。此时减数就是a 和 b 的最大公约数。这一算法根据它的特点，也可以用循环语句 完成。 参考代码 ： /a放较大的数， b 放较小的数 If a r Then a b b r Else a r End If r a b / 确保相减后仍用较大的数减去较小的数 End While Print b 用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性 【小结
8、】比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计 算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较 明显 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0 则得到，而更相减损术则 以减数与差相等而得到 【追踪训练】 1.分析下面一段代码的目的： Read m,n While m/n Int(m/n) cm- Int(m/n) n mn n c End While Print n (Int(x)表示不超过x 的最大整数 ) 【解】求 m，n 的最大公约数。 高中数学1.4 算法案例第
9、2 课时教案苏教版必修3 - 4 - / 8 2.用辗转相除法求下列各组数的最大公约数。 （1）225,135; （2）98,196. 3.用更相减损法求下列各组数的最大公约数。 （31）72 ,168; （2）153,119. 4. 现有长度为360cm 和 780cm 两种规格的钢筋若干.要焊接一批正方形模型.问:怎样才能保证 正方体体积最大且不浪费? 思路点拨 : 正方体的所有棱长都相等,故必须将钢筋剪裁成长度相等的钢筋条;又必须不浪费, 这就说明必须剪后无剩余.于是为了保证正方体的体积最大,故剪的钢筋的最大长度为360cm 和 780cm 的最大公约数,可用更相减损术求最大公约数. 第
10、 11 课时算法案例 (2) 分层训练 1、阅读下列代码，写出该代码的运行结果 t1 n3 高中数学1.4 算法案例第2 课时教案苏教版必修3 - 5 - / 8 s0 Wh ile s10 ttn s s+t End WhilePrint s 答： 2、设计一个计算1357 9 的算法下面给出了程序的一部分，则在横线上不能填入下 面数据中的 ( ) Sl I3 While I S SI II+2 End While Print S A9 B95 C 10 D10.5 3、下列一段伪代码执行结束后S的目的是 ( ) S0 al For I From l To 4 a2a S S+a End F
11、or A计算 2+22+23+24B计算 2+22+23C计算 23D计算 24 4. 先用不同的算法计算 1111 1 2233499 100 ，再比较其优劣。 5. 已知 ABC中,ABc BCa CAb，试写出作 ABC的一个算法。 6. 用条件语句表示：输入x 的值，通过 1 24(, 2 2( 2,2) 22,) x xx yxx x 计算 y 的值。 高中数学1.4 算法案例第2 课时教案苏教版必修3 - 6 - / 8 7. 写出求 123100 ,a aaa中最大数的一个算法。 8、一球从l00m 高度落下，每次落地后反弹回原高度的一半，再落下，在第十次落地时，共 经过多少路程
12、?第十次下落多高? 思考 ?运用 9. 我国古代劳动人民对不定方程的研究作出过重要贡献，其中张丘建算经中的百鸡 问题就是一个很有影响力的问题：“今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百 钱买百鸡，问鸡翁、母、雏各几何？” 其意思是：一只公鸡的价钱是五钱，一只母鸡的价钱是三钱，三只小鸡的价钱是一钱。 现在用一百钱买一百鸡，可以买公鸡、母鸡、小鸡各几个？ 这是一个不定方程的整数解问题，假设公鸡x 只，母鸡 y 只，小鸡 z 只，首先，可以大致 得到 x 在 1 至 20 之间， y 在 1 至 33 之间， z=100-x-y 可以确定。 根据上 述算法思想，画出求解的流程图，并写出相应的伪代码。 高中数学1.4 算法案例第2 课时教案苏教版必修3 - 7 - / 8 高中数学1.4 算法案例第2 课时教案苏教版必修3 - 8 - / 8
