算法初步ppt课件.ppt

《算法初步ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法初步ppt课件.ppt（100页珍藏版）》请在三一办公上搜索。

1、1.1算法与程序框图,1.1.1算法的概念,先去括号,再乘除,后加减,1、,什么是算法呢？,要把大象装冰箱，分几步？,答：分三步：,第一步：打开冰箱门,第二步：把大象装冰箱,第三步：关上冰箱门,问：,简单地说，算法就是解决问题的程序或步骤。,什么是算法呢？,第一步,第二步,第三步,（消元）,（解一元一次方程）,+2，得 ,解得,（代入求解）,将 代入,得,写一写,写出解第二个方程组的算法：,第一步,第二步,第三步,解，得 ,将代入得,变一变,在数学上，通常是按照一定规则解决某一类问题的明确有限的步骤。,算法的定义：,例1,(1)设计一个算法,判断7是否为质数;,(2)设计一个算法,判断35是否

2、为质数.,算法:,探究,你能写出”判断整数n(n2)是否为质数”的算法吗?,第一步,给定大于2的整数n.,第二步,令i=2.,算法的基本特点,1、有穷性,一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。,2、确定性,算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。,3、逻辑性,算法中从开始的“第一步”到“最后一步”之间做到环环相扣，分工明确，“前一步”是“后一步”的前提，“后一步”是“前一步”的继续。,算法1：,第二步：计算10150；,第三步：写出运算结果,算法2：,第一步：取n=100；,第二步：计算,第三步：写出运算结果,写出求1+2+3+

3、+100的一个算法,(1+100)+(2+99)+ +(50+51)；,第一步：将原式变形为,你会了吗？,2.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,第一步:输入任意一个正实数r0；,第二步:计算圆的面积: S=r2;,第三步:输出圆的面积S.,1.1.2程序框图,程序框图,程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形。,在程序框图中，一个或几个程序框的组合表示算法中的一个步骤；带有方向箭头的流程线将程序框连接起来，表示算法步骤的执行顺序。,例 用程序框图表示“判断整数n（n2）是否为质数”的算法,设n是一个大于2的整数.,一般用i=i+1表示.,

4、i=i+1,说明:i表示从2(n-1)的所有正整数,用以判断例1步骤2是否终止,i是一个计数变量,有了这个变量,算法才能依次执行.逐步考察从2(n-1)的所有正整数中是否有n的因数存在.,画程序框图的规则,（1）使用标准的图形符号。,（2）框图一般按从上到下，从左到右的方向画。,（3）除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。,（4）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且又且仅有两个结果；另一类是多分支判断，有几种不同的结果。,（5）在图形符号内描述的语言要非常简练清楚。,算法的基本逻辑结构,顺序结构,用程序框图来表示算法，

5、有三种不同的基本逻辑结构：,条件结构,循环结构,三种基本结构（表示一个良好算法的基本单元）,顺序结构,条件结构（选择结构）,循环结构,While（当型）循环,Until（直到型）循环,顺序结构,顺序结构是由若干个依次执行的步骤组成的。这是任何一个算法都离不开的基本结构,例1 已知一个三角形的三边边长分别为a、b、c，利用海伦-秦九韶公式设计一个算法，求出它的面积，画出它的程序框图.,程序框图,习题1 设计一算法：输入圆的半径,输出圆的面积，并画出流程图,算法分析：,第一步：输入圆的半径,第二步：利用公式“圆的面积=圆周率（半径的平方）”计算圆的面积；,第三步：输出圆的面积。,思考：整个程序框图

6、有什么特点？,条件结构（选择结构）,算法的流程根据条件是否成立有不同的流向。条件结构就是处理这种过程的结构。,例2 任意给定3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在.画出这个算法的程序框图.,解：算法如下。S1 输入xS2 若x为奇数，则输出A=3x+2；否则输出A=5x S3 算法结束。,习题2 设x为一个正整数，规定如下运算：若x为奇数，则求3x+2；若x为偶数，则为5x，写出算法，并画出程序框图。,循环结构,在一些算法中，从否处开始，按照一定条件，反复执行某一处理步骤的情况，这就是循环结构。反复执行的处理步骤称为循环体。,在循环结构中，通常都有一个起到循环计

7、数作用的变量，这个变量的取值一般都含在执行或中止循环体的条件中。,例3 设计一个计算1+2+3+100的值的算法，并画出程序框图。,算法分析：需要一个累加变量和一个计数变量，将累加变量的初始值设为0，计数变量的值可以从1到100.,1.2,基本算法语句,第一章 算法初步,【探究新知】我们知道，顺序结构是任何一个算法都离不开的基本结构。,输入、输出语句和赋值语句基本上对应于算法中的顺序结构.,计算机从上而下按照语句排列的顺序执行这些语句.,输入语句和输出语句分别用来实现算法的输入信息,输出结果的功能.,(如右图),输入语句和输出语句分别用来实现算法的输入信息，输出结果的功能。,例1 用描点法作函

8、数yx33x224x30的图象时,需要求出自变量和函数的一组对应值.编写程序,分别计算当 x5，4，3，2，1，0，1，2，3，4，5时的函数值.,INPUT “x=”;x y=x3+3*x2-24*x+30PRINT xPRINT yEND,程序:,-输入语句,-赋值语句,-打印语句,-打印语句,-表示结束,输出语句,输出语句,一.输入语句,INPUT “提示内容”；变量,输入语句的一般格式,说明:(1)输入语句的作用是实现算法的输入信息功能；(2)“提示内容”提示用户输入什么样的信息，变量是指程序在运行时其值是可以变化的量；(3)输入语句要求输入的值只能是具体的常数，不能是函数、变量或表达

9、式；(4)提示内容与变量之间用分号“；”隔开，若输入多个变量，变量与变量之间用逗号“，”隔开.,例如,输入一个学生数学,语文,英语三门课的成绩,可以写成：,INPUT “数学，语文，英语”；a，b，c,注意:INPUT语句不但可以给单个变量赋值,还可以给多个变量赋值,其格式为：,INPUT “提示内容1，提示内容2，提示内容3，”；变量1，变量2，变量3，,练一练:请你用输入语句表达课本P5和P9页程序框图中输入框中的内容.,P7页:,INPUT “n=”; n,P9页:,INPUT a, b, c,二.输出语句,PRINT “提示内容”；表达式,说明:(1)“提示内容”提示用户输出什么样的信

10、息,表达式是指程序要输出的数据；,输出常量，变量的值和字符串等系统信息。输出数值计算的结果。,(2)输出语句的用途：,输出语句的一般格式,(3)同输入语句一样，表达式前也可以有“提示内容”.,思考:在课本P7页图1.1-2程序框图中的输出框的内容怎样用输出语句来表达？,参考答案：输出框： PRINT “n is a prime number .” PRINT “n is not a prime number.”,PRINT “S=”; S,三.赋值语句,(1)赋值语句的一般格式:,变量表达式,(2)赋值语句的作用是:先计算出赋值号右边表达式的值,然后把这个值赋给左边的变量,使该变量的值等于表达

11、式的值。(3)赋值语句中的“”称作赋值号,与数学中的等号的意义是不同的.赋值号的左右两边不能对换.(4)赋值语句左边只能是变量名字而不是表达式,如:2=x是错误的;右边表达式可以是一个数据、常量或算式；不能利用赋值语句进行代数式的演算。（如化简、因式分解、解方程等） （5）对于一个变量可以多次赋值。,【例题解析】例2：编写程序，计算一个学生数学、语文、英语三门课的平均成绩。,分析：先写出算法，画出程序框图，再进行编程。,结束,程序框图,INPUT “Maths,Chinese,English”；a,b,cy=(a+b+c)/3PRINT “y=”；y END,程序:,例3：给一个变量重复赋值。

12、,程序:,A=10A=A+15PRINT AEND,A的输出值是多少?,分析:此程序给变量A赋了两次值.A的初值为10,第二次赋值后,初值被“覆盖”,A的值变为25,因此输出值是25.,变式引申:在此程序的基础上，设计一个程序，要求最后A的输出值是30.,A=10A=A+15PRINT AA=A+5PRINT AEND,程序:,例3：给一个变量重复赋值。,程序:,A=10A=A+15PRINT AEND,例4交换两个变量A和B的值,并输出交换前后 的值。,分析：引入一个中间变量X,将A的值赋予X,又将B的值赋予A，再将X的值赋予B，从而达到交换A，B的值.（比如交换装满水的两个水桶里的水需要再

13、找一个空桶）,INPUT AINPUT BPRINT A，BX=AA=BB=XPRINT A，BEND,程序:,不能!,练习1:编写一个程序,要求输入一个圆的半径,便能输出该圆的周长和面积.（ 取3.14）,分析:设圆的半径为R,则圆的周长C=2R,面积S=R2,可以利用顺序结构中的INPUT语句,PRINT语句和赋值语句设计程序。,INPUT “R=”；RC=2*3.14*RS=3.14*R2PRINT “C=”；CPRINT “S=”； S END,算法中的条件结构是由条件语句来表达的,条件语句是处理条件分支逻辑结构的算法语句 .,条件语句的一般格式,只含一个“分支”的条件结构,写成条件语

14、句为,当计算机执行这种形式的条件语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句体，否则执行END IF之后的语句.,含两个“分支”的条件结构,写成条件语句为,当计算机执行上述语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句体1，否则执行ELSE后的语句体2.,条件语句的作用 在程序执行过程中，根据判断是否满足约定的条件而决定是否需要转换到何处去。需要计算机按条件进行分析、比较、判断，并按判断后的不同情况进行不同的处理。,1、编写一个程序，求任意实数的绝对值。,程序如下：,程序框图：,开始,y=-x,y=x,输出 y,结束,x0?,是,否,【例题

15、解析】,【例题解析】,例6：编写程序，输入一元二次方程ax2+bx+c=0的系数，输出它的实数根。,算法分析:,一元二次方程的根有三种不同情况:,设判别式=b2-4ac,(1)当0时,一元二次方程有两个不等的实数根.,(2)当=0时,一元二次方程有两个相等的实数根.,(3)当0时,一元二次方程没有实数根.,【程序】,INPUT “ a，b，c =”;a，b，c d=b*b-4*a*c IF d=0 THEN p=-b/(2*a) q=SQR(d)/(2*a)IF d=0 THEN PRINT “One real root:”；pELSE x1=p+q x2=p-q PRINT “Two rea

16、l roots:“；x1,x2 END IFELSE PRINT “No real root!”END IFEND,例7：编写程序，使得任意输入的3个整数按从大到小的顺序输出。,算法分析：用a，b，c表示输入的3个整数；为了节约变量，把它们重新排列后，仍用a，b，c表示，并使abc.具体操作步骤如下。第一步：输入3个整数a，b，c.第二步：将a与b比较，并把小者赋给b，大者赋给a.第三步：将a与c比较. 并把小者赋给c，大者赋给a，此时a已是三者中最大的。第四步：将b与c比较，并把小者赋给c，大者赋给b，此时a，b，c已按从大到小的顺序排列好。第五步：按顺序输出a，b，c.,【程序】,INPU

17、T “a，b，c =”;a，b，cIF ba THEN t=a a=b b=tEND IFIF ca THEN t=a a=c c=tEND IF,IF cb THEN t=b b=c c=tEND IF PRINT a，b，cEND,算法中的循环结构是由循环语句来实现的 .,循环结构有两种-当型与直到型.,当型循环结构(当条件满足时反复执行循环体),直到型循环结构(反复执行循环体直到条件满足),对应于程序框图中的两种循环结构，一般程序设计语言中也有当型（WHILE型）和直到型（UNTIL型）两种语句结构。,即WHILE语句和UNTIL语句。,(1)WHILE语句的一般格式是:,WHILE 条

18、件 循环体WEND,其中循环体是由计算机反复执行的一组语句构成的。WHLIE后面的“条件”是用于控制计算机执行循环体或跳出循环体的。,WHILE当 时候,WEND朝方向 行走,(1)WHILE语句的一般格式是,WHILE 条件 循环体WEND,当计算机遇到WHILE语句时,先判断条件的真假,如果条件符合,就执行WHILE与WEND之间的循环体;然后再检查上述条件,如果条件仍符合,再次执行循环体,这个过程反复进行,直到某一次条件不符合为止.这时,计算机将不执行循环体,直接跳到WEND语句后,接着执行WEND之后的语句.,(2)UNTIL语句的一般格式是:,DO 循环体LOOP UNTIL 条件,

19、DO做什么,LOOP UNTIL绕环回线走,直到达到某种 条件为止,思考:参照其直到型循环结构对应的程序框图,说说计算机是按怎样的顺序执行UNTIL语句的？,(2)UNTIL语句的一般格式是:,DO 循环体LOOP UNTIL 条件,从UNTIL型循环结构分析,计算机执行该语句时,先执行一次循环体,然后进行条件的判断,如果条件不满足,继续返回执行循环体,然后再进行条件的判断,这个过程反复进行,直到某一次条件满足时,不再执行循环体,跳到LOOP UNTIL语句后执行其他语句,是先执行循环体后进行条件判断的循环语句.,提问:通过对照,大家觉得WHILE型语句与UNTIL型语句之间有什么区别呢？,区

20、别：在WHILE语句中,是当条件满足时执行循环体,而在UNTIL语句中,是当条件不满足时执行循环体。,例1.编写程序,计算自然数1+2+3+99+100的和.,分析:这是一个累加问题.我们可以用WHILE型语句,也可以用UNTIL型语句。,i=1S=0,WHLIE i=100,S=S+i,i=i+1,WEND,PRINT S,END,i=1S=0,DO,S=S+ii=i+1,LOOP UNTIL,i100,PRINT S,END,变式训练(1):编写程序求:n!=12345n的值.,如何修改?,WHILE语句,i=1S=0,WHLIE i=100,S=S+i,i=i+1,WEND,PRINT

21、S,END,INPUT “n=”;n,S=1,S=Si,in?,S=1,n,S=Si,变式训练(2):编写程序求:1357101的值.,如何修改?,UNITL语句,i=1S=0,DO,S=S+i,i=i+1,LOOP UNTIL i100,PRINT S,END,S=1,101,S=Si,i=i+2,直到型,S=1,S=Si,i=i+2,i101?,算法案例,1.3,辗转相除法更相减损术,1.1.1,1、求两个正整数的最大公约数,（1）求25和35的最大公约数（2）求225和135的最大公约数,2、求8251和6105的最大公约数,所以，25和35的最大公约数为5,所以，225和135的最大公

22、约数为533=45,课前复习,3,15,9,知识回顾：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来,3,3,5,辗转相除法（欧几里得算法）,观察用辗转相除法求8251和6105的最大公约数的过程,第一步 用两数中较大的数除以较小的数，求得商和余数8251=61051+2146,结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。,第二步 对6105和2146重复第一步的做法6105=21462+1813同理6105和2146的最大公约数也是2146和1813的最

23、大公约数。,思考：从上述的过程你体会到了什么？,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例2 用辗转相除法求225和135的最大公约数,225=1351+90,135=901+45,90=452,显然37是148和37的最大公约数，也就是8251和6105的最大公约数,显然45是90和45的最大公约数，也就是225和135的最大公约数,思考1：从上面的两个例子可以看出计算的规律是什么？,S1：用大数除以小数,S2：除数变成被除数，余数变成除数,S3：重复S1

24、，直到余数为0,第一步,给定两个正数m、n第二步,计算m除以n所得到余数r第三步,m=n；n=r第四步,若r=0,则m、n的最大公约数等于m;否则返回第二步,辗转相除法求最大公约数算法：,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。,否,开始,输入两个正数m,n,mn?,r=m MOD n,r0?,输出n,结束,m=x,m=n,n=r,否,是,是,x=n,n=m,更相减损术,算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是，则执行第二步。,第二步：以

25、较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。,例1、用更相减损术求98与63的最大公约数.,解：由于63不是偶数，把98和63以大数减小数，并辗转相减，,即：986335; 633528; 35287; 28721; 21714; 1477.,所以，98与63的最大公约数是7。,二者算理相似，有异曲同工之妙1、都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。2、

26、从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到（差为0）,辗转相除法与更相减损术的区别,秦九韶算法,1.3.2,问题1设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算法,并写出程序.,点评:上述算法一共做了15次乘法运算,5次加法运算.优点是简单,易懂;缺点是不通用,不能解决任意多项多求值问题,而且计算效率不高.,这析计算上述多项式的值,一共需要9次乘法运算,5次加法运算.,问题2有没有更高效的算法?,分析:计算x的幂时,可以利用前面的计算结果,以减少计算量,即先计算x2,然后依次计算,的值.,第二种做法与第一种

27、做法相比,乘法的运算次数减少了,因而能提高运算效率.而且对于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快地得到结果.,问题3能否探索更好的算法,来解决任意多项式的求值问题?,f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7,v0=2v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=

28、5345+7=2677,这种求多项式值的方法就叫秦九韶算法.,f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.,我们可以改写成如下形式:,求多项式的值时,首先计算最内层括号内一次多项式的值,即,v1=anx+an-1,然后由内向外逐层计算一次多项式的值,即,一般地,对于一个n次多项式,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.这种算法称为秦九韶算法.,f(x)=(anx+an-1)x+an-2)x+a1)x+a0.,秦九韶算法,点评:秦九韶算法是求一元多项式的值的一种方法.它的

29、特点是:把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率.,v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.,观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1的值.,若令v0=an,得,这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现.,问题画出程序框图,表示用秦九韶算法求5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0 (x0是任意实数)时的值的过程,然后

30、写出程序.,算法步骤如下：第一步，输入多项式次数n、最高次项的系数an和x的值.第二步，将v的值初始化为an，将i的值初始化为n-1.第三步，输入i次项的系数ai.第四步，v=vx+ai，i=i-1.第五步，判断i是否大于或等于0，若是，则返回第三步；否则，输出多项式的值v.,否,程序框图,开始,输入n,an,x的值,i0?,i=n-1,v=an,v=vx+ai,i=i-1,输出v,结束,是,输入ai,进位制,1.3.3,问题1我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制.那么什么是进位制?不同的进位制之间又有什

31、么联系呢?,进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制;满十进一,就是十进制;满十六进一,就是十六进制;等等.,“满几进一”,就是几进制,几进制的基数就是几.,可使用数字符号的个数称为基数.基数都是大于1的整数.,例如：二进制可使用的数字有0和1,基数是2; 十进制可使用的数字有0,1,2,8,9等十个数字,基数是10; 十六进制可使用的数字或符号有09等10个数字以及AF等6个字母(规定字母AF对应1015),十六进制的基数是16.,注意:为了区分不同的进位制,常在数字的右下脚标明基数,.,如111001(2)表示二进制数,34(5)表示5进制数.,十进制

32、数一般不标注基数.,问题2十进制数3721中的3表示3个千,7表示7个百,2表示2个十,1表示1个一,从而它可以写成下面的形式:,3721=3103+7102+2101+1100.,想一想二进制数1011(2)可以类似的写成什么形式?,1011(2)=123+022+121+120.,同理:,3421(5)=353+452+251+150.,C7A16(16)=12164+7163+10162 +1161+6160.,一般地,若k是一个大于1的整数,那么以k为基数的k进制数可以表示为一串数字连写在一起的形式,anan-1a1a0(k) (0ank,0an-1,a1,a0k),意思是:(1)第一

33、个数字an不能等于0;(2)每一个数字an,an-1,a1,a0都须小于k.,k进制的数也可以表示成不同位上数字与基数k的幂的乘积之和的形式,即,anan-1a1a0(k)=ankn+an-1kn-1 +a1k1+a0k0 .,注意这是一个n+1位数.,问题3二进制只用0和1两个数字,这正好与电路的通和断两种状态相对应,因此计算机内部都使用二进制.计算机在进行数的运算时,先把接受到的数转化成二进制数进行运算,再把运算结果转化为十进制数输出.那么二进制数与十进制数之间是如何转化的呢?,例1:把二进制数110011(2)化为十进制数.,分析:先把二进制数写成不同位上数字与2的幂的乘积之和的形式,再

34、按照十进制数的运算规则计算出结果.,解:110011(2)=125+124+023+022+121+120=132+116+12+1=51.,问题4你会把三进制数10221(3)化为十进制数吗?,解:10221(3)=134+033+232+231+130 =81+18+6+1=106.,总结： k进制数转化为十进制数的方法,先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式,即,anan-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0 .,再按照十进制数的运算规则计算出结果.,例 设计一个算法,把k进制数a(共有n位)化为十进制数b.,算法步骤如下:,开始,输入a

35、,k,n,b=0,i=1,把a的右数第i位数字赋给t,i=i+1,in?,输出b,结束,否,是,INPUT a,k,ni=1b=0t=a MOD 10DO b=b+t*k(i-1) a=a10 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND,程序:,程序框图：,输入a,k,n,例2:把89化为二进制的数.,分析:把89化为二进制的数,需将89先写成如下形式,89=an2n+an-12n-1+a121+a020 .,89=64+16+8+1=126+025+124 +123+022+021+120 =1011001(2).,但如果数太大,我们是无法这样凑出来的,怎

36、么办?,89=442+1,44=222+0,22=112+0,11=52+1,5=22+1,2=12+0,1=02+1,89=442+1,44=222+0,22=112+0,11=52+1,5=22+1,89=442+1, =(222+0)2+1 =(112+0)2+0)2+1 =(52+1)2+0)2+0)2+1 =(22+1)2+1)2+0) 2+0)2+1 =(12)+0)2+1)2+1)2+0) 2+0)2+1,=126+025+124 +123+022+021+120=1011001(2).,可以用2连续去除89或所得商(一直到商为0为止),然后取余数-除2取余法.,2=12+0,1

37、=02+1,44 1,例2:把89化为二进制的数.,我们可以用下面的除法算式表示除2取余法:,22 0,11 0,5 1,2 1,1 0,0 1,把算式中各步所得的余数从下到上排列,得到,89=1011001(2).,这种方法也可以推广为把十进制数化为k进制数的算法,称为除k取余法.,解:以5作为除数,相应的除法算式为:,17 4,3 2,0 3, 89=324(5).,例3:把89化为五进制的数.,问题5你会把三进制数10221(3)化为二进制数吗?,解:第一步:先把三进制数化为十进制数:10221(3)=134+033+232+231+130 =81+18+6+1=106.,第二步:再把十

38、进制数化为二进制数:,106=1101010(2).,例 设计一个程序，实现“除k取余法”（kN，2k9）,第一步：给定的十进制正整数a和转化后的数的基数k第二步：求出a除以k所得的商q，余数r.第三步：把得到的余数依次从右到左排列.第四步：若q0，则a=q，返回第二步；否则，输出全部余数r排列得到的k进制数.,程序框图：,开始,输入a,k,求a除以k的商q,求a除以k的余数r,a=q,q=0?,输出全部余数r排列得到的k进制数,结束,把得到的余数依次从右到左排列,是,否,INPUT “a,k=”;a,kb=0i=0DO q=ak r=a MOD k b=b+r*10i i=i+1 a=qLOOP UNTIL q=0PRINT bEND,程序:,例 设计一个程序,实现“除k取余法”.,