《湖北省十堰市郧阳中学人教版（b）高中数学必修三教案 13 秦九韶算法与排序》由会员分享，可在线阅读，更多相关《湖北省十堰市郧阳中学人教版（b）高中数学必修三教案 13 秦九韶算法与排序（2页珍藏版）》请在金锄头文库上搜索。
1、 113 3 秦九韶算法与排序（两个课时）秦九韶算法与排序（两个课时）教学目标：教学目标：1 了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计 算效率的实质。 2 掌握数据排序的原理能使用直接排序法与冒泡排序法给一组数据排序， 进而能设计冒泡排序法的程序框图及程序，理解数学算法与计算机算法的区别，理解计算机 对数学的辅助作用。 教学重点：教学重点：秦九韶算法的特点及其程序设计，两种排序法的排序步骤及其程序设计 教学难点教学难点:秦九韶算法的先进性理解及其程序设计,排序法的计算机程序设计 教学过程教学过程 (秦九韶计算多项式的方法秦九韶计算多项式的方法) ) 例例 1、 设计
2、求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7 当 x=5 时的值的算法，并写出程序。个别学生提出一般的解决方案，如：x=5 y=2 * x5 5 * x4 4 * x3 + 3 * x2 6 * x + 7 PRINT“y=” ；y END提问：例 1 计算时需要多少次乘法计算？多少次加法计算？有什么优缺点？( (上述算法一共上述算法一共做了解做了解15 次乘法运算，次乘法运算，5 次加法运算，优点是简单、易懂。缺点是不通用，不能解决任意多次加法运算，优点是简单、易懂。缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高。项式的求值问题，而且计算效率不高。)提问：计算
3、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从内到
4、外，如果把 每一个括号都看成一个常数，x 的系数依次是什么？用图表可以表示为：多项式 x 系数2-5-43-67运算10251055402670+变形后 x 的“系数“25211085342677*5最后的系数 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+a
5、n-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=anvk=vk-1+an-k(k=1,2,n)这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。例例 2、已知一个五次多项式 f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8
6、用秦九韶算法求当 x=5 时多项 式的值。分析：先画出程序框图（见课本）排序排序排序的算法很多，课本主要介绍里两种排序方法：直接插入排序直接插入排序和冒泡排序冒泡排序1、直接插入排序、直接插入排序基本思想：基本思想：插入排序的思想就是读一个，排一个。将第个数放入数组的第个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中 （由于算法简单，可以举例说明）2、冒泡排序、冒泡排序基本思想：基本思想：依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第 1 个数和第 2 个数,大数放前,小数放后.然后比较第 2 个数和第 3 个数直到比较最后两个数.第一趟 结束,最小的一定沉到最后.重复上过程,仍从第 1 个数开始,到最后第 2 个数 由于在 排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序. 例 3、用冒泡法对数据 7，5，3，9，1 从小到大进行排序。 小结小结 (1)秦九韶算法计算多项式的值及程序设计(2)数字排序法中的常见的两种排序法直接插入排 序法与冒泡排序法(3)冒泡法排序的计算机程序设计(4)注意循环语句的使用与算法的循环次 数，对算法进行改进。
