当前位置:首页 >> 其它课程 >> 必修3帝1章帝4节算法案例

必修3帝1章帝4节算法案例


2009~2010 学年度高三数学(人教版 A 版)第一轮复习资料

第 17 讲
一. 【课标要求】

算法案例

通过阅读中国古代数学中的算法案例,体会中国古代数学对世界数学发展的贡献。

二. 【命题走向】
算法是高中数学新课程中的新增内容,本讲的重点是几种重要的算法案例思想

,复习时 重算法的思想轻算法和程序的构造。 预测 2010 年高考队本讲的考察是:以选择题或填空题的形式出现,分值在 5 分左右,考 察的热点是算法实例和传统数学知识的结合题目

三. 【要点精讲】
1.求最大公约数 (1)短除法 求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得 的商是两个互质数为止,然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举, 直到找到公约数立即中断列举,得到的公约数便是最大公约数 (3)辗转相除法 辗转相除法求两个数的最大公约数,其算法可以描述如下: ① 输入两个正整数 m 和 n; ② 求余数 r:计算 m 除以 n,将所得余数存放到变量 r 中; ③更新被除数和余数:m=n,n=r; ④判断余数 r 是否为 0。若余数为 0,则输出结果;否则转向第②步继续循环执行 如此循环,直到得到结果为止。 (4)更相减损术 我国早期也有解决求最大公约数问题的算法,就是更相减损术。在《九章算术》中记载 了更相减损术求最大公约数的步骤:可半者半之,不可半者,副置分母?子之数,以少减多, 更相减损,求其等也,以等数约之 步骤: Ⅰ.任意给出两个正数;判断它们是否都是偶数。若是,用 2 约简;若不是,执行第二 步。 Ⅱ.以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继 续这操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。 2.秦九韶算法 秦九韶算法的一般规则: 秦九韶算法适用一般的多项式 f(x)=anxn+an-1xn-1+….+a1x+a0 的求值问题。用秦九韶算法求一 般多项式 f(x)= anxn+an-1xn-1+….+a1x+a0 当 x=x0 时的函数值, 可把 n 次多项式的求值问题转化成求 n 个一次多项式的值的问题,即求 v0=an v1=anx+an-1 v2=v1x+an-2 v3=v2x+an-3 ……..
-1-

vn=vn-1x+a0 观察秦九韶算法的数学模型,计算 vk 时要用到 vk-1 的值,若令 v0=an。 我们可以得到下面的递推公式: v0=an vk=vk-1+an-k(k=1,2,…n) 这是一个在秦九韶算法中反复执行的步骤,可以用循环结构来实现 3.排序 排序的算法很多,课本主要介绍里两种排序方法:直接插入排序和冒泡排序 (1)直接插入排序 在日常生活中,经常碰到这样一类排序问题:把新的数据插入到已经排好顺序的数据列 中。 例如:一组从小到大排好顺序的数据列{1,3,5,7,9,11,13},通常称之为有序列, 我们用序号 1,2,3,??表示数据的位置,欲把一个新的数据 8 插入到上述序列中。 完成这个工作要考虑两个问题: (1)确定数据“8”在原有序列中应该占有的位置序号。数据“8”所处的位置应满足小 于或等于原有序列右边所有的数据,大于其左边位置上所有的数据。 (2)将这个位置空出来,将数据“8”插进去。 对于一列无序的数据列,例如:{49,38,65,97,76,13,27,49},如何使用这种方法 进行排序呢?基本思想很简单,即反复使用上述方法排序,由序列的长度不断增加,一直到 完成整个无序列就有序了 首先,{49}是有序列,我们将 38 插入到有序列{49}中,得到两个数据的有序列: {38,49}, 然后,将第三个数据 65 插入到上述序列中,得到有序列: {38,49,65} ???? 按照这种方法,直到将最后一个数据 65 插入到上述有序列中,得到 {13,27,38,49,49,65,76,97} 这样,就完成了整个数据列的排序工作。注意到无序列“插入排序算法”成为了解决这 类问题的平台 (2)冒泡法排序 所谓冒泡法排序,形象地说,就是将一组数据按照从小到大的顺序排列时,小的数据视 为质量轻的,大的数据视为质量沉的。一个小的数据就好比水中的气泡,往上移动,一个较 大的数据就好比石头,往下移动。显然最终会沉到水底,最轻的会浮到顶,反复进行,直到 数据列排成为有序列。以上过程反映了这种排序方法的基本思路。 我们先对一组数据进行分析。 设待排序的数据为:{49,38,65,97,76,13,27,49} 排序的具体操作步骤如下: 1.将第 1 个数与右边相邻的数 38 进行比较,因为 38<49,49 应下沉,即向右移动,所 以交换他们的位置,得到新的数据列: {38,49,65,97,76,13,27,49} 2.将新数据列中的第 2 个数 49 与右边相邻的数 65 进行比较,因为 65>49,所以顺序不 变,得到新的数据列: {38,49,65,97,76,13,27,49} 3.将新数据列中的第 3 个数 65 与右边相邻的数 97 进行比较,因为 97>65,所以顺序不 变,得到新的数据列: {38,49,65,97,76,13,27,49}

-2-

4.将新数据列中的第 4 个数 97 与右边相邻的数 76 进行比较,因为 76<97,97 应下沉, 所以顺序不变,得到新的数据列: {38,49,65, 76,97,13,27,49} 5.将新数据列中的第 5 个数 97 与右边相邻的数 13 进行比较,因为 13<97,97 应下沉, 所以顺序改变,得到新的数据列: {38,49,65, 76, 13,97,27,49} 6.将新数据列中的第 6 个数 97 与右边相邻的数 27 进行比较,因为 27<97,97 应下沉, 所以顺序改变,得到新的数据列: {38,49,65, 76, 13,97,27,49} 7.将新数据列中的第 7 个数 97 与右边相邻的数 49 进行比较,因为 49<97,97 应下沉, 所以顺序改变,得到新的数据列: {38,49,65, 76, 13,97, 49,27} 我们把上述过程称为一趟排序。其基本特征是最大的数据沉到底,即排在最左边位置上 的数据是数组中最大的数据。反复执行上面的步骤,就能完成排序工作,排序过程不会超过 7 趟。这种排序的方法称为冒泡排序。 上面的分析具有一般性,如果数据列有 n 个数据组成,至多经过 n-1 趟排序,就能完成 整个排序过程 4.进位制 (1)概念 进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值。可使用数字符号 的个数称为基数,基数为 n,即可称 n 进位制,简称 n 进制。现在最常用的是十进制,通常使 用 10 个阿拉伯数字 0—9 进行记数。 对于任何一个数,我们可以用不同的进位制来表示。比如:十进数 57,可以用二进制表 示为 111001,也可以用八进制表示为 71、用十六进制表示为 39,它们所代表的数值都是一样 的。 一般地,若 k 是一个大于一的整数,那么以 k 为基数的 k 进制可以表示为:
a n a n ?1 ...a1 a 0 ( k ) (0 ? a n ? k , 0 ? a n ?1 , ..., a1 , a 0 ? k ) ,

而表示各种进位制数一般在数字右下脚加注来表示,如 111001(2)表示二进制数,34(5)表示 5 进制数。 (2)进位制间的转换 关于进位制的转换,教科书上以十进制和二进制之间的转换为例讲解,并推广到十进制 和其它进制之间的转换。这样做的原因是,计算机是以二进制的形式进行存储和计算数据的, 而一般我们传输给计算机的数据是十进制数据,因此计算机必须先将十进制数转换为二进制 数,再处理,显然运算后首次得到的结果为二进制数,同时计算机又把运算结果由二进制数 转换成十进制数输出。 非十进制数转换为十进制数比较简单,只要计算下面的式子值即可:
a n a n ?1 ..... a 1 a 0 ( k ) ? a n ? k
n

? a n ?1 ? k

n ?1

? ......... ? a 1 ? k ? a 0

第一步:从左到右依次取出 k 进制数 a n a n ? 1 ..... a1 a 0 ( k ) 各位上的数字,乘以相应的 k 的幂,k 的幂从 n 开始取值,每次递减 1,递减到 0,即 a n ? k n , a n ?1 ? k n ?1 ,......... , a 1 ? k , a 0 ? k 0 ; 第二步:把所得到的乘积加起来,所得的结果就是相应的十进制数。 十进制数转换成非十进制数 把十进制数转换为二进制数,教科书上提供了“除 2 取余法” ,我们可以类比得到十进制

-3-

数转换成 k 进制数的算法“除 k 取余法” 。 非十进制之间的转换 一个自然的想法是利用十进制作为桥梁。教科书上提供了一个二进制数据与 16 进制数据 之间的互化的方法, 也就是先有二进制数转化为十进制数, 再由十进制数转化成为 16 进制数。

四. 【典例解析】
题型 1:求最大公约数 例 1. (1)用辗转相除法求 123 和 48 的最大公约数? (2)用更相减损来求 80 和 36 的最大公约数? 解析:(1)辗转相除法求最大公约数的过程如下:(建立带余除式) 123=2×48+27 48=1×27+21 27=1×21+6 21=3×6+3 6=2×3+0 最后 6 能被 3 整除,得 123 和 48 的最大公约数为 3。 (2)分析:我们将 80 作为大数,36 作为小数,执行更相减损术来求两数的最大公约数。 执行结束的准则是减数和差相等 更相减损术: 因为 80 和 36 都是偶数,要去公因数 2。 80÷2=40,36÷2=18; 40 和 18 都是偶数,要去公因数 2。 40÷2=20,18÷2=9 下面来求 20 与 9 的最大公约数, 20-9=11 11-9=2 9-2=7 7-2=5 5-2=3 3-2=1 2-1=1 可得 80 和 36 的最大公约数为 22×1=4。 点评:对比两种方法控制好算法的结束,辗转相除法是到达余数为 0,更相减损术是到达 减数和差相等。 例 2.设计一个算法,求出 840 与 1764 的最大公因数。 解析:我们已经学习过了对自然数的素因数分解的方法,下面的算法就是在此基础上设 计的。 解题思路如下: 首先对两个数进行素因数分解: 840=23×3×5×7,1764=22×32×72, 其次,确定两个数的公共素因数:2,3,7。 接着确定公共素因数的指数:对于公共素因数 2,840 中为 23,1764 中为 22,应取较少的 一个 22,同理可得下面的因数为 3 和 7。 算法步骤: 第一步:将 840 进行素数分解 23×3×5×7;

-4-

第二步:将 1764 进行素数分解 22×32×72; 第三步:确定它们的公共素因数:2,3,7; 第四步:确定公共素因数 2,3,7 的指数分别是:2,1,1; 第五步:最大公因数为 22×31×71=84。 点评:质数是除1以外只能被1和本身整除的正整数,它应该是无限多个,但是目前没 有一个规律来确定所有的质数 题型 2:秦九韶算法 例 3. (2009 福州模拟)如果执行右面的程序框图,那么输出的 S ? ( )
开始
i ? 1, s ? 1

i ? i ?1

s ? 2( s ? 1)



i ? 5?


输出s

结束

A.22 B.46 C. 9 4 D.190 答案 C 2、 (2009 浙江卷理)某程序框图如图所示,该程序运行后输出的 k 的 值是 A. 4 B. 5 ( ) C. 6 D. 7

【解析】对于 k ? 0, s ? 1,? k ? 1 ,而对于 k ? 1, s ? 3,? k ? 2 ,则
k ? 2, s ? 3 ? 8,? k ? 3 ,后面是 k ? 3, s ? 3 ? 8 ? 2 ,? k ? 4 ,不
11

符合条件时输出的 k ? 4 . 答案 A

3、 (2009 天津卷理)阅读上(右)图的程序框图,则输出的 S= (
-5-

)

A 26

B 35

C 40

D 57

【解析】当 i ? 1 时, T ? 2 , S ? 2 ;当 i ? 2 时, T ? 5 , S ? 7 ;当 i ? 3 时, T ? 8 , S ? 15 ;当 i ? 4 时, T ? 11 , S ? 26 ;当 i ? 5 时,
T ? 14 , S ? 40 ;当 i ? 6 时, T ? 17 , S ? 57 ,故选择 C。

答案



4(2009 安徽卷文)程序框图上(右)(即算法流程图)如图所示,其输入结果是_______。

【解析】根据流程图可得 a 的取值依次为 1、3、7、15、31、63?? 答案 127 点评:秦九韶算法适用一般的多项式 f(x)=anxn+an-1xn-1+….+a1x+a0 的求值问题。直接法乘法 运算的次数最多可到达
( n ? 1) n 2

,加法最多 n 次。秦九韶算法通过转化把乘法运算的次数减

少到最多 n 次,加法最多 n 次。 例 4.已知多项式函数 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 计算的过程可以列表表示为: 多项式 x 系数 运算所得的值 变形后 x 的"系数" 2 2 -5 10 -4 25 3 105 -6 540 7 2670 运算 + *5

5

21

108

534

2677

最后的系数 2677 即为所求的值 算法过程:

-6-

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=2677 点评:如果多项式函数中有缺项的话,要以系数为 0 的项补齐后再计算。 题型三:排序 例 4.试用两种排序方法将以下 8 个数: 7,1,3,12,8,4,9,10。按照从大到小的顺序进行排序。 解析:可以按照直接插入排序和冒泡排序这两种方法的要求,结合图形,分析写出。 直接插入法排序: [7] 1 3 12 8 4 9 10 [7 1] 3 12 8 4 9 10 [7 3 1] 12 8 4 9 10 [12 7 3 1] 8 4 9 10 [12 8 7 3 1] 4 9 10 [12 8 7 4 3 1] 9 10 [12 9 8 7 4 3 1] 10 [12 10 9 8 7 4 3 1] 冒泡排序 7 1 3 12 8 4 9 10 第一趟 7 3 12 8 4 9 10 1 7 12 8 4 9 10 3 1 12 8 7 9 10 4 3 1 12 8 9 10 7 4 3 1 12 9 10 8 7 4 3 1 12 10 9 8 7 4 3 1 7 1 3 12 8 4 9 10 7 3 1 12 8 4 9 10 7 3 12 1 8 4 9 10 7 3 12 8 1 4 9 10 7 3 12 8 4 1 9 10 7 3 12 8 4 9 1 10 7 3 12 8 4 9 10

第2趟 第3趟 第4趟 第5趟 第6趟 点评:直接插入法和冒泡法排序是常见的排序方法,通过该例,我们对比可以发现,直 接插入排序比冒泡排序更有效一些,执行的操作步骤更少一些 例 6.给出以下四个数:6,-3,0,15,用直接插入法排序将它们按从小到大的顺序排 列,用冒泡法将它们按从大到小的顺序排列 分析:不论从大到小的顺序还是按从大到小的顺序,都可按两种方法的步骤进行排序。

-7-

解析: 直接插入排序法: [6] -3 0 [-3 6] 0 [-3 0 6] [-3 0 6 用冒泡排序法排序: 6 -3 0 15 6 -3 0 15 6 0 -3 15

15 15 15 15] 6 0 15 -3 6 0 15 -3 6 15 0 -3 6 15 0 -3 15 6 0 -3 15 6 0 -3 15 6 0 -3

题型 4:进位值 例 7.把十进制数 89 化为三进制数,并写出程序语句. 解析:具体的计算方法如下: 89=3×29+2 29=3×9+2 9=3×3+0 3=3×1+0 1=3×0+1 所以:89(10)=1011001(3)。 点评:根据三进制数满三进一的原则,可以用 3 连续去除 89 及其所的得的商,然后按倒 序的先后顺序取出余数组成数据即可。 例 8.将 8 进制数 314706(8)化为十进制数,并编写出一个实现算法的程序。 解析:314706(8)=3×8 +1×8 +4×8 +7×8 +0×8 +6×8 =104902。 所以,化为十进制数是 104902。 点评: 利用把 k 进制数转化为十进制数的一般方法就可以把 8 进制数 314706(8)化为十进 制数,然后根据该算法,利用 GET 函数,应用循环结构可以设计程序。
5

4

3

2

1

0

五. 【思维总结】
1.求最大公约数 (1)辗转相除法 程序框图与程序语句 程序: INPUT “m,n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT END N 开始 输入:m,n

r=m MOD n m=n

n=r

r=0? Y 输出:
-8-

开始

(2)更相减损术 更相减损术程序: INPUT “请输入两个不相等的正整数” ;a,b i=0 WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DO IF b<a THEN t=a a=b b=t END IF c=a-b a=b b=c LOOP UNTIL a=b PRINT a^i END 对于两个正整数如何选择合适的方法求他们的最大公约数 方法 短除法 穷举法 辗转相除法 更相减损术 适用范围及特点 适合两个较小的正整数或两个质因数较少的正整数,简便易操作。 适合计算机操作,但一一验证过于繁琐。 适用于两个较大的正整数,以除法为主,辗转相除法计算次数相对较少,特别 当两个数字大小差别较大时计算次数较明显。 适用于两个较大的正整数,更相减损术以减法为主,计算次数上相对于辗转相 处法较多。

2.我们以这个 5 次多项式函数为例加以说明,设: f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0 首先,让我们以 5 次多项式一步步地进行改写: f(x)=(a5x4+a4x3+a3x2+a2x+a1)x+a0 =( 5x3+a4x2+ a3x+a2)x+a1)x+a0 (a =((a5x2+a4x+ a3)x+a2)x+a1)x+a0 ( =(( 5x+a4)x+ a3)x+a2)x+a1)x+a0 ((a 上面的分层计算。只用了小括号,计算时,首先计算最内层的括号,然后由里向外逐层计算, 直到最外层的括号,然后加上常数项即可。

-9-

开始

输入 a1,a2,a3,a4,a5,x0

n=1,v=v5

n≤6?

v=v×x0+a5-n

n=n+1

输出 v 结束 3.排序 (1)直接插入排序 插入排序的思想就是读一个,排一个。将数组的第1个数据放入数组的第1个位置,以 后读入的数据与已存入数组的数据进行比较,确定它按从大到小(从小到大)的排列中排在 正确的位置。将该位置以及以后的元素向后推移一个位置,将读入的新数填到空出的位置即 可。 (2)冒泡排序 以从大到小为例:依次比较相邻的两个数,把大的放前面,小的放后面。即首先比较第 1 个数和第 2 个数,大数放前,小数放后;然后比较完成第 2 个数和第 3 个数;......;直到比 较完了最后两个数。第一趟排序结束,最小的一定沉到最后。重复上过程,仍从第 1 个数开始, 到最后第 2 个数...... 由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒 泡排序。 4.进位值 我们常见的数字都是十进制数,比如一般的数值计算,但是并不是生活中的每一种数字都 是十进制的。比如时间和角度的单位是六十进制,电子计算机的指令用的是二进制,早先的计 算机的用的是十六进制的。

- 10 -


更多相关文档:

必修3帝1章帝4节算法案例

必修3帝1章帝4节算法案例 高一,数学,试题高一,数学,试题隐藏>> 2009~2010 学年度高三数学(人教版 A 版)第一轮复习资料 第 17 讲一. 【课标要求】 算法案例...

必修3第1章算法初步1.3算法案例(一)

必修31章算法初步1.3算法案例(一)_数学_高中教育_教育专区。高中数学必修3...1.3 算法案例(一) 题号 1 2 3 4 5 6 C C B C B D 选项 1. 2....

数学必修3第一章算法案例练习题

数学必修3一章算法案例练习题_数学_高中教育_教育专区。算法案例及随机抽样练习题 1. 用秦九韶算法计算多项式 f ( x) ? 3x6 ? 4x5 ? 5x 4 ? 6x3 ?...

必修3第1章算法初步1.3算法案例(二)

必修31章算法初步1.3算法案例(二)_数学_高中教育_教育专区。高中数学必修3...算法案例(二) 题号 1 2 A 3 C 4 D 5 B 6 A D 选项 7.0、1、2...

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

高中数学必修三1.3算法案例练习_数学_高中教育_教育专区。、选择题 1.用辗转...210 (6) 9.若十进制数 26 等于k 进制数 32,则k 等于( ) A.4 B.5 ...

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

高中数学必修三1.3算法案例_高一数学_数学_高中教育_教育专区。1.3《算法案例...4、写出从键盘任意输入两个正整数 a,b,输出这两个数的最小公倍数的算法,画...

数学必修三1.3.1算法案例

教师姓名 课题 胡柱石、汤玉龙 年级 高一 科目 数学,必修 3 §1.3.2 算法案例---进位制 1、了解各种进位制与十进制之间转换的规律,会利用各种进位制与十...

数学:1.3《算法案例》测试(新人教A版必修3)(新人教必修3).

数学:1.3《算法案例》测试(新人教A版必修3)(新人教必修3)._数学_高中教育_教育专区。学而思网校必修 3 www.xueersi.com 1.3 算法案例 1. (1)将 101111011...

必修3第一章第3节算法案例与算法小结(文)同步练习

必修3初步算法与算法案例 ... 8页 5财富值 必修3帝1章帝4节算法案例 10页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...

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

高中数学必修31.3算法案例)》教案设计_数学_高中教育_教育专区。www.xkb1.com 新课标第网系列资料 www.xkb1.com 新课标第网不用注册,免费下载! 1.3...
更多相关标签:
高中数学必修三算法 | 必修三算法 | 必修3算法 | 必修三算法初步 | 数学必修三算法初步 | 数学必修三算法 | 必修三算法ppt | 必修三算法的概念课件 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com