秦九韶算法介绍和实例分析

秦九韶算法算法案例第二课时1、求两个数的最大公约数的两种方法分别是（）和（）。2、两个数21672，8127的最大公约数是（）A、2709B、2606C、2703D、2706复习引入:新课讲解:思考怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？计算多项式ｆ(ｘ)

=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x=5的值的算法：算法1：因为ｆ(ｘ)

=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋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：因为ｆ(ｘ)

=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋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次的多项式对该多项式按下面的方式进行改写：思考：当知道了x的值后该如何求多项式的值？这是怎样的一种改写方式？最后的结果是什么？要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。思考：在求多项式的值上，这是怎样的一个转化？

通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。秦九韶算法的特点：例：已知一个五次多项式为用秦九韶算法求这个多项式当x=5的值。解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x=5时的值：所以，当x=5时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？(1)、算法步骤：第一步：输入多项式次数n、最高次项的系数an和x的值.第二步：将v的值初始化为an，将i的值初始化为n-1.第三步：输入i次项的系数an.第四步：v=vx+ai,i=i-1.第五步：判断i是否大于或等于0，若是，则返回第三步；否则，输出多项式的值v。思考：你能设计程序把“秦九韶算法”表示出来吗？案例3进位制[问题1]我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制.那么什么是进位制?不同的进位制之间又有什么联系呢?进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制;满十进一,就是十进制;满十六进一,就是十六进制;等等.“满几进一”,就是几进制,几进制的基数就是几.可使用数字符号的个数称为基数.基数都是大于1的整数.如二进制可使用的数字有0和1,基数是2;十进制可使用的数字有0,1,2,…

,8,9等十个数字,基数是10;

十六进制可使用的数字或符号有0~9等10个数字以及A~F等6个字母(规定字母A~F对应10~15),十六进制的基数是16.注意:为了区分不同的进位制,常在数字的右下脚标明基数.如111001(2)表示二进制数,34(5)表示5进制数.十进制数一般不标注基数.[问题2]十进制数3721中的3表示3个千,7表示7个百,2表示2个十,1表示1个一,从而它可以写成下面的形式:3721=3×103+7×102+2×101+1×100.想一想二进制数1011(2)可以类似的写成什么形式?1011(2)=1×23+0×22+1×21+1×20.同理:3421(5)=3×53+4×52+2×51+1×50.C7A16(16)=12×164+7×163+10×162

+1×161+6×160.一般地,若k是一个大于1的整数,那么以k为基数的k进制数可以表示为一串数字连写在一起的形式anan-1…a1a0(k)(0<an<k,0≤an-1,…,a1,a0<k)意思是:(1)第一个数字an不能等于0;(2)每一个数字an,an-1,…,a1,a0都须小于k.

k进制的数也可以表示成不同位上数字与基数k的幂的乘积之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1

+…+a1×k1+a0×k0.注意这是一个n+1位数.例1:把二进制数110011(2)化为十进制数.

分析:先把二进制数写成不同位上数字与2的幂的乘积之和的形式,再按照十进制数的运算规则计算出结果.解:110011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.[问题4]你会把三进制数10221(3)化为十进制数吗?解:10221(3)=1×34+0×33+2×32+2×31

+1×30=81+18+6+1=106.k进制数转化为十进制数的方法

先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式,即anan-1…a1a0(k)=an×kn+an-1×kn-1+…+a1×k1+a0×k0.再按照十进制数的运算规则计算出结果.例2:把89化为五进制的数.解:以5作为除数,相应的运算式为:174589余数532503∴89=324(5).89=517+4=5(53+2)+4=352+25+4=324(5)

例3:把89化为二进制的数.分析:把89化为二进制的数,需想办法将89先写成如下形式89=an×2n+an-1×2n-1+…+a1×21+a0×20.89=64+16+8+1=1×26+0×25+1×24 +1×23+0×22+0×21+1×20=1011001(2).但如果数太大,我们是无法这样凑出来的,怎么办?89=44×2+1,44=22×2+0,22=11×2+0,11=5×2+1,5=2×2+1,2=1×2+0,1=0×2+1,441例3:把89化为二进制的数.我们可以用下面的除法算式表示除2取余法:289余数22202110251221210201把算式中各步所得的余数从下到上排列,得到89=1011001(2).这种方法也可以推广为把十进制数化为k进制数的算法,称为除k取余法.可以用2连续去除89或所得商(一直到商为0为止),然后取余数---除2取余法.思考你会把三进制数10221