1.3.2算法案例(第二课时).ppt

算法案例（2）,计算多项式f（x） =x5+x4+x3+x2+x+1当x = 5的值.,算法1：,:因为f（x） =x5+x4+x3+x2+x+1,所以f（5）=55555,=3125625125255,= 3906.,算法2：,f（5）=55+54+53+52+5+1,=5×(54535251） +1,=5×(5×(5+5+5+1)+1)+1,=5×(5×(5× (5+5+1）+1)+1)+1,=5×(5×(5×(5×(5+1)+1)+1）+1）+1.,分析：两种算法中各用了几次乘法运算？和几次加法运算？,数书九章秦九韶算法,对该多项式按下面的方式进行改写：,思考：当知道了x的值后该如何求多项式的值？,这是怎样的一种改写方式？最后的结果是什么？,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,最后的一项是什么？,这种将求一个n次多项式f（x）的值转化成求n个一次多项式的值的方法，称为秦九韶算法.,思考：在求多项式的值上，这是怎样的一个转化？,例2 已知一个五次多项式为,用秦九韶算法求这个多项式当x = 5的值.,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当x = 5时的值：,所以，当x = 5时，多项式的值等于17255.2,你从中看到了怎样的规律？怎么用程序框图来描述呢？,开始,输入f (x)的系数： a0, a1, a2, a3, a4, a5,输入x0,n=0,v=a5,v= v·x0+a5-n,n=n+1,n 5?,输出v,结束,否,是,注意：要想使用检验功能，请使用前，先要减低宏的安全限制.,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,方法1：,S1：比较第2个数与第1个数的大小，并排序得3，8,S2：将第3个数与S1中的数比较，插入适当的位置，得到 2，3，8,S3：将第4个数与S2中的数比较，并插入适当的位置，如此继续下去，直到把最后一个数插入到上一步已排好 的数列的合适位置为止，得到：,2 ，3， 5， 8,2 ，3， 5， 8 ，9,2 ，3， 5， 6 ， 8 ， 9,S4：,S5：,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,方法1：,过程演示,开始,排第1次,排第2次,排第3次,排第4次,排第5次,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,方法2：,S1：用第1个数与第2个数比较，若前者小则两数不变，否则，交换这两个数的位置.,S2：按这样的原则，比较第2个数和第3个数，前者小则两数不变，否则，交换这两个数的位置直到比完最后两个数.（称为“一趟”）,S3：如果前一趟的比较中交换的次数为0，说明排序已完成，否则回到S2.,根据题意，一趟后的结果是什么？,为什么说前一趟的比较中交换为0次时，排序完成？,3，2，5， 8， 6 ， 9,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,请将每一趟的结果写出来,第1趟,该趟中交换的次数为_次,4,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,请将每一趟的结果写出来,第2趟,该趟中交换的次数为_次,2,排序的算法,将下面数字按由小到大的顺序排列,8，3，2，5，9，6,请将每一趟的结果写出来,第3趟,该趟中交换的次数为_次，,0,所以排序的结果为：,2，3，5，6，8，9,(1)秦九韶算法计算多项式的值及程序设计； (2)数字排序法中的常见的两种排序法直接插入排序法与冒泡排序法.,小结,课本P48习题1.3第2，3题,课后作业,