算法初步课件教学内容.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1算法与程序框图,1.1.1算法的概念,先,去括号,再,乘除,后,加减,1,、,什么是算法呢？,要把大象装冰箱，分几步？,答：分三步：,第一步：打开冰箱门,第二步：把大象装冰箱,第三步：关上冰箱门,问：,2,问题,简单地说，算法就是解决问题的程序或步骤。,什么是算法呢？,第一步,第二步,第三步,（消元）,（解一元一次方程）,+2,得,解得,（,代入求解）,将 代入,得,写一写,解方程组,写出,的步骤,写出解第二个方程组的算法：,第一步,第二步,第三步,解，得 ,将代入得,得,变一变,在数学上，通常是按照一定规则解决某一类问题的明确有限的步骤,。,算法的定义：,例,1,(1),设计一个算法,判断,7,是否为质数,;,(1),第一步,用,2,除,7,得到余数,1.,因为余数不为,0,所以,2,不能整除,7.,第二步,用,3,除,7,得到余数,1.,因为余数不为,0,所以,3,不能整除,7.,第三步,用,4,除,7,得到余数,3.,因为余数不为,0,所以,4,不能整除,7.,第四步,用,5,除,7,得到余数,2.,因为余数不为,0,所以,5,不能整除,7.,第五步,用,6,除,7,得到余数,1.,因为余数不为,0,所以,6,不能整除,7.,因此,7,是质数,.,(2),设计一个算法,判断,35,是否为质数,.,算法,:,第一步,用,2,除,35,得到余数,1.,因为余数不为,0,所以,2,不能整除,35.,第二步,用,3,除,35,得到余数,2.,因为余数不为,0,所以,3,不能整除,35.,第三步,用,4,除,35,得到余数,3.,因为余数不为,0,所以,4,不能整除,35.,第四步,用,5,除,35,得到余数,0.,因为余数为,0,所以,5,能整除,35.,因此,35,不是质数,.,探究,你能写出”判断整数n(n2),是否为质数”的算法吗,?,第一步,给定大于,2,的整数,n.,第二步,令,i=2.,第三步,用,i,除,n,得到余数,r.,第四步,判断”,r=0”,是否成立,.,若是,则,n,不是质数,结束算法,;,否则,将,i,的值增加,1,仍用,i,表示,.,第五步,判断”,i(n-1)”,是否成立,.,若是,则,n,是质数,结束算法,;,否则,返回第三步,.,算法的基本特点,1,、有穷性,一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。,2,、确定性,算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。,3,、逻辑性,算法中从开始的“第一步”到“最后一步”之间做到,环环相扣，分工明确，“前一步”是“后一步”的前提，“后一步”是“前一步”的继续。,算法,1,：,第二步,：计算,10150,；,第三步,：写出运算结果,算法,2,：,第一步,：取,n=100,；,第二步,：计算,第三步,：写出运算结果,写出求,1+2+3+100,的一个算法,(1+100)+(2+99)+(50+51),；,第一步,：将原式变形为,你会了吗？,2.,任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积,.,第一步,:,输入任意一个正实数,r0,；,第二步,:,计算圆的面积,:S=,r,2,;,第三步,:,输出圆的面积,S.,1.1.2程序框图,程序框图程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形。,在程序框图中，一个或几个程序框的组合表示算法中的一个步骤；带有方向箭头的流程线将程序框连接起来，表示算法步骤的执行顺序。,图形符号,名称,功能,终端框（起止框）,表示一个算法的起始和结束,输入、输出框,表示一个算法输入和输出的信息,处理框,赋值、计算,判断框,判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”。,流程线,连接程序框,连接点,连接程序框图的两部分,例 用程序框图表示“判断整数n（n2）是否为质数”的算法,开始,输入,n,i=2,求,n,除以,i,的余数,r,i,的值增加,1,仍用,i,表示,in,-1,或r=0?,输出“,n不是质数,”,结束,是,否,是,输出“,n是质数,”,否,r=0?,设,n,是一个大于,2,的整数,.,一般用,i=i+1,表示,.,i=i+1,说明,:i,表示从,2(n-1),的所有正整数,用以判断例,1,步骤,2,是否终止,i,是一个计数变量,有了这个变量,算法才能依次执行,.,逐步考察从,2(n-1),的所有正整数中是否有,n,的因数存在,.,画程序框图的规则,（,1,）使用标准的图形符号。,（,2,）框图一般按从上到下，从左到右的方向画。,（,3,）除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。,（,4,）判断框分两大类，一类判断框“是”与“否”两分支的判断，而且又且仅有两个结果；另一类是多分支判断，有几种不同的结果。,（,5,）在图形符号内描述的语言要非常简练清楚。,算法的基本逻辑结构,开始,输入,n,i=2,求,n,除以,i,的余数,r,i=i+1,in,或,r=0?,n,不是质数,结束,是,否,是,n,是质数,否,r=0?,顺序结构,用程序框图来表示算法，有三种不同的基本逻辑结构：,条件结构,循环结构,三种基本结构（,表示一个良好算法的基本单元,）,顺序结构,条件结构（,选择结构,）,循环结构,A,B,P,A,B,成立,不成立,成立,A,P,不成立,A,P,成立,不成立,While,（,当型,）循环,Until,（,直到型,）循环,顺序结构,顺序结构是由若干个依次执行的步骤组成的。这是任何一个算法都离不开的基本结构,A,B,例,1,已知一个三角形的三边边长分别为a、b、c，利用,海伦,-,秦九韶公式设计一个算法，求出它的面积，画出,它的程序框图,.,第一步：输入三角形三条边的边长,a,，,b,，,c,；,第二步：计算 ；,第三步：计算 ；,第四步：输出,s,。,算法分析：,开始,输入,a,，,b,，,c,输出,S,结束,程序框图,习题,1,设计一算法：,输入圆的半径,输出圆的面积，并画出流程图,算法分析：,第一步：,输入圆的半径,第二步：,利用公式“圆的面积,圆周率,（半径的平方）”计算圆的面积；,第三步：,输出圆的面积。,开始,结束,输入半径,R,计算,S=Pi*R*R,输出面积,S,定义,Pi=3.14,思考：整个程序框图有什么特点？,条件结构（,选择结构,）,算法的流程根据条件是否成立有不同的流向。条件结构就是处理这种过程的结构。,P,A,B,成立,不成立,P,A,不成立,成立,例,2,任意给定,3,个正实数，设计一个算法，判断分别以这,3,个数为三边边长的三角形是否存在,.,画出这个算法的程序框图,.,开始,输入,a,、,b,、,c,a+bc,a+cb,b+ca,是否同时成立,存在这样的三角形,结束,否,是,不存在这样的三角形,解：算法如下。,S1,输入,x,S2,若,x,为奇数，则输出,A=3x+2,；否则输出,A=5x,S3,算法结束。,习题,2,设,x,为一个正整数，规定如下运算：若,x,为奇数，则求,3x+2,；若,x,为偶数，则为,5x,，写出算法，并画出程序框图。,x为奇数？,开始,输入x,A=3x+2,结束,否,是,A=5x,循环结构,A,P,成立,不成立,While,（,当型,）循环,成立,A,P,不成立,Until,（,直到型,）循环,在一些算法中，从否处开始，按照一定条件，反复执行,某一处理步骤的情况，这就是循环结构。反复执行的处,理步骤称为循环体。,在循环结构中，通常都有一个起到循环计数作用的变量，,这个变量的取值一般都含在执行或中止循环体的条件中。,例,3,设计一个计算,1+2+3+100,的值的算法，并画出程序框图。,算法分析：,需要一个累加变量和一个计数变量，将累加变量的初始值,设为,0,，计数变量的值可以从,1,到,100.,i=100?,i=1,开始,输出,sum,结束,否,是,sum=0,i=i+1,sum=sum+1,1.2,基本算法语句,第一章 算法初步,【,探究新知,】,我们知道，顺序结构是任何一个算法都离不开的基本结构。,语句,n+1,语句,n,输入、输出语句和赋值语句基本上对应于算法中的顺序结构,.,计算机从上而下按照语句排列的顺序执行这些语句,.,输入语句和输出语句分别用来实现算法的输入信息,输出结果的功能,.,(,如右图,),输入语句和输出语句分别用来实现算法的输入信息，输出结果的功能。,例,1,用描点法作函数,y,x,3,3,x,2,24,x,30,的图象时,需要求出自变量和函数的一组对应值,.,编写程序,分别计算当,x,5,，,4,，,3,，,2,，,1,，,0,，,1,，,2,，,3,，,4,，,5,时的函数值,.,INPUT,“x=”;x,y=x3+3,*,x2,-,24,*,x,+,30,PRINT,x,PRINT,y,END,程序,:,-,输入语句,-,赋值语句,-,打印语句,-,打印语句,-,表示结束,输出语句,输出语句,一,.,输入语句,INPUT,“,提示内容”；变量,输入语句的一般格式,说明,:,(1),输入语句的作用是实现算法的输入信息功能；,(2)“,提示内容”提示用户输入什么样的信息，,变量是指程序在运行时其值是可以变化的量；,(3),输入语句要求输入的值,只能是具体的常数,，,不能是函数、变量或表达式；,(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)“,提示内容”提示用户输出什么样的信息,表,达式是指程序要输出的数据；,输出常量，变量的值和字符串等系统信息。,输出数值计算的结果。,(2),输出语句的用途：,输出语句的一般格式,(3),同输入语句一样，表达式前也可以有“提示内容”,.,思考,:,在课本,P7,页图,11-2,程序框图中的输出框的内容怎样用输出语句来表达？,参考答案：,输出框：,PRINT “,n is a prime number,.”,PRINT “,n is not a prime number,.”,如,P9,页的输出框 可以转化为输出语句,:,输出,S,PRINT“S=”;S,三,.,赋值语句,(1),赋值语句的一般格式,:,变量表达式,(2),赋值语句的作用,是,:,先计算出赋值号右边表达,式的值,然后把这个值赋给左边的变量,使该变量的,值等于表达式的值。,(3),赋值语句中的“”称作赋值号,与数学中的等,号的意义是不同的,.,赋值号的左右两边不能对换,.,(4),赋值语句左边只能是变量名字而不是表达式,如,:2=x,是错误的,;,右边表达式可以是一个数据、,常量或算式；不能利用赋值语句进行代数式的,演算。（如化简、因式分解、解方程等）,（,5,）对于一个变量可以多次赋值。,【,例题解析,】,例,2,：编写程序，计算一个学生数学、语文、,英语三门课的平均成绩。,分析,：先写出算法，画出程序框图，再进行编程。,结束,开始,输入,a,b,c,输出,y,程序框图,INPUT,“Maths,Chinese,English”,；,a,b,c,y=(a+b+c)/3,PRINT “y=”,；,y,END,程序,:,例,3,：给一个变量重复赋值。,程序,:,A=10,A=A+15PRINT,A,END,A,的输出值是多少,?,分析,:,此程序给变量,A,赋了两次值,.A,的初值为,10,第二次赋值后,初值被“覆盖”,A,的值变为,25,因此输出值是,25.,变式引申,:,在此程序的基础上，设计一个程序，,要求最后,A,的输出值是,30.,A=10,A=A+15,PRINT,A,A=A+5,PRINT,A,END,程序,:,例,3,：给一个变量重复赋值。,程序,:,A=10,A=A+15,PRINT,A,END,例,4,交换两个变量,A,和,B,的值,并输出交换前后,的值。,分析：,引入一个,中间变量,X,将,A,的值赋予,X,又将,B,的值赋予,A,，再将,X,的值赋予,B,，从而达到交换,A,，,B,的值,.,（比如交换装满水的两个水桶里的水需要,再找一个空桶）,INPUT,A,INPUT,B,PRINT,A,，,B,X=A,A=B,B=X,PRINT,A,，,B,END,程序,:,问题,:,能否用下列赋值语句交换,A,B,的值,?,A=B,B=A,不能,!,练习,1,:,编写一个程序,要求输入一个圆的半径,便能输出该圆的周长和面积,.,（,取,3.14,）,分析,:,设圆的半径为,R,则圆的周长,C=2R,面积,S=R,2,可以利用顺序结构中的,INPUT,语句,PRINT,语句和赋值语句设计程序。,INPUT“R=”,；,R,C=2,*,3.14,R,S=3.14,*,R2,PRINT,“,C=,”,；,C,PRINT,“,S=,”,；,S,END,算法中的条件结构是由条件语句来表达的,条件语句是处理条件分支逻辑结构的算法语句,.,条件语句的一般格式,满足条件？,语句,是,否,只含一个“分支”的条件结构,写成条件语句为,IF,条件,THEN,语句体,END IF,当计算机执行这种形式的条件语句时，首先对,IF,后的条件进行判断，如果条件符合，就执行,THEN,后的语句体，否则执行,END IF,之后的语句,.,满足条件？,语句,1,语句,2,是,否,含两个“分支”的条件结构,写成条件语句为,IF,条件,THEN,语句体,1,ELSE语句体,2,END IF,当计算机执行上述语句时，首先对,IF,后的条件进行判断，如果条件符合，就执行,THEN,后的语句体,1,，否则执行,ELSE,后的语句体,2.,条件语句的作用,在程序执行过程中，根据判断是否满足约定的条件而决定是否需要转换到何处去。需要计算机按条件进行分析、比较、判断，并按判断后的不同情况进行不同的处理。,1,、编写一个程序，求任意实数的绝对值。,INPUT “x=”,；,x,IF x0 THEN,y=-x,ELSE,y=x,END IF,PRINT “x=”,；,y,END,程序如下：,程序框图：,开始,输入,x,y=-x,y=x,输出,y,结束,x0,时,一元二次方程有两个不等的实数根,.,(2),当,=0,时,一元二次方程有两个相等的实数根,.,(3),当,=0 THEN,p=-b/(2,*,a),q=SQR(d)/(2,*,a),IF d=0 THEN,PRINT“One real root:”,；,p,ELSE,x1=p+q,x2=p-q,PRINT“Two real roots:“,；,x1,x2,END IF,ELSE,PRINT “No real root,!,”,END IF,END,例,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.,【,程序,】,INPUT,“a,，,b,，,c=”;a,，,b,，,c,IF ba THEN,t=a,a=b,b=t,END IF,IF ca THEN,t=a,a=c,c=t,END IF,IF cb THEN,t=b,b=c,c=t,END IF,PRINT a,，,b,，,c,END,算法中的循环结构是由循环语句来实现的,.,循环结构有两种,-,当型与直到型,.,满足条件？,循环体,是,否,当型循环结构,(,当条件满足时反复执行循环体,),直到型循环结构,(,反复执行循环体直到条件满足,),循环体,是,否,满足条件？,对应于程序框图中的两种循环结构，一般程序设计语言中也有当型（,WHILE,型）和直到型（,UNTIL,型）两种语句结构。,即,WHILE,语句和,UNTIL,语句。,(1)WHILE,语句的一般格式是,:,WHILE,条件,循环体,WEND,其中循环体是由计算机反复执行的一组语句构成的。,WHLIE,后面的“条件”是用于控制计算机执行循环体或跳出循环体的。,WHILE,当,时候,WEND,朝,方向,行走,(1)WHILE,语句的一般格式是,WHILE,条件,循环体,WEND,当计算机遇到,WHILE,语句时,先判断条件的真假,如果条件,符合,就执行,WHILE,与,WEND,之间的循环体,;,然后再检查上述条件,如果条件仍符合,再次执行循环体,这个过程反复进行,直到某一次条件不符合为止,.,这时,计算机将不执行循环体,直接跳到,WEND,语句后,接着执行,WEND,之后的语句,.,满足条件？,循环体,是,否当型循环结构,(2)UNTIL,语句的一般格式是,:,DO,循环体,LOOP UNTIL,条件,循环体,是,否,满足条件？,直到型循环结构,DO,做什么,LOOP UNTIL,绕环回线走,直到达到某种,条件为止,思考,:,参照其直到型循环结构对应的程序框图,说说,计算机是按怎样的顺序执行,UNTIL,语句的？,(2)UNTIL,语句的一般格式是,:,DO,循环体,LOOP UNTIL,条件,循环体,是,否,满足条件？,直到型循环结构,从,UNTIL,型循环结构分析,计算机执行该语句时,先,执行一次循环体,然后进行条件的判断,如果条件不,满足,继续返回执行循环体,然后再进行条件的判断,这个过程反复进行,直到某一次条件满足时,不再执,行循环体,跳到,LOOP UNTIL,语句后执行其他语句,是先执行循环体后进行条件判断的循环语句,.,提问,:,通过对照,大家觉得,WHILE,型语句与,UNTIL,型,语句之间有什么区别呢？,区别,：在,WHILE,语句中,是当条件,满足,时执行循环,体,而在,UNTIL,语句中,是当条件,不满足,时执行循环,体。,WHILE,语句的一般格式,WHILE,条件,循环体,WEND,UNTIL,语句的一般格式,DO,循环体,LOOP UNTIL,条件,例,1.,编写程序,计算自然数,1+2+3+,+99+100,的和,.,分析,:,这是一个累加问题,.,我们可以用,WHILE,型语句,也可以用,UNTIL,型语句。,WHILE,语句,开始,结束,i=1,S=0,i=i+1,S=S+i,输出,S,i100?,是,否,当型循环结构,i=1,S=0,WHLIE i100?,否,是,直到型,i=1,S=0,DO,S=S+i,i=i+1,LOOP UNTIL,i100,PRINT S,END,开始,i=1,S=,0,i100?,是,S=S+i,i=i+1,否,输出,S,结束,当型循环结构,变式训练,(1):,编写程序求,:n!=12345n,的值,.,如何修改,?,输入,n,WHILE,语句,i=1,S=0,WHLIE i100,PRINT S,END,S=1,101,S=S,i,i=i+2,是,开始,结束,i=1,S=0,i=i+1,S=S+i,输出,S,i100?,否,直到型,S=1,S=S,i,i=i+2,i101?,算法案例,1.3,辗转相除法更相减损术,1.1.1,1,、求两个正整数的最大公约数,（,1,）求,25,和,35,的最大公约数,（,2,）求,225,和,135,的最大公约数,2,、求,8251,和,6105,的最大公约数,25,（,1,）,5,5,35,7,所以，,25,和,35,的最大公约数为,5,所以，,225,和,135,的最大公约数为,533=45,课前复习,225,（,2,）,5,45,135,27,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,的最大公约数。,思考：从上述的过程你体会到了什么？,完整的过程,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,，直到余数为,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,否,是,是,INPUT m,n,IF m=0,PRINT “i=”;I,INPUT “a,i,=”;a,v=v*x+a,i=i-1,WEND,PRINT v,END,输入,a,i,进位制,1.3.3,问题,1,我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的,.,比如时间和角度的单位用六十进位制,电子计算机用的是二进制,.,那么什么是进位制,?,不同的进位制之间又有什么联系呢,?,进位制是人们为了计数和运算的方便而约定的一种记数系统，约定满二进一,就是二进制,;,满十进一,就是十进制,;,满十六进一,就是十六进制,;,等等,.,“满几进一”,就是几进制,几进制的,基数,就是几,.,可使用数字符号的个数称为基数,.,基数都是大于,1,的整数,.,例如：二进制可使用的数字有,0,和,1,基数是,2;,十进制可使用的数字有,0,1,2,8,9,等十个数字,基数是,10;,十六进制可使用的数字或符号有,09,等,10,个数字以及,AF,等,6,个字母,(,规定字母,AF,对应,1015),十六进制的基数是,16.,注意,:,为了区分不同的进位制,常在数字的右下脚标明基数,.,如,111001,(2),表示二进制数,34,(5),表示,5,进制数,.,十进制数一般不标注基数,.,问题,2,十进制数,3721,中的,3,表示,3,个千,7,表示,7,个百,2,表示,2,个十,1,表示,1,个一,从而它可以写成下面的形式,:,3721=310,3,+7102,+210,1,+110,0,.,想一想二进制数,1011,(2),可以类似的写成什么形式,?,1011,(2),=12,3,+02,2,+12,1,+12,0,.,同理,:,3421,(5),=35,3,+45,2,+25,1,+15,0,.,C7A16,(16),=1216,4,+716,3,+1016,2,+116,1,+616,0,.,一般地,若,k,是一个大于,1,的整数,那么以,k,为基数的,k,进制数可以表示为一串数字连写在一起的形式,a,n,a,n-1,a,1,a,0(k),(0a,n,k,0a,n-1,a,1,a,0,n?,输出,b,结束,否,是,INPUT a,k,n,i=1,b=0,t=a MOD 10,DO,b=b+t*k(i-1),a=a10,t=a MOD 10,i=i+1,LOOP UNTIL in,PRINT b,END,程序,:,程序框图：,输入,a,k,n,例,2:,把,89,化为二进制的数,.,分析,:,把,89,化为二进制的数,需将,89,先写成如下形式,89=a,n,2,n,+a,n-1,2,n-1,+a,1,2,1,+a,0,2,0,.,89=64+16+8+1=12,6,+02,5,+12,4,+12,3,+02,2,+02,1,+12,0,=1011001,(2),.,但如果数太大,我们是无法这样凑出来的,怎么办,?,89=4421,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,=12,6,+02,5,+12,4,+12,3,+02,2,+02,1,+12,0,=1011001,(2),.,可以用,2,连续去除,89,或所得商,(,一直到商为,0,为止,),然后取余数,-,除,2,取余法,.,2=12+,0,1=02+,1,44 1,例,2:,把,89,化为二进制的数,.,我们可以用下面的除法算式表示除,2,取余法,:,2,89,余数,2,22 0,2,11 0,2,5 1,2,2 1,2,1 0,2,0 1,把算式中各步所得的余数,从下到上排列,得到,89=1011001,(2),.,这种方法也可以推广为把十进制数化为,k,进制数的算法,称为,除,k,取余法,.,解,:,以,5,作为除数,相应的除法算式为,:,17 4,5,89,余数,5,3 2,5,0 3,89=324,(5),.,例,3:,把,89,化为五进制的数,.,问题,5,你会把三进制数,10221,(3),化为二进制数吗,?,解,:,第一步,:,先把三进制数化为十进制数,:,10221,(3),=13,4,+03,3,+23,2,+23,1,+13,0,=81+18+6+1=106.,第二步,:,再把十进制数化为二进制数,:,106=1101010,(2),.,10221,(3),=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,k,b=0,i=0,DO,q=ak,r=a MOD k,b=b+r*10i,i=i+1,a=q,LOOP UNTIL q=0,PRINT b,END,程序,:,例,设计一个程序,实现“除,k,取余法”,.,