nbhkdz.com冰点文库

人教版高中数学必修三《1.3算法案例(教、学案)

时间:2013-05-30


临清三中数学组 编写人:赵万龙 审稿人: 郭振宇 李怀奎

1.3 算法案例

【教学目标】 : 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。 2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 【教学重难点】 : 重点:理解辗转相除法与更相减损术求最大公约数的方法。 难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言。 【教学过程】 : 情境导入: 1.教师首先提出问题:在初中,我们已经学过求最大公约数的知识,你能求出 18 与 30 的公约数吗? 2.接着教师进一步提出问题, 我们都是利用找公约数的方法来求最大公约数, 如果公约数 比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数? 比如求 8251 与 6105 的最大公约数?这就是我们这一堂课所要探讨的内容。 新知探究: 1.辗转相除法 例 1 求两个正数 8251 和 6105 的最大公约数。 (分析:8251 与 6105 两数都比较大,而且没有明显的公约数,如能把它们都变小一点, 根据已有的知识即可求出最大公约数) 解:8251=6105×1+2146 显然 8251 的最大公约数也必是 2146 的约数,同样 6105 与 2146 的公约数也必是 8251 的 约数,所以 8251 与 6105 的最大公约数也是 6105 与 2146 的最大公约数。 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 则 37 为 8251 与 6105 的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。 也叫欧几里德算法, 它是由欧几里德在公 元前 300 年左右首先提出的。利用辗转相除法求最大公约数的步骤如下: 第一步:用较大的数 m 除以较小的数 n 得到一个商 q0 和一个余数 r0; 第二步:若 r0=0,则 n 为 m,n 的最大公约数;若 r0≠0,则用除数 n 除以余数 r0 得到一 个商 q1 和一个余数 r1; 第三步:若 r1=0,则 r1 为 m,n 的最大公约数;若 r1≠0,则用除数 r0 除以余数 r1 得到一 个商 q2 和一个余数 r2; ?? 依次计算直至 rn=0,此时所得到的 rn-1 即为所求的最大公约数。 练习:利用辗转相除法求两数 4081 与 20723 的最大公约数(答案:53) 2.更相减损术

我国早期也有解决求最大公约数问题的算法,就是更相减损术。 更相减损术求最大公约数的步骤如下:可半者半之,不可半者,副置分母·子之数,以少 减多,更相减损,求其等也,以等数约之。 翻译出来为: 第一步:任意给出两个正数;判断它们是否都是偶数。若是,用 2 约简;若不是,执行第 二步。 第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。 继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。 例 2 用更相减损术求 98 与 63 的最大公约数. 解:由于 63 不是偶数,把 98 和 63 以大数减小数,并辗转相减,即:98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以,98 与 63 的最大公约数是 7。 练习:用更相减损术求两个正数 84 与 72 的最大公约数。 (答案:12) 比较辗转相除法与更相减损术的区别: (1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主, 计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别 较明显。 (2)从结果体现形式来看,辗转相除法体现结果是以相除余数为 0 则得到,而更相减损 术则以减数与差相等而得到 3. 秦九韶算法 秦九韶计算多项式的方法

令 其中 .这样,我们便可由 依次求出

,则有 ;



显然,用秦九韶算法求 n 次多项式的值时只需要做 n 次乘法和 n 次加法运算

4.进位制 进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.可使用数字符号的 个数称为基数,基数为 n,即可称 n 进位制,简称 n 进制.现在最常用的是十进制,通常使用 10 个阿拉伯数字 0-9 进行记数. 对于任何一个数,我们可以用不同的进位制来表示.比如:十进数 57,可以用二进制表示 为 111001, 也可以用八进制表示为 71、 用十六进制表示为 39, 它们所代表的数值都是一样的. 表示各种进位制数一般在数字右下脚加注来表示,如 111001(2)表示二进制数,34(5)表示 5 进 制数. (1).k 进制转换为十进制的方法: , (2).十进制转化为 k 进制数 b 的步骤为: 第一步,将给定的十进制整数除以基数 k,余数便是等值的 k 进制的最低位; 第二步,将上一步的商再除以基数 k,余数便是等值的 k 进制数的次低位; 第三步,重复第二步,直到最后所得的商等于 0 为止,各次所得的余数,便是 k 进制各 位的数,最后一次余数是最高位,即除 k 取余法. 要点诠释: 1、在 k 进制中,具有 k 个数字符号.如二进制有 0,1 两个数字. 2、在 k 进制中,由低位向高位是按“逢 k 进一”的规则进行计数. 3、非 k 进制数之间的转化一般应先转化成十进制,再将这个十进制数转化为另一种进制 的数,有的也可以相互转化. 【反馈测评】 : 1.求 324、243、135 这三个数的最大公约数。 求三个数的最大公约数可以先求出两个数的最大公约数, 第三个数与前两个数的最大公约 数的最大公约数即为所求。 2.用更相减损术求 98 与 63 的最大公约数 解:由于 63 不是偶数,把 98 和 63 以大数减小数,并辗转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=21 14-7=7 所以,98 和 63 的最大公约数等于 7 3. 已知一个五次多项式为 f ( x) ? 5x ? 2 x ? 3.5x ? 2.6 x ? 1.7 x ? 0.8 用秦九韶算法求
5 4 3 2

这个多项式当 x = 5 的值。 解: 将多项式变形: f ( x) ? ((((5x ? 2) x ? 3.5) x ? 2.6) x ? 1.7) x ? 0.8 按由里到外的顺序, 依此计算一次多项式当 x = 5 时的值:

v0 ? 5 , v1 ? 5 ? 5 ? 2 ? 27 , v2 ? 27? 5 ? 3.5 ? 138.5 , v3 ? 138.5 ? 5 ? 2.6 ? 689.9
v4 ? 689.9 ? 5 ? 1.7 ? 34512 , v5 ? 34512 ? 5 ? 0.8 ? 172552 所以,当 x = 5 时,多 . . .

项式的值等于 17255.2 4.将二进制数 110011(2)化成十进制数 解:根据进位制的定义可知

1100112) ? 1? 25 ?1? 24 ? 0 ? 23 ? 0 ? 22 ?1? 21 ?1? 20 (
? 1? 32 ? 1?16 ? 1? 2 ? 1 ? 51
所以,110011(2)=51。 【板书设计】 : 1.3 算法案例 一、辗转相除法 例1 作业
二、更相减损术

三、秦九韶算法

五、反馈测评:

小结

四、进位制

例2

临清三中数学组 编写人:赵万龙

审稿人: 郭振宇 李怀奎

1.3 算法案例
课前预习学案 一、预习目标 1、理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。 2、理解秦九韶算法的思想。 二、预习内容 什么是进位制?最常见的进位制是什么?除此之外还有哪些常见的进位制?请举例说 明. 三、提出疑惑 思考:辗转相除法中的关键步骤是哪种逻辑结构? 课内探究学案 一、学习目标 1. 会用辗转相除法与更相减损术求最大公约数的方法。 2. 会利用秦九韶算法求多项式的值。 3.各进位制之间能灵活转化。 二、学习重难点: 重点:辗转相除法与更相减损术求最大公约数的方法和秦九韶算法求多项式的值。 难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言。 三、学习过程 辗转相除法思路:可以利用除法将大数化小,找两数的最大公约数.(适于两数较大时) (1)用较大的数 m 除以较小的数 n 得到一个商 S0 和一个余数 R0 ; (2)若 R0 =0,则 n 为 m,n 的最大公约数;若 R0 ≠0,则用除数 n 除以余数 R0 得到一个 S1 和一个余数 R1 ;(3)若 R1 =0,则 R1 为 m,n 的最大公约数;若 R1 ≠0,则用除数 R0 除以余数 R1 得 到一个商 S2 和一个余数 R2 ;??依次计算直至 Rn =0,此时所得到的 Rn?1 即为所求的最大公 约数. 例题 1:求两个正数 1424 和 801 的最大公约数.

①以上我们求最大公约数的方法就是辗转相除法,也叫欧几里德算法. ②由上述步骤可以看出,辗转相除法中的除法是一个反复执行的步骤,且执行次数由余数 是否等于 0 来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.

教学更相减损术:我国早期也有求最大公约数问题的算法,就是更相减损术. 在《九章 算 术》中有更相减损术求最大公约数的步骤:可半者半之,不可半者,副置 分母?子之数,

以少减多,更相减损,求其等也,以等数约之. 翻译为:(1) 任意给出两个正数;判断它们是否都是偶数. 若是,用 2 约简;若不是, 执 行第二步. (2) 以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小 数. 继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最 大公约数. 例题 2. 用更相减损术求 91 和 49 的最大公约数.

秦九韶算法: (1)设计求多项式 f ( x) ? 2 x 5 ? 5x 4 ? 4x 3 ? 3x 2 ? 6x ? 7 当 x=5 时的值的算法,并写出 程序。

(2)有没有更高效的算法?能否探求更好的算法,来解决任意多项式的求解问题? 引导学生把多项式变形为:

f ( x) ? 2 x 5 ? 5 x 4 ? 4 x 3 ? 3 x 2 ? 6 x ? 7 ? ((((2 x ? 5) x ? 4) x ? 3) x ? 6) x ? 7
并提问:从内到外,如果把每一个括号都看成一个常数,那么变形后的式子中有哪些“一 次式”?x 的系数依次是什么? 用秦九韶算法求多项式的值, 与多项式组成有直接关系吗?用秦九韶算法计算上述多项式 的值,需要多少次乘法运算和多少次加法运算?秦九韶算法适用于一般的多项式

f ( x) ? an x n ? an?1 x n?1 ? ? ? ? ? a1 x ? a0 的求值问题吗?

怎样用程序框图表示秦九韶算法?观察秦九韶算法的数学模型,计算 若令

vk 时要用到 v k ?1 的值,

v0 ? an ,我们可以得到下面的递推公式:

v0 ? a n ? (k ? 1,2,? ? ?n) ? ?vk ? vk ?1 x ? an?k
构来实现。请画出程序框图。

这是一个在秦九韶算法中反复执行的步骤,可以用循环结

例题 3.已知一个五次多项式为 f ( x) ? 5x5 ? 2 x 4 ? 3.5x3 ? 2.6 x 2 ? 1.7 x ? 0.8 用秦九韶 算法求这个多项式当 x = 5 的值。

进位制: 我们了解十进制吗?所谓的十进制,它是如何构成的?其它进位制的数又是如何的呢? 进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式,用有限的数 字在不同的位置表示不同的数值。可使用数字符号的个数称为基数,基数为 n,即可称 n 进位 制,简称 n 进制。 例题 4.将二进制数 110011(2)化成十进制数

精讲点拨: 1.求两个正数 8251 和 2146;228 和 1995;5280 和 12155 的最大公约数.

2. 求两个正数 8251 和 2146 的最大公约数.

3.用秦九韶算法计算多项式 在 x=-4 时的值时,V3 的值为 :

反思总结: 比较辗转相除法与更相减损术的区别 (1)都是求 的方法, 计算上辗转相除法以 法为主, 更相减损术以 法为主, 计算次数上 法计算次数相对较少,特别当两个数字 时计算次数的 区别较明显. (2)从结果体现形式来看,辗转相除法体现结果是以 则得到,而更相减损术 则以 而得到. (3)通过对秦九韶算法的学习,你对算法本身有哪些进一步认识?

(4)秦九韶算法在计算一个 n 次多项式的值时,只要做____次乘法运算和____次加法运算。

课后练习与提高 1、用“辗转相除法”求得 459 和 357 的最大公约数是: A.3 B.9 C.17 D.51
2、将数 转化为十进制数为:

A. 524 B. 774 C. 256 3、用秦九韶算法计算多 当

D. 260 项式

时的值时,需要做乘法和加法的次数分别是: A. 6 , 6 C. 5 , 5 B. 5 , 6 D. 6 ,5


赞助商链接

高中数学 1.3中国古代数学中的算法案例学案 新人教A版...

高中数学 1.3中国古代数学中的算法案例学案人教A版必修3_高三数学_数学_高中教育_教育专区。§1.3 中国古代数学中的算法案例 【学习目标】1、通过辗转相除法...

人教B版必修3高中数学1.3《算法案例 秦九韶算法》word...

四川省古蔺县中学高中数学必修三:1.3《算法案例---秦九韶算法》 学案 学习目标: (1)在学习中国古代数学中的算法案例的同时,进一步体会算法的特点。 (2)体会...

人教A版高中数学必修三《循环语句》学案

人教A版高中数学必修三《循环语句》学案 - 中学人教版数学必修三 循环语句教案 学习目标: 1.掌握两种循环语句的一般形式,进一步体会算法的基本思想. 2.能够熟练地...

第一章算法初步1.3算法案例学案(含解析)新人教A版必修3

第一章算法初步1.3算法案例学案(含解析)新人教A版必修3 - 1.3 算法案例 辗转相除法与更相减损术 [提出问题] 问题 1:如何求 18 与 54 的最大公约数? ...

...1.4.1算法案例一(韩信点兵)学案 苏教版必修3

2015年高中数学 1.4.1算法案例一(韩信点兵)学案教版必修3_数学_高中教育_...人教版高中数学必修三《... 8页 5下载券 高中数学 1.3中国古代数... 2页...

高中数学 1.4.3算法案例三(二分法)学案 苏教版必修3

高中数学 1.4.3算法案例三(二分法)学案教版必修3_高三数学_数学_高中教育_教育专区。第 13 课时 5.4 算法案例 重点难点 重点:理解区间二分法的意义;学会分析...

人教A版高中数学必修三 1.2.3《循环语句》学案

人教A版高中数学必修三 1.2.3《循环语句》学案_教学案例/设计_教学研究_教育...4.将循环体改变,如改变为“S=S+1/i”,则该程序描述的算法实现什 么功能?...

1.3算法案例学案(完美版)_图文

河北衡水重点中学高一数学学案 1.3 算法案例 辗转相除法与更相减损术 教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能 根据这些...

高中数学第一章算法初步13算法案例教学案新人教A版必修...

高中数学第一章算法初步13算法案例教学案人教A版必修3(数学教案) - 1.3 算法案例 预习课本 P34~45, 思考并完成以下问题 (1)如何求 a,b,c 的最大公约...

高中数学 第12课时5.4算法案例学案 新人教A版必修3

高中数学 第12课时5.4算法案例学案人教A版必修3 - 第 12 课时 5.4 算法案例 重点难点 重点:通过案例分析理解辗转相除法与更相减损术求最大公约数的方法,...