《1.3.2 秦九韶算法与排序》由会员分享，可在线阅读，更多相关《1.3.2 秦九韶算法与排序（5页珍藏版）》请在金锄头文库上搜索。
1、英格教育文化有限公司 http:/www.e-l- 全新课标理念，优质课程资源学习方法报社 第 1 页 共 5 页13 秦九韶算法与排序【学习目标学习目标】：（1） 了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率 的实质. （2） 掌握数据排序的原理能使用直接排序法与冒泡排序法给一组数据排序，进而能设计冒 泡排序法的程序框图及程序，理解数学算法与计算机算法的区别，理解计算机对数学 的辅助作用.【学习重点学习重点】秦九韶算法的特点及其程序设计，两种排序法的排序步骤及其程序设计（重点放在循环语句的应用上）【学习难点学习难点】秦九韶算法的先进性理解及其程序设计,排序法的计
2、算机程序设计【学法与学习用具学法与学习用具】：学法：学法：探究秦九韶算法对比一般计算方法中计算次数的改变，体会科学的计算；模仿排序法 中数字排序的步骤，理解计算机计算的一般步骤，领会数学计算在计算机上实施的要求.学习用具学习用具:计算机，TI-voyage200 图形计算器【课堂过程课堂过程】秦九韶计算多项式的方法秦九韶计算多项式的方法 例例 1 设计求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7 当 x=5 时的值的算法，并写出程序.个别学生提出一般的解决方案，如：x=5y=2 * x5 5 * x4 4 * x3 + 3 * x2 6 * x + 7PRINT“y=” ；yE
3、ND提问：例 1 计算时需要多少次乘法计算？多少次加法计算？有什么优缺点？答：上述算法一共做了解 15 次乘法运算，5 次加法运算，优点是简单、易懂.缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高.提问：计算 x 的幂时，可以利用前面的计算结果，以减少计算量，即先计算 x2，然后依次计算 x2.x， （x2.x）.x， (（x2.x）.x).x 的值,这样计算上述多项式的值,一共需要多少次乘法，多少次加法?答：上述算法一共做了解 4 次乘法运算，5 次加法运算.英格教育文化有限公司 http:/www.e-l- 全新课标理念，优质课程资源学习方法报社 第 2 页 共 5 页结论：
4、第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法更快地得到结果.我们把多项式变形为：f(x)= 2x5-5x4-4x3+3x2-6x+7=(2x-5)x-4)x+3)x-6)x+7从内到外，如果把每一个括号都看成一个常数，x 的系数依次是什么？用图表可以表示为：多项式 x 系数2-5-43-67运算10251055402670+变形后 x 的“系数“25211085342677*5最后的系数 2677 即为所求的值, 请描述上述计算过程.上述算法就是“秦九韶算法”.如何应用秦九韶算法完成一般的
5、多项式 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-2v3=v2x+an-3.vn=vn-1x+a0这样，把 n 次多项式的求值问题转化成求 n 个一次多项式的值的问题观察秦九韶算法的数学模型，计算
6、vk时要用到 vk-1的值，若令 v0=an，我们可以得到下面的递推公式：v0=an英格教育文化有限公司 http:/www.e-l- 全新课标理念，优质课程资源学习方法报社 第 3 页 共 5 页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
7、的系数，可以随意改5,2,3.5, 2.6,1.7, 0.8变，通过图形计算器，学生很快的把系数的输入换成用数组来代替，从而得到更普遍的程序，激发学生的求学创新精神）排序排序大家考完试后如果要排一下成绩的话，单靠人手该怎样操作呢？如果你们用计算机里的软件（如：电子表格）又如何操作？排序的算法很多，课本主要介绍里两种排序方法：直接插入排序直接插入排序和冒泡排序冒泡排序1. 直接插入排序直接插入排序基本思想基本思想插入排序的思想就是读一个，排一个.将第个数放入数组的第个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置将该位置以及以后的元素向后推移一个位置，将读入的新
8、数填入空出的位置中 （由于算法简单，可以举例说明）2. 冒泡排序冒泡排序基本思想基本思想 依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第 1 个数和第 2 个数,大 数放前,小数放后.然后比较第 2 个数和第 3 个数.直到比较最后两个数.第一趟结束,最 小的一定沉到最后.重复上过程,仍从第 1 个数开始,到最后第 2 个数. 由于在排序过程 中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序. 运行英格教育文化有限公司 http:/www.e-l- 全新课标理念，优质课程资源学习方法报社 第 4 页 共 5 页例 3 用冒泡法对数据 7，5，3，9，1 从小到大进行排序.
9、以下是第一趟排序，最后我们得到新数列为：5，3，7，9，1按上述方法我们进行第二趟、第三趟.排序，直到这 5 个数按从小到大进行排序为止： 如下图所示：第二趟 第三趟 第四趟利用 TI-voyage200 图形计算器操作，把冒泡排序变成程序为：运行结果为：75391573915379173791537195178 953719351793157913579注意：可以把 “If riri+1 then” 改为“if riri+1 then”则排序的方向 就是按照从大到小的顺序进行。学生 回发现排序是很有趣的事情，鼓励他 们研究新的排序方法！英格教育文化有限公司 http:/www.e-l- 全新课标理念，优质课程资源学习方法报社 第 5 页 共 5 页小结小结 (1)秦九韶算法计算多项式的值及程序设计 (2)数字排序法中的常见的两种排序法直接插入排序法与冒泡排序法 (3)冒泡法排序的计算机程序设计 (4)注意循环语句的使用与算法的循环次数，对算法进行改进.
