tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 数学 >>

1.3 算法案例


1.3 算法案例
. 课时安排 3 课时 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大公约数? (3)怎样用辗转相除法求最大公约数? (4)怎样用更相减损术求最大公约数? 讨论结果: (1)短除法 求两个正整数的最大公约数的步骤: 先用两个数公有的质因数连续去除, 一直除到所得 的商是两个互质数为止,然后把所有的除数连乘起来. (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举, 直到找到公约数立即中断列举,得到的公约数便是最大公约数. (3)辗转相除法 辗转相除法求两个数的最大公约数,其算法步骤可以描述如下: 第一步,给定两个正整数 m,n. 第二步,求余数 r:计算 m 除以 n,将所得余数存放到变量 r 中. 第三步,更新被除数和余数:m=n,n=r. 第四步,判断余数 r 是否为 0.若余数为 0,则输出结果;否则转向第二步继续循环执行. 如此循环, 直到得到结果为止. 这种算法是由欧几里得在公元前 300 年左右首先提出的, 因而又叫欧几里得算法. (4)更相减损术 我国早期也有解决求最大公约数问题的算法,就是更相减损术. 《九章算术》是中国古 代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之, 不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”翻译为现代语 言如下: 第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用 2 约简;若不是,执 行第二步. 第二步, 以较大的数减去较小的数, 接着把所得的差与较小的数比较, 并以大数减小数, 继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是 所求的最大公约数. 应用示例 例 1 用辗转相除法求 8 251 与 6 105 的最大公约数,

例2

用更相减损术求 98 与 63 的最大公约数.

1

变式训练 用辗转相除法或者更相减损术求三个数 324,243,135 的最大公约数.

例 3 (1)用辗转相除法求 123 和 48 的最大公约数.

(2)用更相减损术求 80 和 36 的最大公约数.

点评:对比两种方法控制好算法的结束,辗转相除法是到达余数为 0,更相减损术是到达减 数和差相等. 变式训练 分别用辗转相除法和更相减损术求 1 734,816 的最大公约数.

知能训练 求 319,377,116 的最大公约数.

. 课堂小结 (1)用辗转相除法求最大公约数. (2)用更相减损术求最大公约数. 思想方法:递归思想. 作业 分别用辗转相除法和更相减损术求 261,319 的最大公约数.(29)

2

第 2 课时 案例 2 秦九韶算法
导入新课 .怎样求多项式 f(x)=x5+x4+x3+x2+x+1 当 x=5 时的值呢?方法也是多种多样的, 今天我们 开始学习秦九韶算法. 提出问题 (1)求多项式 f(x)=x5+x4+x3+x2+x+1 当 x=5 时的值有哪些方法?比较它们的特点. (2)什么是秦九韶算法? (3)怎样评价一个算法的好坏? 讨论结果: (1)怎样求多项式 f(x)=x5+x4+x3+x2+x+1 当 x=5 时的值呢? 一个自然的做法就是把 5 代入多项式 f(x),计算各项的值,然后把它们加起来,这时, 我们一共做了 1+2+3+4=10 次乘法运算,5 次加法运算. 另一种做法是先计算 x2 的值,然后依次计算 x2· x, (x2· x)· x, ( (x2· x)· x)· x 的值,这 样每次都可以利用上一次计算的结果,这时,我们一共做了 4 次乘法运算,5 次加法运算. 第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率,对于 计算机来说, 做一次乘法运算所用的时间比做一次加法运算要长得多, 所以采用第二种做法, 计算机能更快地得到结果. (2)上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约 1202~1261)在 他的著作《数书九章》中提出了下面的算法: 把一个 n 次多项式 f(x)=anxn+an-1xn-1+…+a1x+a0 改写成如下形式: f(x)=anxn+an-1xn-1+…+a1x+a0 =(anxn-1+an-1xn-2+…+a1)x+ a0 =( (anxn-2+an-1xn-3+…+a2)x+a1)x+a0 =… =(…( (anx+an-1)x+an-2)x+…+a1)x+a0. 求多项式的值时,首先计算最内层括号内一次多项式的值,即 v1=anx+an-1, 然后由内向外逐层计算一次多项式的值,即 v2=v1x+an-2, v3=v2x+an-3, … vn=vn-1x+a0, 这样,求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值. 上述方法称为秦九韶算法.直到今天,这种算法仍是多项式求值比较先进的算法. 应用示例 例 1 已知一个 5 次多项式为 f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8, 用秦九韶算法求这个多项式当 x=5 时的值.

(17 255.2.)

3

变式训练 请以 5 次多项式函数为例说明秦九韶算法。 解:设 f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0 首先,让我们以 5 次多项式一步步地进行改写: f(x)=(a5x4+a4x3+a3x2+a2x+a1)x+a0 =( (a5x3+a4x2+ a3x+a2)x+a1)x+a0 =( ( (a5x2+a4x+ a3)x+a2)x+a1)x+a0 =( ( ( (a5x+a4)x+ a3)x+a2)x+a1)x+a0 .
k 例 2 已知 n 次多项式 Pn(x)=a0xn+a1xn-1+…+an-1x+an,如果在一种算法中,计算 x0 (k=2,3,

4,…,n)的值需要 k-1 次乘法,计算 P3(x0)的值共需要 9 次运算(6 次乘法,3 次加法) , 那 么计 算 P10(x0) 的 值共需 要 __________ 次运 算 . 下 面给 出一 种减 少运 算次 数的 算法 : P0(x)=a0,Pk+1(x)=xPk(x)+ak+1(k=0,1,2,…,n-1) .利用该算法,计算 P3(x0)的值共需要 6 次运算,计算 P10(x0)的值共需要___________次运算. 答案:65 20 点评:秦九韶算法适用一般的多项式 f(x)=anxn+an-1xn-1+…+a1x+a0 的求值问题.直接法乘法运 算的次数最多可到达

( n ? 1) n ,加法最多 n 次.秦九韶算法通过转化把乘法运算的次数减少 2

到最多 n 次,加法最多 n 次 . 例 3 已知多项式函数 f(x)=2x5-5x4-4x3+3x2-6x+7,求当 x=5 时的函数的值. 解析:把多项式变形为:f(x)=2x5-5x4-4x3+3x2-6x+7 =((((2x-5)x-4)x+3)x-6)x+7. 计算的过程可以列表表示为:

最后的系数 2 677 即为所求的值. 算法过程: v0=2; v1=2× 5-5=5; v2=5× 5-4=21; v3=21× 5+3=108; v4=108× 5-6=534; v5=534× 5+7=2 677. 点评:如果多项式函数中有缺项的话,要以系数为 0 的项补齐后再计算. 知能训练 当 x=2 时,用秦九韶算法求多项式 f(x)=3x5+8x4-3x3+5x2+12x-6 的值. 解法一:根据秦九韶算法,把多项式改写成如下形式: f(x)=((((3x+8)x-3)x+5)x+12)x-6. 按照从内到外的顺序,依次计算一次多项式当 x=2 时的值. .
4

解法二:f(x)=((((3x+8)x-3)x+5)x+12)x-6



用秦九韶算法求多项式 f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x 当 x=3 时的值.

课堂小结 1.秦九韶算法的方法和步骤. 2.秦九韶算法的计算机程序框图. 作业 已知函数 f(x)=x3-2x2-5x+8,求 f(9)的值.

5

第 3 课时 案例 3 进位制
情境导入 在日常生活中,我们最熟悉、最常用的是十进制,据说这与古人曾以手指计数有关,爱 好天文学的古人也曾经采用七进制、十二进制、六十进制,至今我们仍然使用一周七天、一 年十二个月、一小时六十分的历法.今天我们来学习一下进位制. 提出问题 (1)你都了解哪些进位制? (2)举出常见的进位制. (3)思考非十进制数转换为十进制数的转化方法. (4)思考十进制数转换成非十进制数及非十进制之间的转换方法. 讨论结果: (1)进位制是人们为了计数和运算方便而约定的计数系统,约定满二进一,就是二进制; 满十进一,就是十进制;满十二进一,就是十二进制;满六十进一,就是六十进制等等.也 就是说:“满几进一”就是几进制,几进制的基数(都是大于 1 的整数)就是几. (2)在日常生活中,我们最熟悉、最常用的是十进制,据说这与古人曾以手指计数有关, 爱好天文学的古人也曾经采用七进制、十二进制、六十进制,至今我们仍然使用一周七天、 一年十二个月、一小时六十分的历法. (3)十进制使用 0~9 十个数字.计数时,几个数字排成一行,从右起,第一位是个位,个位 上的数字是几,就表示几个一;第二位是十位,十位上的数字是几,就表示几个十;接着依 次是百位、千位、万位…… 例如:十进制数 3 721 中的 3 表示 3 个千,7 表示 7 个百,2 表示 2 个十,1 表示 1 个一.于 是,我们得到下面的式子: 3 721=3× 103+7× 102+2× 101+1× 100. 与十进制类似,其他的进位制也可以按照位置原则计数.由于每一种进位制的基数不同,所 用的数字个数也不同.如二进制用 0 和 1 两个数字,七进制用 0~6 七个数字. 其他进位制的数也可以表示成不同位上数字与基数的幂的乘积之和的形式,如 110 011(2)=1× 25+1× 24+0× 23+0× 22+1× 21+1× 20, 7 342(8)=7× 83+3× 82+4× 81+2× 80. (4)关于进位制的转换,教科书上以十进制和二进制之间的转换为例讲解,并推广到十进 制和其他进制之间的转换.这样做的原因是,计算机是以二进制的形式进行存储和计算数据 的, 而一般我们传输给计算机的数据是十进制数据, 因此计算机必须先将十进制数转换为二 进制数,再处理,显然运算后首次得到的结果为二进制数,同时计算机又把运算结果由二进 制数转换成十进制数输出. 1°十进制数转换成非十进制数 把十进制数转换为二进制数,教科书上提供了“除 2 取余法”,我们可以类比得到十进制数转 换成 k 进制数的算法“除 k 取余法”. 2°非十进制之间的转换 一个自然的想法是利用十进制作为桥梁.教科书上提供了一个二进制数据与 16 进制数据之间 的互化的方法,也就是先由二进制数转化为十进制数,再由十进制数转化成为 16 进制数.

6

应用示例 思路 1 例1 把二进制数 110 011(2)化为十进制数.

点评: 先把二进制数写成不同位上数字与 2 的幂的乘积之和的形式, 再按照十进制的运算规 则计算出结果. 变式训练 例2 把 89 化为二进制数.

思路 2 例1 将 8 进制数 314 706(8)化为十进制数

例2

把十进制数 89 化为三进制数

知能训练 将十进制数 34 转化为二进制数.

拓展提升 把 1 234(5)分别转化为十进制数和八进制数

. 点评: 本题主要考查进位制以及不同进位制数的互化. 五进制数直接利用公式就可以转化为 十进制数;五进制数和八进制数之间需要借助于十进制数来转化. 课堂小结 (1)理解算法与进位制的关系. (2)熟练掌握各种进位制之间转化. 作业 习题 1.3A 组 3、4.

7


推荐相关:

高中数学必修3《1.3算法案例)》教案设计

高中数学必修3《1.3算法案例)》教案设计_数学_高中教育_教育专区。www.xkb1.com 新课标第一网系列资料 www.xkb1.com 新课标第一网不用注册,免费下载! 1.3...


1.3 算法案例知识点,试题及答案

1.3 算法案例知识点,试题及答案_数学_高中教育_教育专区。一、知识要点及方法辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的: 1. 若 r...


高中数学必修三1.3算法案例练习

高中数学必修三1.3算法案例练习_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 高中数学必修三1.3算法案例练习_数学_高中教育_教育专区。一、选择...


1.3_算法案例

1.3_算法案例_高一数学_数学_高中教育_教育专区。1.3 算法案例 教学分析 在学生学习了算法的初步知识, 理解了表示算法的算法步骤、 程序框图和程序三种不同 ...


1.3算法案例

1.3算法案例_数学_高中教育_教育专区。1.3 算法案例 [自我认知]: 1.用辗转相除法求 840 与 1785 的最大公约数: 班次 姓名 2.用更相减损术求 612 与 ...


1.3算法案例

1.3 算法案例 第 1、2 课时 辗转相除法与更相减损术(1)教学目标 (a)知识与技能 1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法...


1.3算法案例

1.3算法案例_高二数学_数学_高中教育_教育专区。1.3 算法案例 1. 8251 与 6105 的最大公约数是( A.4 B.37 ) C.148 ) D.1 813 2.如图所示的程序...


1.3算法案例

1.3算法案例_数学_高中教育_教育专区。高一数学必修 3 第一章算法初步导学案 编制人: 审核人: 班级: 小组: 姓名: 等级: §1.3算法案例》练习案 1、用...


1.3算法案例

1.3算法案例_数学_高中教育_教育专区。高二数学必修三1. 3 算法案例 (讲) 在初中,我们已经学过求最大公约数的知识,你能求出 18 与 30 的公约数吗? 我们...


1.3 算法案例

1.3 算法案例_数学_高中教育_教育专区。1.3 算法案例 . 课时安排 3 课时 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com