2022年算法案例.docx

《2022年算法案例.docx》由会员分享，可在线阅读，更多相关《2022年算法案例.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习1.3 算法案例【教学目标】：1. 懂得辗转相除法与更相减损术中包蕴地数学原理,并能依据这些原理进行算法分析. . 2. 基本能依据算法语句与程序框图地学问设计完整地程序框图并写出算法程序【教学重难点】：重点：懂得辗转相除法与更相减损术求最大公约数地方法 . 难点：把辗转相除法与更相减损术地方法转换成程序框图与程序语言 . 【教学过程】：情境导入：18 与 30 1. 老师第一提出问题：在中学,我们已经学过求最大公约数地学问,你能求出 地公约数吗？2. 接着老师进一步提出问题,我们都是利用找公约数地方法来求最大公约数,

2、假如公约 数比较大而且依据我们地观看又不能得到一些公约数,我们又应当怎样求它们地最大公约数？比如求8251 与 6105 地最大公约数？这就是我们这一堂课所要探讨地内容.新知探究：1. 辗转相除法 例 1 求两个正数 8251 和 6105 地最大公约数 . （分析： 8251 与 6105 两数都比较大,而且没有明显地公约数,如能把它们都变小一 点,依据已有地学问即可求出最大公约数）解： 82516105 12146 2146 地约数,同样 6105 与 2146 地公约数也必是 8251 地 明显 8251 地最大公约数也必是 约数,所以 8251 与 6105 地最大公约数也是 6105

3、 与 2146 地最大公约数 .61052146 2 1813 21461813 1 333 1813333 5148 333148 237 14837 40 就 37 为 8251 与 6105 地最大公约数 . 以上我们求最大公约数地方法就是辗转相除法. 也叫欧几里德算法,它是由欧几里德在公元前 300 年左右第一提出地. 利用辗转相除法求最大公约数地步骤如下：n 除以余数r0 得到第一步：用较大地数m除以较小地数n 得到一个商q0 和一个余数r0；其次步：如r00,就 n 为 m, n 地最大公约数；如r0 0,就用除数一个商 q1和一个余数r 1；r0除以余数r1 得到第三步：如r10

4、,就 r1为 m,n 地最大公约数；如r1 0,就用除数一个商 q2和一个余数r 2； 依次运算直至 r n0,此时所得到地 r n-1 即为所求地最大公约数 . 练习：利用辗转相除法求两数 4081 与 20723 地最大公约数（答案：53）2. 更相减损术我国早期也有解决求最大公约数问题地算法,就是更相减损术 . 更相减损术求最大公约数地步骤如下：可半者半之,不行半者,副置分母 子之数,以- 1 - / 10 名师归纳总结 - - - - - - -第 1 页,共 10 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习少减多,更相减损,求其等也,以等数约之 .

5、翻译出来为：第一步：任意给出两个正数；判定它们是否都是偶数 二步 . . 如是,用 2 约简；如不是,执行第其次步：以较大地数减去较小地数,接着把较小地数与所得地差比较,并以大数减小数 . 连续这个操作,直到所得地数相等为止,就这个数（等数）就是所求地最大公约数 . 例 2 用更相减损术求 98 与 63 地最大公约数 . 98 和 63 以大数减小数,并辗转相减,即：9863 35 解：由于 63 不是偶数,把 6335 28 3528 7 28721 21714 1477 7. 所以, 98 与 63 地最大公约数是练习：用更相减损术求两个正数84 与 72 地最大公约数 . （答案： 1

6、2）比较辗转相除法与更相减损术地区分：（ 1）都是求最大公约数地方法,运算上辗转相除法以除法为主,更相减损术以减法为 主,运算次数上辗转相除法运算次数相对较少,特殊当两个数字大小区分较大时运算次数地 区分较明显 .（2）从结果表达形式来看,辗转相除法表达结果是以相除余数为 术就以减数与差相等而得到 3. 秦九韶算法 秦九韶运算多项式地方法0 就得到,而更相减损令,就有,其中 . 这样,我们便可由 依次求出；明显,用秦九韶算法求 n 次多项式地值时只需要做 n 次乘法和 n 次加法运算- 2 - / 10 名师归纳总结 - - - - - - -第 2 页,共 10 页精选学习资料 - - -

7、- - - - - - 4.进位制个人收集整理仅供参考学习进位制是一种记数方式,用有限地数字在不同位置置表示不同地数值 . 可使用数字符号地个数称为基数,基数为 n,即可称 n 进位制,简称 n 进制 . 现在最常用地是十进制,通常使用 10 个阿拉伯数字 0-9 进行记数 .对于任何一个数,我们可以用不同地进位制来表示 . 比如：十进数 57,可以用二进制表示为 111001,也可以用八进制表示为 71、用十六进制表示为 39,它们所代表地数值都是一样地 .表示各种进位制数一般在数字右下脚加注来表示 5 进制数 .（1）.k 进制转换为十进制地方法：（2）. 十进制转化为 k 进制数 b 地

8、步骤为：, 如 1110012 表示二进制数 ,345 表示,第一步,将给定地十进制整数除以基数 k,余数便是等值地 k 进制地最低位；其次步,将上一步地商再除以基数 k,余数便是等值地 k 进制数地次低位；第三步,重复其次步,直到最终所得地商等于 0 为止,各次所得地余数,便是 k 进制各位地数,最终一次余数是最高位,即除 k 取余法 .要点诠释：1、在 k 进制中,具有 k 个数字符号 . 如二进制有 0,1 两个数字 . 2、在 k 进制中,由低位向高位是按“ 逢 k 进一” 地规章进行计数 . 3、非 k 进制数之间地转化一般应先转化成十进制,再将这个十进制数转化为另一种进制地数,有地

9、也可以相互转化 .【反馈测评】：1求 324、243、135 这三个数地最大公约数 . 求三个数地最大公约数可以先求出两个数地最大公约数,第三个数与前两个数地最大公约数地最大公约数即为所求 .2用更相减损术求 98 与 63 地最大公约数解：由于 63 不是偶数,把 98 和 63 以大数减小数,并辗转相减98 6335 63 3528 35 287 28 721 21721 1477 所以, 98 和 63 地最大公约数等于 7 3已知一个五次多项式为 f x 5 x 5 2 x 4 3 . 5 x 3 2 . 6 x 2 1 . 7 x 0 8. 用秦九韶算法求这个多项式当 x = 5 地

10、值 . 解：将多项式变形：f x 5 x 2 x 3 5. x 2 . 6 x 1 7. x 0 . 8 按由里到外地顺序,依此运算一次多项式当 x = 5 时地值：v 0 5,1v 5 5 2 27,v 2 27 5 3 . 5 138 5.,3v 138 5. 5 2 . 6 689 . 9v 4 689 . 9 5 1 . 7 3451 2.,v 5 3451 . 2 5 0 8. 17255 2. 所以,当 x = 5 时,多- 3 - / 10 名师归纳总结 - - - - - - -第 3 页,共 10 页精选学习资料 - - - - - - - - - 项式地值等于17255.2

11、 个人收集整理仅供参考学习4将二进制数 1100112 化成十进制数解：依据进位制地定义可知110011 215 214 203 202 211 210 213211612151所以, 110011（2）=51. 【板书设计】：1.3 算法案例一、 辗转相除法三、秦九韶算法五、反馈测评 ：小结例 1作业二、 更相减损术 四、进位制例 2- 4 - / 10 名师归纳总结 - - - - - - -第 4 页,共 10 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习1.3 算法案例课前预习学案一、预习目标1、懂得辗转相除法与更相减损术中包蕴地数学原理,并能依据这些

12、原理进行算法分析 . 2、懂得秦九韶算法地思想 . 二、预习内容什么是进位制？最常见地进位制是什么？除此之外仍有哪些常见地进位制？请举例说明三、提出疑问摸索：辗转相除法中地关键步骤是哪种规律结构？课内探究学案一、学习目标1. 会用辗转相除法与更相减损术求最大公约数地方法 . 2. 会利用秦九韶算法求多项式地值 . 3各进位制之间能敏捷转化 .二、学习重难点：重点：辗转相除法与更相减损术求最大公约数地方法和秦九韶算法求多项式地值 . 难点：把辗转相除法与更相减损术地方法转换成程序框图与程序语言 . 三、学习过程辗转相除法思路：可以利用除法将大数化小 ,找两数地最大公约数 .适于两数较大时 1 用

13、较大地数 m除以较小地数 n 得到一个商 S 和一个余数 R ；2 如 R 0, 就 n 为 m,n 地最大公约数；如 R 0, 就用除数 n 除以余数 R 得到一个 1S和一个余数 R ；3 如 R 0, 就 R 为 m,n 地最大公约数 ; 如 R 0, 就用除数 R 除以余数 R 得到一个商 S 和一个余数 R ； 依次运算直至 R 0,此时所得到地 R n 1 即为所求地最大公约数 .例题 1：求两个正数 1424 和 801 地最大公约数 .以上我们求最大公约数地方法就是辗转相除法,也叫欧几里德算法 . 由上述步骤可以看出,辗转相除法中地除法是一个反复执行地步骤,且执行次数由余- 5

14、 - / 10 名师归纳总结 - - - - - - -第 5 页,共 10 页精选学习资料 - - - - - - - - - 数 是否等于个人收集整理仅供参考学习0 来打算 , 所以可把它看成一循环体, 写出辗转相除法完整地程序框图和程序语言.教学更相减损术：我国早期也有求最大公约数问题地算法,就是更相减损术 . 在九章算 术中有更相减损术求最大公约数地步骤：可半者半之,不行半者,副置 分母.子之数,以少减多,更相减损,求其等也,以等数约之 . 翻译为： 1 任意给出两个正数；判定它们是否都是偶数 执 行其次步 . . 如是,用 2 约简；如不是,2 以较大地数减去较小地数,接着把较小地数

15、与所得地差比较,并以大数减小 数. 连续这个操作,直到所得地数相等为止,就这个数（等数）就是所求地最 大公约数 . 例题 2. 用更相减损术求 91 和 49 地最大公约数 . 秦九韶算法：（ 1）设计求多项式fx2x55x44x33x26x7当 x=5 时地值地算法,并写出程序 . （ 2）有没有更高效地算法？能否探求更好地算法,来解决任意多项式地求解问题？引导同学把多项式变形为：fx22x5x5x4x4x3x3x2x6x7x54367并提问：从内到外,假如把每一个括号都看成一个常数,那么变形后地式子中有哪些“ 一次式” ？ x 地系数依次是什么？用秦九韶算法求多项式地值,与多项式组成有直接

16、关系吗？用秦九韶算法运算上述多项 式 地 值 , 需 要 多 少 次 乘 法 运 算 和 多 少 次 加 法 运 算 ？ 秦 九 韶 算 法 适 用 于 一 般 地 多 项 式fxanxnan1xn1a1xa0地求值问题吗？- 6 - / 10 名师归纳总结 - - - - - - -第 6 页,共 10 页精选学习资料 - - - - - - - - - 个人收集整理仅供参考学习v 时要用到vk1地怎样用程序框图表示秦九韶算法？观看秦九韶算法地数学模型,运算值,如令 v0 a n,我们可以得到下面地递推公式：v 0 a n k ,1 ,2 n v k v k 1 x a n k 这是一个在秦

17、九韶算法中反复执行地步骤,可以用循环结构来实现 . 请画出程序框图 . 例题 3已知一个五次多项式为 f x 5 x 5 2 x 4 3 . 5 x 3 2 . 6 x 2 1 . 7 x 0 . 8 用秦九韶算法求这个多项式当 x = 5 地值 . 进位制：我们明白十进制吗？所谓地十进制,它是如何构成地？其它进位制地数又是如何地呢？进位制是人们为了计数和运算便利而商定地记数系统. 进位制是一种记数方式,用有限地数字在不同位置置表示不同地数值. 可使用数字符号地个数称为基数,基数为n,即可称n 进位制,简称 n 进制 .例题 4将二进制数 1100112 化成十进制数精讲点拨：1求两个正数 8

18、251 和 2146;228 和 1995;5280 和 12155 地最大公约数 . 2 求两个正数 8251 和 2146 地最大公约数 .3. 用秦九韶算法运算多项式在 x=-4 时地值时 , V 3地值为：- 7 - / 10 名师归纳总结 - - - - - - -第 7 页,共 10 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习反思总结：比较辗转相除法与更相减损术地区分 1 都是求地方法,运算上辗转相除法以法为主,更相减损术以法为主,运算次数上法计 算次数相对较少,特殊当两个数字时运算次数地区分较明显2 从结果表达形式来看,辗转相除法表达结果是以就

19、得到,而更相减损术就以而得到3 通过对秦九韶算法地学习,你对算法本身有哪些进一步熟悉？4 秦九韶算法在运算一个n 次多项式地值时,只要做_次乘法运算和 _次加法运算 . 课后练习与提高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 版权申明 本文部分内容,包括文字、图片、以及设计等在网上搜集整理 .

20、版权为个人全部 This article includes some parts, including text, - 8 - / 10 名师归纳总结 - - - - - - -第 8 页,共 10 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习pictures, and design. Copyright is personal ownership.用户可将本文地内容或服务用于个人学习、讨论或观赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律地规定,不得侵害本网站及相关权益人地合法权益. 除此以外,将本文任何内容或服务用于其他用途时,须征

21、得本人及相关权益人地书面 许可,并支付酬劳 .Users may use the contents or services of this article for personal study, research or appreciation, and other non-commercial or non-profit purposes, but at the same time, they shall abide by the provisions of copyright law and other relevant laws, and shall not infringe upon

22、the legitimate rights of this website and its relevant obligees. In addition, when any content or service of this article is used for other purposes, written permission and remuneration shall be obtained from the person concerned and the relevant obligee.转载或引用本文内容必需是以新闻性或资料性公共免费信息为使用目地地合理、善意引用,不得对本文

23、内容原意进行曲解、修改,并 自负版权等法律责任 .Reproduction or quotation of the content of this article must be reasonable and good-faith citation for the use of - 9 - / 10 名师归纳总结 - - - - - - -第 9 页,共 10 页精选学习资料 - - - - - - - - - 个人收集整理 仅供参考学习news or informative public free information. It shall not misinterpret or modify the original intention of the content of this article, and shall bear legal liability such as copyright.- 10 - / 10 名师归纳总结 - - - - - - -第 10 页,共 10 页