课件15张PPT。案例3 进位制算法案例一、进位制1、什么是进位制？最常用的是十进制数，我们约定满十进一。满二进一，就是二进制，满十二进一，就是十二进制。满几进一就是几进制。 进位制是人们为了计数和运算方便而约定的记数系统。 进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。
比如时间和角度的单位用六十进位制, 计算“一打”数值时是12进制的。
电子计算机用的是二进制 3、我们了解十进制吗？所谓的十进制，它是如何构成的？十进制由两个部分构成例如：3721其它进位制的数又是如何的呢？(用10个数字来记数，称基数为10)二、 二进制二进制是用0、1两个数字来描述的．如11001二进制的表示方法区分的写法：11001（2）或者(11001)2八进制呢？如7342(8)k进制呢？anan-1an-2…a1(k)？表示成不同位上数字与基数的幂的乘积之和的形式。三、二进制与十进制的转换1、二进制数转化为十进制数例1 将二进制数110011(2)化成十进制数解：根据进位制的定义可知所以，110011（2）=51． 设计一个将k进制数a转换为十进制数(共有 n位)的程序开始结束输入a,k,nb=0 i=1把a的右数第i位数字赋给tb=b+t·k i－1i=i+1i>n?输出b是否INPUT “a,k,n=”;a,k,n
b=0
i=1
t= a MOD 10
DO
b=b+t*k^(i-1)
a=a10
t=a MOD 10
i=i+1
LOOP UNTIL i>n
PRINT b
END开始结束输入a,k,nb=0 i=1把a的右数第i位数字赋给tb=b+t·k i－1i=i+1i>n?输出b是否根据逢二进一的原则：用2连续去除89或所得的商，然后取余数)例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)+15＝ 2× 2＋1＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋189＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20所以：89=1011001（2）＝2×（2×（2×（23＋2＋1）＋0）＋0）＋1＝2×（2×（24＋22＋2＋0）＋0）＋1＝2×（25＋23+22＋0＋0）＋1＝26＋24+23＋0＋0＋2089＝2×44＋144＝ 2×22＋022＝ 2×11＋011＝ 2× 5＋1＝ 2× (2× (2× (2× (2× 2＋1)+1)+0)+0)+1所以89＝2×（2×（2×（2×（2 × 2 ＋1）＋1）＋0）＋0）＋12、十进制转换为二进制除二取余法注意：
1.最后一步商为0，
2.将上式各步所得的余数从下到上排列，得到：
89=1011001（2）2、十进制转换为二进制例2 把89化为二进制数522212010余数11224489222201101例3 把89化为五进制数3、十进制转换为其它进制解：根据除k取余法以5作为除数，相应的除法算式为：所以，89=324（5）练习：
完成下列进位制之间的转化：
（1）10231（4）= （10）；
（2）235（7）= （10）；
（3）137（10）= （6）；
（4）1231（5）= （7）；
（5）213（4）= （3）；
（6）1010111（2）= （4）。3013451113 设计一个将十进制数a转换为k进制数的程序开始结束输入a,k求a除以k的商qa=qq=0?输出b是否求a除以k的余数r把得到的余数从右到左排列得b 能写出它的程序吗?1．进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为k，即可称k进位制，简称k进制。k进制需要使用k个数字；2．十进制与二进制之间转换的方法；
先把这个k进制数写成用各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果。小结3．十进制数转化为k进制数的方法：（除k取余法）
用k连续去除该十进制数或所得的商，直到商为零为止，然后把每次所得的余数倒着排成一个数，就是相应的k进制数。课件15张PPT。案例1 辗转相除法与更相减损术算法案例1. 回顾算法的三种表述：自然语言程序框图程序语言（三种逻辑结构）（五种基本语句）2. 思考： 小学学过的求两个数最大公约数的方法？ 先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.1、求两个正整数的最大公约数（1）求25和35的最大公约数
（2）求18和30的最大公约数所以，25和35的最大公约数为5所以，18和30的最大公约数为62、除了用这种方法外还有没有其它方法？算出8256和6105的最大公约数. 335辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105的最大公约数的过程 第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146 结论： 8251和6105的公约数就是6105和2146的公约数，反之也成立。求8251和6105的最大公约数，只要求出6105和2146的最大公约数就可以了。第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。 为什么呢？思考：从上述的过程你体会到了什么？完整的过程8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2 用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2显然37是148和37的最大公约数，也就是8251和6105的最大公约数 显然45是90和45的最大公约数，也就是225和135的最大公约数 思考1：从上面的两个例子可以看出计算的规律是什么？ S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。m = n × q ＋ r用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否思考2：辗转相除法中的关键步骤是哪种逻辑结构？ 输出m1、辗转相除法（欧几里得算法）（1）算理：
所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。（2）算法步骤第一步：输入两个正整数m,n(m>n).
第二步：计算m除以n所得的余数r.
第三步：m=n, n=r.
第四步：若r＝0,则m,n的最大公约数等于m；
否则转到第二步.
第五步：输出最大公约数m.（3）程序框图（4）程序开始输入m,n r=m MOD n m=nr=0?是否 n=r 输出m结束 INPUT “m,n=“;m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END《九章算术》——更相减损术 算理：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个数或这个数与约简数的乘积就是所求的最大公约数。例3 用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并辗转相减 98－63=35
63－35 =28
35－28＝7
28－7＝21
21－7＝14
14－7＝7所以，98和63的最大公约数等于7 先约简，再求21与18的最大公约数,然后乘以两次约简的质因数4 你能根据“更相减损术”设计程序,求两个正整数的最大公约数吗? 思考?例3、求324、243、135这三个数的最大公约数。思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到小结课件13张PPT。案例2 秦九韶算法案例2、秦九韶算法问题怎样求多项式 f(x)=x5+x4+x3+x2+x+1当x=5时的值呢 ？计算多项式 f(x)=x5+x4+x3+x2+x+1 当x = 5的值算法1：因为 f(x)=x5+x4+x3+x2+x+1 所以f(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１= 3906算法2：f(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次加法运算。= 3906《数书九章》——秦九韶算法对该多项式按下面的方式进行改写：思考：当知道了x的值后该如何求多项式的值？这是怎样的一种改写方式？最后的结果是什么？要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法，称为秦九韶算法。思考：在求多项式的值上，这是怎样的一个转化？例 已知一个五次多项式为用秦九韶算法求这个多项式当x = 5的值。解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x = 5时的值：所以，当x = 5时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？算法步骤：第一步：输入多项式次数n、最高次项的系数an和x的值.第二步：将v的值初始化为an，将i的值初始化为n-1.第三步：输入 i 次项的系数ai第四步：v=vx+ai , i=i-1.第五步：判断i是否大于或等于0，若是，则返回第三步；否则，输出多项式的值v。程序框图：这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。开始输入n,an,xi>=0?输出v结束 v=vx+aii=i-1是否i=n-1v=anINPUT “n=”;n
INPUT “an=”;a
INPUT “x=”;x
v=a
i=n－1
WHILE i>=0
PRINT “i=”; i
INPUT “ai=”;a
v=v*x+a
i=i－1
WEND
PRINT v
END特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。练习、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1
用秦九韶算法求这个多项式当x=-2时的值。程序框图：这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现。课堂小结：
1、秦九韶算法的方法和步骤
2、秦九韶算法的程序框图
