2023学年完整公开课版秦九韶算法

1.3算法案例(第二课时）

秦九韶算法第1页问题提出

1.辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合.所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两数的最大公约数；第1页第2页秦九韶算法2.对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.

所谓更相减损术，就是对于两个给定的不全为偶数的数，以较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差和较小的数相等，此时相等的两数就是原来两数的最大公约数；第1页3知识探究(一):秦九韶算法的基本思想

思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？4+3+2+1=10次乘法运算，5次加法运算.

第1页第3页思考2:在上述问题中，若先计算x2的值，然后依次计算x2·x，(x2·x)·x，((x2·x)·x)·x的值，这样每次都可以利用上一次计算的结果，再将这些数与x和1相加，那么一共做了多少次乘法运算和多少次加法运算？

4次乘法运算，5次加法运算.

第1页5第4页思考3:求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，一共要做多少次乘法运算和多少次加法运算？f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0

=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.（上有n-1组括号）利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种形式？最多需次乘法运算，n次加法运算.

第1页第5页第一步，计算v1=anx+an-1.

第二步，计算v2=v1x+an-2.第三步，计算v3=v2x+an-3.

…第n步，计算vn=vn-1x+a0.思考4:对于由内向外逐层计算一次多项式的值，其算法步骤如何？

共需n次乘法运算，n次加法运算第1页第6页思考5:上述求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法称为秦九韶算法，利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？

把运算的次数由至多次乘法运算和n次加法运算，减少为至多n次乘法运算和n次加法运算南宋数学家秦九韶《九章算术》（1202－1261）至今七百多年，仍是先进算法。第1页第7页思考6:在秦九韶算法中，记v0=an，则第k步的算式是什么？

vk=vk-1x+an-k(k=1，2，…，n)在秦九韶算法中，这是一个反复执行的步骤第一步，计算v1=anx+an-1.

第二步，计算v2=v1x+an-2.第三步，计算v3=v2x+an-3.

…第n步，计算vn=vn-1x+a0.第1页第8页理论迁移

例1已知一个5次多项式为 用秦九韶算法求f(5)的值.f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=5×5+2=27；v2=27×5+3.5=138.5；v3=138.5×5-2.6=689.9；v4=689.9×5+1.7=3451.2；v5=3451.2×5-0.8=17255.2.所以f(5)==17255.2.第1页第9页

f(x)=((((0.83x+0.41)x+0.16)x+0.33)x+0.5)x+1v1=0.83×5+0.41=4.56；v2=4.56×5+0.16=22.96；v3=22.96×5+0.33=115.13；v4=115.13×5+0.5=576.15；v5=576.15×5+1=2881.75.所以f(5)=2881.75.学生练习：书P45练习2当x=5时的函数值；第1页第10页知识探究(二):秦九韶算法的程序设计

思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数n，最高次 项的系数an和x的值.

第二步，令v=an，i=n-1.

第三步，输入i次项的系数ai.

第四步，v=vx+ai，i=i-1.第五步，判断i≥0是否成立.若是，则返回第 三步；否则，输出多项式的值v.

第1页12第11页思考2:该算法的程序框图如何表示？开始输入n，an，x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1结束输出v否见书P39算法步骤是INPUT

“n=”；nINPUT

“an=”；aINPUT

“x=”；xv=ai=n-1WHILE

i>=0INPUT

“ai=”；av=v*x+ai=i-1WENDPRINT

vEND第1页13第12页

例1已知一个5次多项式为

用秦九韶算法求f(5)的值.另法：523.5-2.61.7-0.8x=52527135138.5692.5689.93449.53451.21725617255.2所以f(5)=17255.2.第1页14第13页

f(x)=((((0.83x+0.41)x+0.16)x+0.33)x+0.5)x+1v1=0.83×5+0.41=4.56；v2=4.56×5+0.16=22.96；v3=22.96×5+0.33=115.13；v4=115.13×5+0.5=576.15；v5=576.15×5+1=2881.75.所以f(5)=2881.75.学生练习：书P45练习2当x=5时的函数值；第1页15第14页

学生练习：书P45练习2当x=5时的函数值；0.830.410.160.330.51x=54.154.5622.822.96114.8115.13575.65576.152880.752881.75所以f(5)=2881.75.第1页16第1页5

f(x)=((((((7x+6)x+5)x+4)x+3)x+2)x+1)xv1=7×3+6=27；v2=27×3+5=86；v3=86×3+4=262；v4=262×3+3=789；v5=789×3+2=2369所以f(5)=21324学生练习：书P48习题A

2当x=3时的函数值；v6=2369×3+1=7108v7=7108×3=21324第1页17第16页另法：76

5

4

32

1

0x=321278186258262786789236721324所以f(3)=21324学生练习：书P48习题A

2当x=3时的函数值；23697107710821324第1页18第17页法一：当x=6时的函数值.补充练习：《名校学案》课后巩固作业（八）7第1页19第18页另法：312

8

-3.5

7.25

-13

x=6183018018811286754.26747当x=6时的函数值.补充练习：《名校学案》课后巩固作业（八）71124.540525.240530.2243181.2243168.2第1页20第19页

例2阅读下列程序，说明它解决的实际问题是什么？INPUT

“x=”；an=0y=0WHLEn<5

y=y+(n+1)*a∧n

n=n+1WENDPRINT

yEND求多项式在x=a时的值.

补充练习第1页21第20页小结作业

评价一个算法好坏的一个重要