1.3算法案例—(2)秦九韶算法ppt课件

格式：ppt
大小：743.48 KB
文档页数：19

下载文档原格式

1.3算法案例—(2)秦九韶算法ppt课件

A. 4 B. 5 C. 10 D. 20 21672=8127×2+5418
8127=5418×1+2709
5418=2709×2+0
2
辗转相除法与更相减损术的比较:
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主; 计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.
一般地,对于一个n次多项式 f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0. 我们可以改写成如下形式:
f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0. 求多项式的值时,首先计算最内层括号内一次多项式的值,即 v1=anx+an-1, 然后由内向外逐层计算一次多项式的值,即
13
v1=anx+an-1,
v2=v1x+an-2,
v3=v2x+an-3, ……, vn=vn-1x+a0.
观察上述秦九韶算法中的n个一次式,可见 vk的计算要用到vk-1的值. 若令v0=an,得
v0=an, vK=vK-1x+an-k(k=1,2,……,n
这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现.因此可用循环结构来实现。
然后由内向外逐层计算一次多项式的值,即
v0=2 v1=v0x-5=2×5-5=5
v2=v1x-4=5×5-4=21
v3=v2x+3=21×5+3=108

数学：1.3.2《算法案例-秦九韶算法》课件(2)(新人教A版必修3)

练习:把89化为五进制的数. 解:以5作为除数,相应的除法算式为: 余数 5 89 5 17 4 5 3 2 0 3 ∴ 89=324(5).
小结
• 进位制的概念及表示方法; anan-1…a1a0(k) =an×kn+an-1×kn-1+…+a1×k1+a0×k0 . • 各种进位制之间的相互转化.
例4:把89化为二进制的数. 我们可以用下面的除法算式表示除2取余法: 把算式中各步所得的余数余数 2 89 从下到上排列,得到 2 44 1 89=1011001(2). 2 22 0 可以用2连续去除89或所得 2 11 0 商(一直到商为0为止),然后 2 5 1 取余数---除2取余法. 1 2 2 这种方法也可以推广为把 0 21 十进制数化为k进制数的 0 1 算法,称为除k取余法.
＝(„((anx＋an－1)x＋an－2)x＋„＋a1)x＋a0
f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0.
求多项式的值时,首先计算最内层括号内一次多项式的值,即 v1=anx+an-1, 然后由内向外逐层计算一次多项式的值,即 v2=v1x+an-2, v3=v2x+an-3, ……, vn=vn-1x+a0. 这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.
v1=v0x-5=2×5-5=5
v2=v1x-4=5×5-4=21
v3=v2x+3=21×5+3=108
v4=v3x-6=108×5-6=534
v5=v4x+7=534×5+7=2677
所以,当x=5时,多项式的值是2677.

高中数学精品课件§1-3 算法案例第2课时秦九韶算法与进位制课件

反思感悟将k进制数anan－1…a1a0(k)化为十进制数的方法：把k进制数anan－1 …a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式，然后计算出结果即为对应的十进制数.
跟踪训练2 (1)把二进制数1 110 011(2)化为十进制数. 解 1 110 011(2)＝1×26＋1×25＋1×24＋0×23＋0×22＋1×21＋1×20＝115. (2)将8进制数314 706(8)化为十进制数. 解 314 706(8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80＝104 902. 所以，化为十进制数是104 902.
题型三十进制化k进制
例3 将十进制数458分别转化为四进制数和六进制数. 解算式如图，
则458＝13 022(4)＝2 042(6).
反思感悟十进制数化为k进制数的思路为除k取余 → 倒序写出 → 标明基数 .
跟踪训练3 把89化为二进制数. 解算式如图，
则89＝1 011 001(2).
解 f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1 ＝((((x＋5)x＋10)x＋10)x＋5)x＋1. 当x＝－2时，有v0＝1； v1＝v0x＋a4＝1×(－2)＋5＝3； v2＝v1x＋a3＝3×(－2)＋10＝4； v3＝v2x＋a2＝4×(－2)＋10＝2； v4＝v3x＋a1＝2×(－2)＋5＝1； v5＝v4x＋a0＝1×(－2)＋1＝－1. 故f(－2)＝－1.
第一章 §1.3 算法案例
第2课时秦九韶算法与进位制
学习目标
XUEXIMUBIAO
1.了解秦九韶算法. 2.了解生活中的各种进位制，了解计算机内部运算为什么选择二进制. 3.会用除k取余法把十进制转换为各种进位制，并理解其中的数学规律．

必修三课件：1.3.2秦九韶算法(共14张PPT)

算法步骤第一步：输入多项式次数n、最高次项的系数an和x的值第二步：将v的值初始化为an,将i的值初始化为n-1 第三步：输入i次项的系数ai 第四步：v=vx+ai,i=i-1. 第五步：判断i是否大于或等于0,若是, 则返回第三步;否则,输出多项式的值v.
秦九韶算法的程序设计
程序框图
第一步：输入多项式次数n、最高次项的系数an和x的值第二步：将v的值初始化为an, 将i的值初始化为n-1
算法1：因为ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１
所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１
=3125＋625＋125＋25＋5＋１
= 3906 10次的乘法运算,5次的加法运算
算法2：
ｆ（5）=5５＋5４＋5３＋5２＋5＋１4次的乘法运算,5次的加法运算
=5×（5４＋5３＋5２＋5＋１）＋１ =5×（5×（5３＋5２＋5 ＋１）＋１）＋１ =5×（5×（ 5× （5２＋5 ＋１）＋１）＋１）＋１ =5×（5×（ 5× （5× （5＋１）＋１）＋１）＋１）＋１
1.3.2 案例2、秦九韶算法
复习
1、求两个数的最大公约数的两种方法分别是（）和
（）.
辗转相除法更相减损术
2、两个数21672，8127的最大公约数是（A ）
A、2709 B、2606 C、2703 D、2706
案例2、秦九韶算法
秦九韶算法是求一元多项式的值的一种方法。
怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？
=5x5x5x5x5＋5x5x5x5＋5x5x5＋5x5＋5＋１ =3125＋625＋125＋25＋5＋１

秦九韶算法课件

(2)已知一个五次多项式f(x)＝2x5－4x3＋3x2 －5x＋1，用秦九韶算法求这个多项式当x＝3 是的值．
秦九韶算法课件
[探究] 1.用秦九韶算法求多项式的值时，几次多项式就做几次乘法运算，对吗？
2．用秦九韶算法求多项式f(x)＝anxn＋an－1xn －1ቤተ መጻሕፍቲ ባይዱ…＋a1x＋a0在x＝x0时的值时，v0是什么？ v1呢？
秦九韶算法课件
[规律总结] 用秦九韶算法时要正确将多项式的形式进行改写，然后由内向外依次计算．当多项式函数中间出现空项时，要以系数为零的齐次项补充．
秦九韶算法课件
用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋ 4x4＋3x3＋2x2＋x当x＝3时的值．
[探究] 解决本题首先需要将原多项式化成 f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋ 1)x的形式，其次再弄清v0，v1，v2，…，v7 分别是多少，再针对这些式子进行计算．
秦九韶算法课件
用更相减损术检验： 80－36＝44， 44－36＝8， 36－8＝28， 28－8＝20， 20－8＝12， 12－8＝4， 8－4＝4. 故80和36的最大公约数是4.
秦九韶算法课件
[规律总结] 更相减损术与辗转相除法都能
求两个数的最大公约数，二者的区别与联系
求出其中两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，所得的结果就是这三个数的最大公约数．
秦九韶算法课件
[解析] 先求175与100的最大公约数： 175＝100×1＋75,100＝75×1＋25，
75＝25×3， ∴175与100的最大公约数是25. 再求25与75的最大公约数：
39， 42＝39×1＋3,39＝3×13， ∴288和123的最大公约数是3.

高中数学必修3公开课课件 1.3.2算法案例--秦九韶算法

次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多式求值的各种算法中，秦九韶算法是一个优秀算法.
10
课后再做好复习巩固. 谢谢！
再见！
新疆王新敞
奎屯
王新敞特级教师源头学子小屋 wxckt@ 新疆奎屯
再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果。显然少了6次乘法运算。
这种算法就叫秦九韶算法。
3
秦九韶算法
把一个多项式
f (x) an xn an1xn1 an2 xn2 a1x a0
改写为：
f (x) an xn an1xn1 an2 xn2 a1x a0 (an xn1 an1xn2 an2 xn3 a1)x a0 ((an xn2 an1xn3 a2 )x a1)x a0
·2007·
11
案例2 秦九韶算法
2019年5月6日星期一
1
问题提出
1.辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合.
2.对于求n次多项式的值，在我国古代数学中也有一个优秀算法，即秦九韶算法，本节对这个算法作些了解和探究.
=……
( ((an x an1)x an2 )x a1) a0
4
秦九韶算法
对于f(x)=(…((anx+an-1)x+ an-2)x+…+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤：
第一步，计算v1=anx+an-1. 第二步，计算v2=v1x+an-2. 第三步，计算v3=v2x+an-3.

数学：1.3.2《算法案例-秦九韶算法》课件(3)(新人教版a版必修3)

知识探究(一):秦九韶算法的基本思想
思考1:对于多项式f(x)=x5+x4+x3+x2+x+1，求f(5)的值. 若先计算各项的值，然后再相加，那么一共要做多少次乘法运算和多少次加法运算？
4+3+2+1=10次乘法运算， 5次加法运算.
思考2:在上述问题中，若先计算x2的值，然后依次计算x2·x，(x2·x)·x， ((x2·x)·x)·x的值，这样每次都可以利用上一次计算的结果，再将这些数与x 和1相加，那么一共做了多少次乘法运算和多少次加法运算？
例2 阅读 INPUT “x=”；a 下列程序，说 n=0 明它解决的实 y=0 际问题是什么？ WHLE n<5 y=y+(n+1)*a∧n n=n+1 WEND PRINT y END
求多项式在x=a时的值.
f (x ) = 1 + 2x + 3x 2 + 4x 3 + 5x 4
小结作业
评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法. 在多项式求值的各种算法中，秦九韶算法是一个优秀算法.
1.3
算法案例
第二课时
问题提出
1.辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合.
2.对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.
在孤独晓寂结业的那一天，莫艳艳终于下了最后通牒“晓寂妹子，你已经修成正果了，你赶紧的吧，明天你就要去师兄哪里报道了，你不会还是要以这种别扭的方式出现在别人面前吧，你不着急，我都替你急死了！” 那一个晚上，孤独晓寂因为那样的一种事情都过得惴惴不安，睡不好觉，第二天一大早，莫艳艳便拿了一大堆衣服来到孤独晓寂的房间，她十分悲壮的开口“我决定了，要亲自改造你，今天，你必须去跟你的师兄打招呼，然后跟他一起去单位报到！” 莫艳艳果断的催促着孤独晓寂抓紧时间洗漱，然后拿出她认为比较适合孤独晓寂的衣服一件件的给她试穿，直到她觉得很满意为止。换好衣服，又将她的脸蛋涂抹了起来，尽管孤独晓寂小声的抗议“艳艳，我不喜欢化妆，而且我也不会化”。莫艳艳直接无视她的抗议“妹子，这年头素颜就等于自杀，懂么，姐这是在拯救你！” 将她收拾利索之后硬是将她拽了出去，等在司空阳宇必经之路的转角处。虽然孤独晓寂仍是碎碎念“艳艳，要不今天就算了吧，我觉得这样的自己好奇怪呀！” 莫艳艳不容置疑的瞪她一眼“到目前为止还没有人敢质疑姐姐我的化妆水平！”顺势对她举了举握紧的拳头、孤独晓寂便悄悄地闭了嘴。等到司空阳宇快要走近的时候，莫艳艳不容分说的将孤独晓寂一把推向了司空阳宇的身上，孤独晓寂尴尬到脸颊红透，挠了挠头轻声的说了句“真是不好意思”，便往后退了一步。司空阳宇不在意的笑了笑“你今天又在跑步么？” 孤独晓寂没反应过来的“啊？”了声。司空阳宇笑着提醒“我看你好像经常在这条路上跑步。”

《秦九韶算法》课件

秦九韶பைடு நூலகம்法的代码示例
} ``` Java实现
秦九韶算法的代码示例
01
```java
02
import java.util.Scanner;
public class Main {
03
秦九韶算法的代码示例
01
02
03
public static void main(String[] args) {
Scanner scanner = new
秦九韶算法的步骤解析
01
确定多项式的最高次项系数和次数。
02
根据秦九韶算法的公式，计算一次多项式的系数。
03
利用一次多项式求值公式，计算多项式的值。
04
重复以上步骤，直到求出所有需要计算的多项式的值。
秦九韶算法的公式推导
根据多项式求值原理，推导出秦九韶算法的公式。
利用递归的思想，将高次多项式转化为一次多项式，推导出秦九韶算法的公式。
编写代码
按照秦九韶算法的步骤，编写相应的代码。需要注意代码的健壮性和可读性，以便于后续的维护和调试。
测试代码
通过输入不同的多位数，测试代码的正确性和性能。
秦九韶算法的代码示例
C语言实现 ```c
int main() {
秦九韶算法的代码示例
int n, x = 0, i, d; printf("请输入一个多位数：");
05
秦九韶算法的优缺点
秦九韶算法的优点
01
02
03
高效性
秦九韶算法将多项式求值问题转化为一系列一元运算，减少了乘法的次数，提高了运算效率。
易于编程实现
秦九韶算法的步骤明确，易于转化为程序代码，便于计算机实现。

算法案例2秦九韶算法课件

k
已知n 已知次多项式 Pn ( x) = a0 xn + a1 xn−1 + ... + an−1 x + an
我国南宋时期的数学家秦九韶(约我国南宋时期的数学家秦九韶约1202-1261) 在他的著作《数书九章》中提出了下面的算法. 他的著作《数书九章》中提出了下面的算法把一个n次多项式把一个次多项式 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
, 如果在一种算法中计算x0 (k = 2, 3, 4, ..., n) k 9 的值需要 − 1次乘6次乘法, 3次加法), 那么计算 n ( x0 )的值共需要______ 次运算.
k
已知n 已知次多项式 Pn ( x) = a0 xn + a1 xn−1 + ... + an−1 x + an
《考一本》第10课时考一本》课时
【例1】】
5次多项式为已知一个次多项式为 f ( x) = 4x + 2x + 3.5x − 2.6x + 1.7 x − 0.8 ,

新人教A版必修三1.3《算法案例---秦九韶算法》ppt课件

共做了4次乘法运算，5次加法运算。
《数书九章》——秦九韶算法设 f ( x) 是一个n 次的多项式
f ( x) an x an 1 x a1 x a0 对该多项式按下面的方式进行改写：
n
n 1
f ( x) an x n an 1 x n 1 a1 x a0
算法案例
第二课时
复习引入:
1、求两个数的最大公约数的两种方法分别是（）和（）。
2、两个数21672，8127的最大公约数是（
）
A、2709
B、2606
C、2703
D、2706
新课讲解:
怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？
计算多项式ｆ(ｘ) =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x = 5的值的算法：算法1：因为ｆ(ｘ) =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１
v 0 a n v k v k 1 x a n k ( k 1,2, , n)
这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。
n=1
v=a5
n=n+1 n≤5?
Y
v=vx0+a5-n
N
输出v
结束
例：已知一个五次多项式为
5 4 3
f ( x) 5 x 2 x 3.5 x 2.6 x 1.7 x 0.8
f ( x) ( (an x an 1 ) x an 2 ) x a1 ) x a0
要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即
v1 an x an 1 v2 v1 x an 2

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

=(((2x2-5x-4)x+3)x-6)x+7 v3=v2x+3=21×5+3=108
=((((2x-5)x-4)x+3)x-6)x+7 v4=v3x-6=108×5-6=534
v5=v4x+7=534×5+7=2677
当x=5时,多项式
的值是多少？
所以,当x=5时,多
这种求多项式值的方法就项叫式秦的九值韶是算26法77..
A. 4 B. 5 C. 10 D. 20 21672=8127×2+5418
8127=5418×1+2709
5418=2709×2+0
2
辗转相除法与更相减损术的比较:
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主; 计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则(x)=x5+x4+x3+x2+x+1当x = 5的值
算法2：
ｆ(5)=5５＋5４＋5３＋5２＋5＋1
=5×(5４＋5３＋5２＋5＋1 ) ＋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
解:原多项式先化为:
f(x)=2x6-5x5 +0×x4-4x3+3x2-6x+0,列表如下
2 -5 0 -4 3 -6 0
解法二:列表
原多项式的系数
2 -5 -4 3 -6 7
x=5
10 25 105 540 2670
2 5 21 108 534 2677
v0 v1 v2 v3 v4 v5 多项式所以,当x=5时,多项式的值是2677. 的值.
12
练一练:用秦九韶算法求多项式 f(x)=2x6-5x5 -4x3+3x2-6x当x=5时的值.
6
《数书九章》——秦九韶算法设f(x) 是一个n 次的多项式
f ( x ) a n x n a n 1 x n 1 a 1 x a 0
对该多项式按下面的方式进行改写：
f ( x ) a n x n a n 1 x n 1 a 1 x a 0
( a n x n 1 a n 1 x n 2 a 1 ) x a 0
3
问题1：怎样求多项式f(x)=x5+x4+x3+x2+x+1
当x=5时的值？并写出程序.
算法1：因为f(x)=x5+x4+x3+x2+x+1
所以ｆ(5)=5５＋5４＋5３＋5２＋5＋1
=3125＋625＋125＋25＋5＋1
= 3906 一共做了多少次乘法运算和多少次加法运算？
上述算法一共做了1+2+3+4=10次乘法运算， 5次加法运算.优点是简单易懂，但计算效率不高.
然后由内向外逐层计算一次多项式的值,即
v0=2 v1=v0x-5=2×5-5=5
v2=v1x-4=5×5-4=21
v3=v2x+3=21×5+3=108
v4=v3x-6=108×5-6=534 所以,当x=5时,多 V5=v4x+7=534×5+7=2677 项式的值是2677.
11
例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.
的值.
注:对于一个n次多项式: 秦九韶算法把运算的次数由最多1+ 2+3+…+n=n(n+1)/2次乘法和 n次加法的运算,减少为最多只需做 n次乘法和n次加法运算,大大提高了运算效率.
10
例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.
解法一:首先将原多项式改写成如下形式 : f(x)=((((2x-5)x-4)x+3)x-6)x+7
v2=v1x+an-2, v3=v2x+an-3, ……, vn=vn-1x+a0.
这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.
9
特点：通过一次式的反复计算，逐步得出
高次多项式 f ( x ) a n x n a n 1 x n 1 a 1 x a 0
一般地,对于一个n次多项式 f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0. 我们可以改写成如下形式:
f(x)=(…(anx+an-1)x+an-2)x+…+a1)x+a0. 求多项式的值时,首先计算最内层括号内一次多项式的值,即 v1=anx+an-1, 然后由内向外逐层计算一次多项式的值,即
( a n x n 2 ( a n 1 x n 3 a 2 ) x a 1 ) x a 0
( ( a n x a n 1 ) x a n 2 ) x a 1 ) x a 0
7
f ( x ) ( ( a n x a n 1 ) x a n 2 ) x a 1 ) x a 0
案例2 秦九韶算法
1
复习
1、求两个数的最大公约数的两种方法分别是 ___辗__转_相__除_法___和__更__相_减__损__术__
2.两个数21672，8127的最大公约数是（ A ）
A. 2709 B. 2606 C. 2703 D. 2706
3.用更相减损术求140和80的最大公约数是（D ）
要求多项式的值，应该先算最内层的一次多项式的
值，即 v0 an
v1a nxa n 1
然后，由内到外逐层计算一次多项式的值，即
v2 v 1 x a n 2 v 3 v 2x a n 3
vnvn 1 x a 0
最后的一项是什么？
这种将求一个n次多项式f(x)的值转化成求n个
一次多项式的值的方法，称为秦九韶算法。 8
共做了4次乘法运算，5次加法运算。
5
问题2：能否探索一个算法,来解决任意多项式的 f(求x)值=2问x5题-5?x4-4x3+3x2-6x+7v0=2
=(2x4-5x3-4x2+3x-6)x+7 v1=v0x-5=2×5-5=5
=((2x3-5x2-4x+3)x-6)x+7 v2=v1x-4=5×5-4=21

1.3算法案例—(2)秦九韶算法ppt课件

合集下载