《1..3算法案例(教、教案).pdf》由会员分享,可在线阅读,更多相关《1..3算法案例(教、教案).pdf(12页珍藏版)》请在三一文库上搜索。
1、- 1 - / 12 1. 3算法案例 【教学目标】: 1. 理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这 些原理进行算法分析。 2. 基本能根据算法语句与程序框图的知识设计完整的程序框图并 写出算法程序。 【教学重难点】: 重点:理解辗转相除法与更相减损术求最大公约数的方法。 难点:把辗转相除法与更相减损术的方法转换成程序框图与程序 语言。 【教学过程】: 情境导入: 1. 教师首先提出问题:在初中,我们已经学过求最大公约数的知 识,你能求出 18 与 30 的公约数吗? 2. 接着教师进一步提出问题,我们都是利用找公约数的方法来求 最大公约数,如果公约数比较大而且根据我们的观察又
2、不能得到一些 公约数,我们又应该怎样求它们的最大公约数?比如求8251 与 6105 的最大公约数?这就是我们这一堂课所要探讨的内容。ZnwB6NobTj 新知探究: 1. 辗转相除法 例 1 求两个正数 8251 和 6105的最大公约数。 表 示二进制数 ,34(5 表示 5 进制数. ZnwB6NobTj 化成十进制数 解:根据进位制的定义可知 012345 )2( 212120202121110011 121161321 51 所以,110011 (1用较大的数 m除以较小的数 n 得到一个商 0 S和一个余数 0 R; (2若 0 R0, 则 n 为 m,n 的最大公约数;若 0 R
3、0, 则用除数 n 除 以余数 0 R得到一个 1 S 和一个余数 1 R;(3若 1 R0, 则 1 R 为 m,n 的最大公约数 ; 若 1 R0, 则用 除数 0 R除以余数 1 R得到一个商 2 S和一个余数 2 R;依次计算直至 n R 0,此时所得到的 1n R即为所求的最大公约数 . ZnwB6NobTj 例题 1:求两个正数 1424 和 801 的最大公约数 . 以上我们求最大公约数的方法就是辗转相除法,也叫欧几里德 算法. 由上述步骤可以看出,辗转相除法中的除法是一个反复执行的 步骤,且执行次数由余数是否等于 0 来决定, 所以可把它看成一循环 体, 写出辗转相除法完整的程
4、序框图和程序语言. ZnwB6NobTj 教学更相减损术:我国早期也有求最大公约数问题的算法,就是 更相减损术 . 在九章算术中有更相减损术求最大公约数的步 骤:可半者半之,不可半者,副置分母?子之数,以少减多,更相减 损,求其等也,以等数约之. ZnwB6NobTj 翻译为: (1 任意给出两个正数;判断它们是否都是偶数. 若 是,用 2 约简;若不是,执行第二步 . (2 以较大的数减去较小的数,接着把较小的数与所得的差 比较,并以大数减小 数. 继续这个操作,直到所得的数相等为止,则这个数 化成十进制数 精讲点拨: 1求两个正数 8251 和 2146;228 和 1995;5280 和
5、 12155 的最大公 约数. 2 求两个正数 8251 和 2146的最大公约数 . 3. 用秦九韶算法计算多项式 在 x=-4 时的值时 , V3的值为 : 反思总结: 比较辗转相除法与更相减损术的区别 (1都是求的方法,计算上辗转相除法以法为主, 更相减损术以法为主,计算次数上法计算次数相对 较少,特别当两个数字时计算次数的区别较明 显ZnwB6NobTj (2 从 结 果 体 现 形 式 来 看 , 辗 转 相 除 法 体 现 结 果 是 以 则得到,而更相减损术 则以而得到 (3通过对秦九韶算法的学习,你对算法本身有哪些进一步认识? (4秦九韶算法在计算一个n 次多项式的值时,只要做_次乘法 - 12 - / 12 运算和_次加法运算。 课后练习与提高 1、用“辗转相除法”求得459和 357 的最大公约数是: A3 B9 C17 D51 2、将数转化为十进制数为: A. 524 B. 774 C. 256 D. 260 3、用秦九韶算法计算多项式 当时的值时 ,需要做乘法和加法的次数分别是: A. 6 , 6 B. 5 , 6 C. 5 , 5 D. 6 ,5 参考答案 :1D 2B 3A 申明: 所有资料为本人收集整理,仅限个人学习使用,勿做商业用途。
链接地址:https://www.31doc.com/p-4516344.html