文档介绍：普通高中课程标准实验教科书—数学[人教版]
高三新数学第一轮复习教案(讲座17)—算法案例
:
通过阅读中国古代数学中的算法案例,体会中国古代数学对世界数学发展的贡献。
算法是高中数学新课程中的新增内容,本讲的重点是几种重要的算法案例思想,复习时重算法的思想轻算法和程序的构造。
预测2007年高考队本讲的考察是:以选择题或填空题的形式出现,分值在5分左右,考察的热点是算法实例和传统数学知识的结合题目。
(1)短除法
求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得的商是两个互质数为止,然后把所有的除数连乘起来。
(2)穷举法(也叫枚举法)
穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数。
(3)辗转相除法
辗转相除法求两个数的最大公约数,其算法可以描述如下:
①输入两个正整数m和n;
②求余数r:计算m除以n,将所得余数存放到变量r中;
③更新被除数和余数:m=n,n=r;
④判断余数r是否为0。若余数为0,则输出结果;否则转向第②步继续循环执行。
如此循环,直到得到结果为止。
(4)更相减损术
我国早期也有解决求最大公约数问题的算法,就是更相减损术。在《九章算术》中记载了更相减损术求最大公约数的步骤:可半者半之,不可半者,副置分母•子之数,以少减多,更相减损,求其等也,以等数约之。
步骤:
Ⅰ.任意给出两个正数;判断它们是否都是偶数。若是,用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
……..
vn=vn-1x+a0
观察秦九韶算法的数学模型,计算vk时要用到vk-1的值,若令v0=an。
我们可以得到下面的递推公式:
v0=an
vk=vk-1+an-k(k=1,2,…n)
这是一个在秦九韶算法中反复执行的步骤,可以用循环结构来实现。
排序的算法很多,课本主要介绍里两种排序方法:直接插入排序和冒泡排序
(1)直接插入排序
在日常生活中,经常碰到这样一类排序问题:把新的数据插入到已经排好顺序的数据列中。
例如:一组从小到大排好顺序的数据列{1,3,5,7,9,11,13},通常称之为有序列,我们用序号1,2,3,……表示数据的位置,欲把一个新的数据8插入到上述序列中。
完成这个工作要考虑两个问题:
(1)确定数据“8”在原有序列中应该占有的位置序号。数据“8”所处的位置应满足小于或等于原有序列右边所有的数据,大于其左边位置上所有的数据。
(2)将这个位置空出来,将数据“