高三数学教案：算法案例

1、普通高中 程 准 教科 数学人教版 高三新 数学第一轮复习教案（讲座17）算法案例一课标要求：通 中国古代数学中的算法案例，体会中国古代数学 世界数学 展的 献。二命题走向算法是高中数学新 程中的新增内容，本 的重点是几种重要的算法案例思想，复 重算法的思想 算法和程序的构造。预测 2007 年高考 本 的考察是： 以 或填空 的形式出 ， 分 在 5 分左右，考察的 点是算法 例和 数学知 的 合 目。三要点精讲1求最大公 数（ 1）短除法求两个正整数的最大公 数的步 ：先用两个数公有的 因数 去除，一直除到所得的商是两个互 数 止，然后把所有的除数 乘起来。（ 2） 法（也叫枚 法） 法求

2、两个正整数的最大公 数的解 步 ：从两个数中 小数开始由大到小列 ，直到找到公 数立即中断列 ，得到的公 数便是最大公 数。（ 3） 相除法 相除法求两个数的最大公 数，其算法可以描述如下： 入两个正整数 m 和 n； 求余数 r： 算 m 除以 n，将所得余数存放到 量r 中；更新被除数和余数：m=n ，n=r；判断余数r 是否 0。若余数 0， 出 果；否 向第步 循 行。如此循 ，直到得到 果 止。（ 4）更相减 我国早期也有解决求最大公 数 的算法，就是更相减 。在九章算 中 了更相减 求最大公 数的步 ：可半者半之，不可半者，副置分母 ?子之数，以少减多，更相减 ，求其等也，以等数

3、之。步 ：任意 出两个正数；判断它 是否都是偶数。若是，用 2 ；若不是， 行第二步。以 大的数减去 小的数，接着把 小的数与所得的差比 ，并以大数减小数。 操作，直到所得的数相等 止， 个数（等数）就是所求的最大公 数。2秦九韶算法秦九韶算法的一般 ：秦九韶算法适用一般的多 式f(x)=a nnn-1 n-110的求 。用秦九韶算x +ax+ .+a x+a法求一般多 式f(x)= ann n-1xn-1100 的函数 ，可把n 次多 式的求x +a+ .+a x+a当 x=x 化成求n 个一次多 式的 的 ，即求第 1页共 10页v0=anv1=anx+an 1v2=v 1x+an 2v3

4、=v 2x+an 3 .vn=v n 1x+a0 察秦九韶算法的数学模型， 算vk 要用到 vk 1 的 ，若令v0=an。我 可以得到下面的 推公式：v0=anvk=v k 1+ank (k=1,2, n) 是一个在秦九韶算法中反复 行的步 ，可以用循 构来 。3. 排序排序的算法很多， 本主要介 里两种排序方法：直接插入排序和冒泡排序（ 1）直接插入排序在日常生活中， 常碰到 一 排序 ：把新的数据插入到已 排好 序的数据列中。例如：一 从小到大排好 序的数据列 1 ， 3，5， 7，9， 11， 13 ，通常称之 有序列，我 用序号 1，2，3，表示数据的位置， 欲把一个新的数据 8 插

5、入到上述序列中。完成 个工作要考 两个 ：（ 1）确定数据“ 8”在原有序列中 占有的位置序号。数据“8”所 的位置 足小于或等于原有序列右 所有的数据，大于其左 位置上所有的数据。（ 2）将 个位置空出来，将数据“8”插 去。 于一列无序的数据列，例如：49 ， 38， 65， 97， 76， 13， 27， 49 ，如何使用 种方法 行排序呢？基本思想很 ，即反复使用上述方法排序，由序列的 度不断增加，一直到完成整个无序列就有序了。首先， 49 是有序列，我 将38 插入到有序列 49 中，得到两个数据的有序列：38 ，49 ，然后，将第三个数据65 插入到上述序列中，得到有序列：38 ，

6、 49， 65按照 种方法，直到将最后一个数据65 插入到上述有序列中，得到13 ， 27， 38， 49， 49， 65， 76， 97 ，就完成了整个数据列的排序工作。注意到无序列“插入排序算法”成 了解决 的平台。（ 2）冒泡法排序所 冒泡法排序，形象地 ，就是将一 数据按照从小到大的 序排列 ，小的数据 量 的， 大的数据 量沉的。 一个小的数据就好比水中的气泡， 往上移 ，一个 大的数据就好比石 ，往下移 。 然最 会沉到水底，最 的会浮到 ，反复 行，直到数据列排成 有序列。以上 程反映了 种排序方法的基本思路。第 2页共 10页我们先对一组数据进行分析。设待排序的数据为：49 ，

7、 38， 65， 97， 76， 13， 27， 49排序的具体操作步骤如下：1将第 1 个数与右边相邻的数 38 进行比较， 因为 3849 ，所以顺序不变，得到新的数据列：38 ， 49， 65， 97， 76， 13， 27， 493将新数据列中的第3 个数 65 与右边相邻的数97 进行比较，因为9765 ，所以顺序不变，得到新的数据列：38 ， 49， 65， 97， 76， 13， 27， 494将新数据列中的第4 个数 97 与右边相邻的数76 进行比较，因为7697，97 应下沉，所以顺序不变，得到新的数据列：38 ， 49， 65， 76， 97， 13， 27， 495将新

8、数据列中的第5 个数 97 与右边相邻的数13 进行比较，因为1397，97 应下沉，所以顺序改变，得到新的数据列：38 ， 49， 65， 76， 13，97， 27， 496将新数据列中的第6 个数 97 与右边相邻的数27 进行比较，因为2797，97 应下沉，所以顺序改变，得到新的数据列：38 ， 49， 65， 76， 13，97， 27， 497将新数据列中的第7 个数 97 与右边相邻的数49 进行比较，因为4997，97 应下沉，所以顺序改变，得到新的数据列：38 ， 49，65， 76， 13， 97， 49， 27我们把上述过程称为一趟排序。其基本特征是最大的数据沉到底，即

9、排在最左边位置上的数据是数组中最大的数据。反复执行上面的步骤，就能完成排序工作，排序过程不会超过 7 趟。这种排序的方法称为冒泡排序。上面的分析具有一般性，如果数据列有 n 个数据组成，至多经过 n 1 趟排序，就能完成整个排序过程。4进位制（ 1）概念进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数， 基数为 n，即可称 n 进位制，简称 n 进制。现在最常用的是十进制，通常使用 10 个阿拉伯数字 09 进行记数。对于任何一个数，我们可以用不同的进位制来表示。比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示

10、为39，它们所代表的数值都是一样的。一般地，若k 是一个大于一的整数，那么以k 为基数的k 进制可以表示为：anan 1.a1a0( k )(0ank,0an 1 ,., a1 , a0k) ，而表示各种进位制数一般在数字右下脚加注来表示, 如 111001(2) 表示二进制数,34 (5)表示 5 进制数。第 3页共 10页（ 2）进位制间的转换关于进位制的转换，教科书上以十进制和二进制之间的转换为例讲解，并推广到十进制和其它进制之间的转换。这样做的原因是，计算机是以二进制的形式进行存储和计算数据的，而一般我们传输给计算机的数据是十进制数据，因此计算机必须先将十进制数转换为二进制数，再处理，

11、显然运算后首次得到的结果为二进制数，同时计算机又把运算结果由二进制数转换成十进制数输出。非十进制数转换为十进制数比较简单，只要计算下面的式子值即可：anan 1 .a1a0 ( k)an k nan 1k n 1.a1 k a0第一步：从左到右依次取出k 进制数.a1a0(k)各位上的数字，乘以相应的k 的anan 1幂 ， k 的 幂 从 n开 始 取 值 ， 每 次 递 减 1 ， 递 减 到 0 ， 即an k n , an 1 k n 1 ,. , a1 k, a0 k 0 ；第二步：把所得到的乘积加起来，所得的结果就是相应的十进制数。十进制数转换成非十进制数把十进制数转换为二进制数，

12、教科书上提供了“除2 取余法”，我们可以类比得到十进制数转换成 k 进制数的算法“除k 取余法”。非十进制之间的转换一个自然的想法是利用十进制作为桥梁。教科书上提供了一个二进制数据与16 进制数据之间的互化的方法，也就是先有二进制数转化为十进制数，再由十进制数转化成为16 进制数。四典例解析题型 1：求最大公约数例 1（ 1）用辗转相除法求123 和 48 的最大公约数？（ 2）用更相减损来求80 和 36 的最大公约数？解析：（ 1）辗转相除法求最大公约数的过程如下：（建立带余除式）123248 2748127 2127121 62136 3623+0最后 6 能被 3 整除，得123 和

13、48 的最大公约数为3。（ 2）分析：我们将 80 作为大数， 36 作为小数，执行更相减损术来求两数的最大公约数。执行结束的准则是减数和差相等。更相减损术：因为 80 和 36 都是偶数，要去公因数2。80 2=40， 362=18；40 和 18 都是偶数，要去公因数2。第 4页共 10页40 2=20， 182=9下面来求20 与 9 的最大公 数，20 9=1111 9=29 2=77 2=55 2=33 2=12 1=1可得 80 和 36 的最大公 数 22 1=4。点 ： 比两种方法控制好算法的 束， 相除法是到达余数 0，更相减 是到达减数和差相等。例 2 一个算法，求出 84

14、0 与 1764 的最大公因数。解析：我 已 学 了 自然数的素因数分解的方法，下面的算法就是在此基 上 的。解 思路如下：首先 两个数 行素因数分解：840=23 3 5 7， 1764=22 32 72，其次，确定两个数的公共素因数：2， 3， 7。接着确定公共素因数的指数： 于公共素因数2， 840 中 23， 1764 中 22， 取 少的一个 22，同理可得下面的因数 3 和 7。算法步 ：第一步：将840 行素数分解23 35 7；第二步：将1764 行素数分解22 32 72 ；第三步：确定它 的公共素因数：2， 3， 7；第四步：确定公共素因数 2， 3，7 的指数分 是： 2

15、， 1， 1；第五步：最大公因数 2231 71=84 。点 ： 数是除以外只能被和本身整除的正整数，它 是无限多个，但是目前没有一个 律来确定所有的 数。 型 2：秦九韶算法例 3（ 2005 北京， 14）已知 n 次多 式 pn (x)a0 xna1 xn 1 lan 1x an ，如果在一种算法中， 算 x0k （ 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

16、 0， 1，第 5页共 10页2， n 1）利用 算法， 算p3 (x0 ) 的 共需要6 次运算， 算p10 ( x0 ) 的 共需要次运算。答案： 65； 20。点 ：秦九韶算法适用一般的多 式f(x)=a nxn+an-1xn-1 + .+a1x+a0 的求 。直接法乘法运算的次数最多可到达(n1)n ，加法最多 n 次。秦九韶算法通 化把乘法运2算的次数减少到最多n 次，加法最多n 次。例 4已知多 式函数 f(x)=2x 5 5x 4 4x3 +3x2 6x+7 ，求当 x=5 的函数的 。解析：把多 式 形 ： f(x)= 2x 5 5x4 4x3+3x 2 6x+7=(2x 5)

17、x 4)x+3)x 6)x+7 算的 程可以列表表示 ：多 式 x 系数2 543 67运算运算所得的 10251055402670+ 形后 x 的 系数 25211085342677*5最后的系数 2677 即 所求的 。算法 程：v0=2v1=2 5 5=5v2=5 5 4=21v3=21 5+3=108v4=108 5 6=534v5=534 5+7=2677点 ：如果多 式函数中有缺 的 ，要以系数 0 的 后再 算。 型三：排序例 4 用两种排序方法将以下 8 个数： 7,1,3,12,8,4,9,10。按照从大到小的 序 行排序。解析：可以按照直接插入排序和冒泡排序 两种方法的要求

18、， 合 形， 分析写出。直接插入法排序：7131284910713128491073112849101273184910第 6页共 10页1287314910128743191012987431101210987431冒泡排序7777777711333333331121212121212121218888888814444444419999999911010101010101010第一趟771212121231288910128791098491088491077791044441033333111111第 2 趟第 3 趟第 4 趟第 5 趟第 6 趟点评：直接插入法和冒泡法排序是常见的排序

19、方法，通过该例， 我们对比可以发现，直接插入排序比冒泡排序更有效一些，执行的操作步骤更少一些。例 6给出以下四个数： 6， 3， 0，15，用直接插入法排序将它们按从小到大的顺序排列，用冒泡法将它们按从大到小的顺序排列。分析：不论从大到小的顺序还是按从大到小的顺序，都可按两种方法的步骤进行排序。解析：直接插入排序法：6 3015 36015 30615 30615用冒泡排序法排序：6666666151515 33000151566600 3151500000第 7页共 10页151515 3 3 33 3 3 3题型 4：进位值例 7把十进制数89 化为三进制数，并写出程序语句.解析：具体的计

20、算方法如下：89=3 29+229=3 9+29=3 3+03=3 1+01=3 0+1所以 :89 （ 10） =1011001(3) 。点评：根据三进制数满三进一的原则，可以用3 连续去除89 及其所的得的商，然后按倒序的先后顺序取出余数组成数据即可。例 8将 8 进制数 314706（8 ）化为十进制数，并编写出一个实现算法的程序。解析： 314706 （8）=3 85432+18 +4 8 +7 8 +0 81+6 80=104902。所以，化为十进制数是104902。点评：利用把 k 进制数转化为十进制数的一般方法就可以把8 进制数 314706（ 8）化为十进制数，然后根据该算法，

21、利用get 函数，应用循环结构可以设计程序。五思维总结1求最大公约数开始（ 1）辗转相除法程序框图与程序语句程序：输入： m,ninput “m ， n= ”;m,ndor=m mod nr=m mod nm=nn=rm=nloop until r=0printn=rendnr=0?y输出：开始第 8页共 10页（ 2）更相减损术更相减损术程序：input “请输入两个不相等的正整数”；a， bi=0while a mod 2=0 and b mod 2=0a=a/2b=b/2i=i+1wenddoif ba thent=aa=bb=tend ifc=a ba=bb=cloop until a=bprint aiend对于两个正整数如何选择合适的方法求他们的最大公约数方法适用范围及特点短除法适合两个较小的正整数或两个质因数较少的正整数，简便易操作。穷举法适合计算机操作，但一一验证过于繁琐。辗转相除法适用于两个较大的正整数，以除法为主，辗转相除法计算次数相对较少，特别当两个数字大小差别较大时计算次数较明显。更相减损术适用于两个较大的正整数，更相减损术以减法为主，计算次数上相对于辗转相处法较多。2我们以这个5 次多项式函数为例加以说明，设：f （ x） =a5x5+a4x4 +a3x3+a2x2