高中数学必修3知识点

一：算法初步

7：辗转相除法与更相减损术

（1）辗转相除法。也叫欧几里德算法，用辗转相除法求最大公约数的步骤如下： （2）更相减损术

我国早期也有求最大公约数问题的算法，就是更相减损术。在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母 子之数，以少减多，更相减损，求其等也，以等数约之。 翻译为：{ = 1 \* GB3 |①任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。 （3）辗转相除法与更相减损术的区别：

都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等

而得到

8：秦九韶算法与排序 （1）秦九韶算法概念：

f(x)=anx+an-1x+ .+a1x+a0求值问题

f(x)=anx+an-1x+ .+a1x+a0=( anx+an-1x+ .+a1)x+a0 =(( anx+an-1x+ .+a2)x+a1)x+a0

n

n-1

n-1

n-2

n-2

n-3

n

n-1

=......=(...( 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次多项式的求值问题转化成求n个一次多项式的值的问题。 （2）两种排序方法：直接插入排序和冒泡排序 直接插入排序

基本思想：插入排序的思想就是读一个，排一个。将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．（由于算法简单，可以举例说明） 冒泡排序

基本思想：依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数...... 由于在排序过程中总是大数往前,小数往后,