秦九韶算法与排序 人教必修

【教学目标】：

了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。

掌握数据排序的原理能使用直接排序法与冒泡排序法给一组数据排序，进而能设计冒泡排序法的程序框图及程序，理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用。

【教学重点】秦九韶算法的特点及其程序设计，两种排序法的排序步骤及其程序设计（重点放在循环语句的应用上）

【教学难点】秦九韶算法的先进性理解及其程序设计,排序法的计算机程序设计

【学法与教学用具】：

学法：探究秦九韶算法对比一般计算方法中计算次数的改变，体会科学的计算；模仿排序法中数字排序的步骤，理解计算机计算的一般步骤，领会数学计算在计算机上实施的要求。

教学用具:计算机，TI-voyage200图形计算器

【教学过程】

秦九韶计算多项式的方法

例1、设计求多项式f(x)=2x5-5x4-4x3＋3x2-6x＋7当x=5时的值的算法，并写出程序。

个别学生提出一般的解决方案，如：

x=5

y=2 * x^5 – 5 * x^4 – 4 * x^3 ＋ 3 * x^2 – 6 * x ＋ 7

pRINT“y=”；y

END

提问：例1计算时需要多少次乘法计算？多少次加法计算？有什么优缺点？

学生答：上述算法一共做了解15次乘法运算，5次加法运算，优点是简单、易懂。缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高。

提问：计算x的幂时，可以利用前面的计算结果，以减少计算量，即先计算x2，然后依次计算x2.x，（x2.x）.x， (（x2.x）.x).x的值,这样计算上述多项式的值,一共需要多少次乘法，多少次加法?

学生答：上述算法一共做了解4次乘法运算，5次加法运算。

结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法更快地得到结果。

我们把多项式变形为：f(x)= 2x5-5x4-4x3＋3x2-6x＋7=((((2x-5)x-4)x＋3)x-6)x＋7

从内到外，如果把每一个括号都看成一个常数，x的系数依次是什么？

用图表可以表示为：

最后的系数2677即为所求的值,让学生描述上述计算过程。

上述算法就是“秦九韶算法”。

如何应用秦九韶算法完成一般的多项式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次多项式的求值问题转化成求n个一次多项式的值的问题

观察秦九韶算法的数学模型，计算vk时要用到vk-1的值，若令v0=an，我们可以得到下面的递推公式：

v0=an

vk=vk-1＋an-k(k=1,2,…n)

这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。

例2、已知一个五次多项式f(x)=5x5＋2x4＋3.5x3-2.6x2＋1.7x-0.8用秦九韶算法求当x=5时多项式的值。

分析：先画出程序框图（见课本）再利用TI-voyage200图形计算器操作：

（其中表示f(x)=5x5＋2x4＋3.5x3-2.6x2＋1.7x-0.8的系数，可以随意改变，通过图形计算器，学生很快的把系数的输入换成用数组来代替，从而得到更普遍的程序，激发学生的求学创新精神）

排序

大家考完试后如果要排一下成绩的话，单靠人手该怎样操作呢？如果你们用计算机里的软件（如：电子表格）又如何操作？

排序的算法很多，课本主要介绍里两种排序方法：直接插入排序和冒泡排序

1、直接插入排序

基本思想

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

2、冒泡排序

基本思想

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

例3、用冒泡法对数据7，5，3，9，1从小到大进行排序。

以下是第一趟排序，最后我们得到新数列为：5，3，7，9，1

按上述方法我们进行第二趟、第三趟......排序，直到这5个数按从小到大进行排序为止：

如下图所示：

第二趟第三趟第四趟

利用TI-voyage200图形计算器操作，把冒泡排序变成程序为：

运行结果为：

小结

(1)秦九韶算法计算多项式的值及程序设计

(2)数字排序法中的常见的两种排序法直接插入排序法与冒泡排序法

(3)冒泡法排序的计算机程序设计

(4)注意循环语句的使用与算法的循环次数，对算法进行改进。