秦九韶算法与进位制
图片预览
文档简介
(共16张PPT)
秦九韶算法、进位制
复习
回顾
1、求两个数的最大公约数的两种方法分别是（ ）和（ ）.
2、两个数21672，8127的最大公约数是（ ）
A、2709 B、2606 C、2703 D、2706
问题
怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值？
算法1
ｆ(5)=5５＋5４＋5３＋5２＋5＋１ = 3906
算法2
ｆ(5)=5５＋5４＋5３＋5２＋5＋１
=5×(5４＋5３＋5２＋5＋１ ) ＋１
=5×(5×(5３＋5２＋5 ＋１ )＋１ ) ＋１
=5×(5×(5×(5２+5 +１) +１ ) +１ ) +１
=5×(5×(5×(5 ×(5 +１) +１ )+１)+１) +１
共做了1+2+3+4=10次乘法运算,5次加法运算.
共做了4次乘法运算,5次加法运算.
秦九韶算法
新 课
《数书九章》——秦九韶算法
对该多项式按下面的方式进行改写
设
是一个n 次的多项式
n次加法运算
次乘法运算
要求多项式的值，应该先算最内层的一次多项式的值，即
然后，由内到外逐层计算一次多项式的值，即
这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法
n次加法运算
n次乘法运算
按由里到外的顺序,依此计算一次多项式当x = 5时的值：
所以,x = f(5)=时17255.2
例1 已知一个五次多项式为
用秦九韶算法求这个多项式当x = 5的值.
解：
将多项式变形：
5 2 3.5 -2.6 1.7 -0.8
x=5
27 138.5 689.9 3451.2 17255.2
25 135 692.5 3449.5 17256
第一步：输入多项式次数n、最高次项的系数an和x的值
算法步骤
第二步：将v的值初始化为an,将i的值初始化为n-1
第三步：输入i次项的系数ai
第四步：v=vx+ai,i=i-1.
第五步：判断 ,若是,则返 回第三步;否则,输出多项式的值v.
i大于或等于零
第一步：输入多项式次数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
i≥0？
输出v
输入ai
v=vx+ai
i=i-1
结束
N
Y
一、进位制的由来
人类在长期的生产劳动中创造了数字,为了方便读写和计算,逐渐地产生了进位制.古罗马人采取60进制,玛雅人使用20进制,中国、埃及、印度等国主要采取10进制.而近代由于计算机的诞生,二进制应运而生.
计算机为何采用二进制？
1.二进制只有0和1两个数字,要得到表示两种不同稳定状态的电子器件很容易,而且制造简单,可靠性高.
2.在各种计数中,二进制的算法逻辑简单,有布尔逻辑代数做理论依据,简单的运算规则则使得机器内部的操作也变得简单,如加法法则只有4条：0+0=0,0+1=1,1+0=1,1+1=10,而十进制加法法则从0+0=0到9+9=18需要100条;乘法法则也是这样：0×0=0,0×1=0,1×0=0,1×1=1,十进制的乘法法则要由一张“九九表”来规定,比较复杂.
进位制是人们为了计数和运算方便而约定的记数系统.
进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.“满几进一”就是几进制,几进制的基数就是几.
二、进位制的定义
十进制数 3721 的意义
1.满10进1
2.每个数位上的数字都小于10(基数),取自0,1,2,3,4,5,6,7,
8,9(十个数字),首位不是0.
不同位上的数字与基数的幂的乘积之和的形式
三、进位制的表示方法
二进制逢2进1,使用0和1两个数字
八进制逢8进1,使用0~7两个数字
k进制的数 表示为：
十进制数
四、进位制间的转换
1、二进制数转化为十进制数
例1 (1)将二进制数110011化成十进制数
所以,110011（2）=51．
(2) 将六十进制数52014化成十进制数
k进制的数 转化位十进制数的算法
1.从右到左依次取k进制数各位上的数字,乘以相应k的幂k的幂从0开始取值,每次增加1,递增到n-1
2.把得到的乘积加起来,所得的结果就是相应的十进制数.
算法：教材P41
2、十进制数转化为二进制数
例2 把89化为二进制数
89＝2×44＋1
＝2×(2×22＋0)+1
＝2×(2×(2×11＋0)+0)+1
＝2×(2×(2×(2×5＋1)+0)+0)+1
所以：89=1011001（2）
＝1×26＋0×25+1×24+1×23＋0×22＋0×21＋1×20
＝2×(2×(2×(2×(2×2＋1)+1)+0)+0)+1
＝2×(2×(2×(2×(2×(2×1+0)＋1)+1)+0)+0)+1
1.最后一步商为0
2.将上式各步所得的余数从下到上排列,得到:89=1011001（2）
5
2
2
2
1
2
0
1
0
余数
11
22
44
89
2
2
2
2
0
1
1
0
1
除2取余法
作业：学法第 9、10 课时
练习：教材P45 T2、T3
秦九韶算法、进位制
复习
回顾
1、求两个数的最大公约数的两种方法分别是（ ）和（ ）.
2、两个数21672，8127的最大公约数是（ ）
A、2709 B、2606 C、2703 D、2706
问题
怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值？
算法1
ｆ(5)=5５＋5４＋5３＋5２＋5＋１ = 3906
算法2
ｆ(5)=5５＋5４＋5３＋5２＋5＋１
=5×(5４＋5３＋5２＋5＋１ ) ＋１
=5×(5×(5３＋5２＋5 ＋１ )＋１ ) ＋１
=5×(5×(5×(5２+5 +１) +１ ) +１ ) +１
=5×(5×(5×(5 ×(5 +１) +１ )+１)+１) +１
共做了1+2+3+4=10次乘法运算,5次加法运算.
共做了4次乘法运算,5次加法运算.
秦九韶算法
新 课
《数书九章》——秦九韶算法
对该多项式按下面的方式进行改写
设
是一个n 次的多项式
n次加法运算
次乘法运算
要求多项式的值，应该先算最内层的一次多项式的值，即
然后，由内到外逐层计算一次多项式的值，即
这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法
n次加法运算
n次乘法运算
按由里到外的顺序,依此计算一次多项式当x = 5时的值：
所以,x = f(5)=时17255.2
例1 已知一个五次多项式为
用秦九韶算法求这个多项式当x = 5的值.
解：
将多项式变形：
5 2 3.5 -2.6 1.7 -0.8
x=5
27 138.5 689.9 3451.2 17255.2
25 135 692.5 3449.5 17256
第一步：输入多项式次数n、最高次项的系数an和x的值
算法步骤
第二步：将v的值初始化为an,将i的值初始化为n-1
第三步：输入i次项的系数ai
第四步：v=vx+ai,i=i-1.
第五步：判断 ,若是,则返 回第三步;否则,输出多项式的值v.
i大于或等于零
第一步：输入多项式次数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
i≥0？
输出v
输入ai
v=vx+ai
i=i-1
结束
N
Y
一、进位制的由来
人类在长期的生产劳动中创造了数字,为了方便读写和计算,逐渐地产生了进位制.古罗马人采取60进制,玛雅人使用20进制,中国、埃及、印度等国主要采取10进制.而近代由于计算机的诞生,二进制应运而生.
计算机为何采用二进制？
1.二进制只有0和1两个数字,要得到表示两种不同稳定状态的电子器件很容易,而且制造简单,可靠性高.
2.在各种计数中,二进制的算法逻辑简单,有布尔逻辑代数做理论依据,简单的运算规则则使得机器内部的操作也变得简单,如加法法则只有4条：0+0=0,0+1=1,1+0=1,1+1=10,而十进制加法法则从0+0=0到9+9=18需要100条;乘法法则也是这样：0×0=0,0×1=0,1×0=0,1×1=1,十进制的乘法法则要由一张“九九表”来规定,比较复杂.
进位制是人们为了计数和运算方便而约定的记数系统.
进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.“满几进一”就是几进制,几进制的基数就是几.
二、进位制的定义
十进制数 3721 的意义
1.满10进1
2.每个数位上的数字都小于10(基数),取自0,1,2,3,4,5,6,7,
8,9(十个数字),首位不是0.
不同位上的数字与基数的幂的乘积之和的形式
三、进位制的表示方法
二进制逢2进1,使用0和1两个数字
八进制逢8进1,使用0~7两个数字
k进制的数 表示为：
十进制数
四、进位制间的转换
1、二进制数转化为十进制数
例1 (1)将二进制数110011化成十进制数
所以,110011（2）=51．
(2) 将六十进制数52014化成十进制数
k进制的数 转化位十进制数的算法
1.从右到左依次取k进制数各位上的数字,乘以相应k的幂k的幂从0开始取值,每次增加1,递增到n-1
2.把得到的乘积加起来,所得的结果就是相应的十进制数.
算法：教材P41
2、十进制数转化为二进制数
例2 把89化为二进制数
89＝2×44＋1
＝2×(2×22＋0)+1
＝2×(2×(2×11＋0)+0)+1
＝2×(2×(2×(2×5＋1)+0)+0)+1
所以：89=1011001（2）
＝1×26＋0×25+1×24+1×23＋0×22＋0×21＋1×20
＝2×(2×(2×(2×(2×2＋1)+1)+0)+0)+1
＝2×(2×(2×(2×(2×(2×1+0)＋1)+1)+0)+0)+1
1.最后一步商为0
2.将上式各步所得的余数从下到上排列,得到:89=1011001（2）
5
2
2
2
1
2
0
1
0
余数
11
22
44
89
2
2
2
2
0
1
1
0
1
除2取余法
作业：学法第 9、10 课时
练习：教材P45 T2、T3