算法案例秦九韶算法.docx

§1.3算法案例---秦九韶算法
高二数学组梅杰
一.教学目标
1.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；
2.能利用秦九韶算法进行一些多项式的计算，能用循环结构表示算法步骤。
二．教学重难点
1.理解秦九韶算法体现的思想；
2.用循环结构表示算法步骤。
三.教学过程
（一）创设情景，揭示课题
问题1：请同学们设计一个算法，计算当时的值。
学生可能会提出两种做法：
做法一：把5代入多项式的每一项，计算每一项的值，然后相加；
做法二：先计算x的幂，可以利用前面的计算结果，以减少计算量，即先计算x2,然后依次计算x2.x,(x2.x).x,((x2.x).x).x的值，再各项相加。
结合学生的做法，进行比较点评：
①有哪些优点？哪些不足？
②计算次数各是多少？有哪些计算种类？
[做法一有15次乘法运算，5次加法运算；做法二有9次乘法运算，5次加法运算]
对于计算机来说，做一次乘法运算所用时间要比做一次加法要长的多，所以算法好坏的一个重要标志仍然是运算的次数
问题2：上述问题1还有没有更有效的算法呢？
老师引导学生从因式分解的角度，将多项式变形为：

思考：从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？
师生一起列表表示出计算过程：
原多项式x的系数423.5-2.61.7--0.8运算20110567.52824.514131+变形后x的系数422113.5564.92826.214130.2*5思考：让学生回顾整个计算过程，用此种方法一共进行了多少次乘法、加法运算？
点评：一共进行了5次乘法，5次加法运算，相比较前两种做法，此做法更快、更方便，而且在计算过程中，只与多项式的系数有关。
这种算法就是“秦九韶算法”，在此可以介绍下秦九韶生平。【见附页】
（二）研探新知
问题1：怎样用秦九韶算法求一般的多项式当x=x0时的值？
类似上述方法，将多项式变形为：

由内向外逐层计算一次多项式的值，把n次多项式的求值问题转化为求n个一次多项式值的问题，即求：,
,

……
.
思考：秦九韶算法使用一般的多项式中运算的次数？运算种类？
点评:秦九韶算法使用一般的多项式的求值问题.直接法乘法运算的次数最多可到达,加法最多次.秦九韶算法通过转化把乘法运算的次数减少到最多次,加法最多次.
问题2：怎样用程序语言来表示秦九韶算法呢？
通过观察上述秦九韶算法中的n个一次式，可见计算要用到的值，若令，我们可以得到下面的递推公式：
,
（k=1,2,…,n）
这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。
师生一起分三步进行：
自然语言写算法：
第一步,输入多项式次数,最高次项的系数和的值.
第二步,；第三步,输入次项的系数；第四步,；
第五步,判断是否大于等于,若是,则返回第三步;否则,输出多项式的值.
②画程序框图（略）
③翻译成程序语言
INPUT“n=”;n
INPUT“an=”;a
INPUT“x=”;x
v=a
i=n-1
WHILEi>=0
PRINT“i=”;i
INPUT“ai=”;a
v=v*x+a
i=i-1
WEND
PRINTv
END
（三）例题讲解
例1.利用秦九韶算法计算
当时的值，并统计需要多少次乘法计算和多少次加法计算？
例2．利用秦九韶算法计算多项式
当时的值
点评:如果多项式函数中有缺项的画,要以系数为的项补齐后再计算.
例3.某城市2001年末汽车保有量为万辆,预计此后每年报废上一年末汽车保有量的,并且每年新增汽车万辆.设计算法,计算经过多少年可使汽车保有量达到万辆.将此算法用程序语言给出.
解：设,经过几年的汽车保有量为,则

上述各式充分说明了秦九韶算法的优点:可以通过递推关系进行迭代处理.
程序为:C=0.94
A=30
n=0
WHILEA<40
A=A*C+3
n=n+1
WEND
PRINTn
END
（四）课堂小结
（五）布置作业
秦九韶生平简介
南宋大数学家秦九韶秦九韶（公元1202－1261），字道古，安岳人。秦九韶与李冶、杨辉、朱世杰并称宋元数学四大家。其父秦季栖，进士出身，官至上部郎中、秘书少监。秦九韶聪敏勤学。宋绍定四年（1231），秦九韶考中进士，先后担任县尉、通判、参议官、州守、同农、寺丞等职。先后在湖北、安徽、江苏、浙江等地做官，1261年左右被贬至梅州（今广东梅县），不久死于任所。他在政务之余，对数学进行虔心钻研，并广泛搜集历学、数学、星象、音律、营造等资料，进行分析、研究。宋淳祜四至七年（1244至1247），他在为母亲守孝时，把长期积累的数学知识和研究所得加以编辑，写成了闻名的巨著《数学九章》，并创造了“大衍求一术”。这不仅在当时处于世界领先地位，在近代数学和现代