浙江版信息技术高考总复习专题六算法的程序实现(讲解练)教学讲练

考点清单栏目索引专题六算法的程序实现技术技术浙江专用浙江专用考点清单栏目索引考点一考点一解析算法及程序实现解析算法及程序实现考向基础1.解析算法的基本思想用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式,并通过数学表达式的计算来实现问题的求解。如:已知圆的半径为r,求圆的面积s,则可通过公式s=3.14*r*r计算得到。2.解析算法的程序实现(1)分析问题,建立正确的数学模型,找到数学计算式或数学算法。要注意的是,有些问题能找到一个明确的公式,但是有些问题可能是一个运算过程,比如除二倒取余法求二进制,辗转相除法求最大公约数等问题。考点清单考点清单考点清单栏目索引(2)将数学计算或数学算法转化为VB运算过程。考向突破解析算法一般难度不大,重点题型是各种进制之间的相互转换。例1将十进制数转化为二进制数的VB程序段如下:DimyAsInteger,sAsString,rAsIntegery=Val(Text1.Text)输入十进制数s=DoWhiley0LoopText2.Text=s显示二进制数考点清单栏目索引方框中的代码由以下三部分组成:s=Str(r)+sy=y2r=yMod2代码顺序正确的选项是()A.B.C.D.解析解析本题采用“除2取余法”将十进制转换成二进制,先求余数(Mod运算)并保存,再求商(整除),商用来下一次求余数。重复执行该过程直到商为0。答案答案D考点清单栏目索引例2辗转相除法是数学史中著名的算法,用于计算两个正整数a和b的最大公约数。步骤如下:现编写程序,在文本框Text1和Text2中输入a和b,在文本框Text3中输出两数的最大公约数。代码如下:PrivateSubCommand1_Click()DimaAsInteger,bAsInteger,rAsInteger变量ab余数初始值24159第一次辗转1596第二次辗转963第三次辗转630余数为0时终止,最大公约数为3考点清单栏目索引a=Val(Text1.Text)b=Val(Text2.Text)r=aModbDoWhilea=bb=rr=aModbLoopText3.Text=EndSub解析解析循环结束条件是r=0,因此循环条件是r0或r0。退出循环后,结果存在变量b中。答案答案r0str(b)考点清单栏目索引考点二考点二枚举算法及程序实现枚举算法及程序实现考向基础1.枚举算法的基本思想将问题的可能解一一列举,逐个判断,找到所有符合条件的解。即使中途找到符合的解也要继续找下去,要将所有可能解找完才结束。设计枚举算法时要尽量减小罗列范围(提高算法的效率),不能遗漏,也不能重复。2.枚举算法的程序实现根据枚举算法的主要思想:一一列举,逐个判断。因此一般情况下枚举算法的代码具有以下特点:(1)用循环语句在一定范围内列举所有可能的解。(2)用选择语句判断和选择真正的解。枚举算法的一般格式:考点清单栏目索引For(列举所有可能的解)If可能解是正确解Then输出该解或计数Next注意:循环语句不一定用For语句,也可用Do语句。3.多变量列举某些枚举算法的问题比较复杂,可能有多个变量需要列举,此时就需要多重循环,也即循环嵌套。格式如下:For(列举变量1所有可能的解)For(列举变量2所有可能的解)If该组解是正确解Then输出该组解或计数考点清单栏目索引NextNext如鸡兔同笼问题、百鸡百钱问题等。在设定多个变量的列举范围时,可以利用验证条件,尽可能缩小列举范围,减少列举变量,从而减少循环的嵌套。如百鸡百钱问题:100元钱买100只鸡,公鸡5元一只,母鸡3元一只,小鸡1元3只。则代码如下:Forx=1To100Fory=1To100Forz=1To100Ifx+y+z=100And5*x+3*y+z/3=100Then输出该组解或计数NextzNexty考点清单栏目索引Nextx利用验证条件,代码可优化为:Forx=1To20公鸡最多不超过20只Fory=1To33母鸡最多不超过33只z=100-x-yIf5*x+3*y+z/3=100Then输出该组解或计数NextyNextx考点清单栏目索引例寻找3位的水仙花数。什么是水仙花数?水仙花数是指一个n位数(n3),它的每一位上的数字的n次幂之和等于它本身。例如153是水仙花数,因为13+53+33=153。解决此问题的VisualBasic程序如下,程序界面如图所示,在列表框List1中输出结果。在(1)和(2)划线处,填入合适的语句或表达式,把程序补充完整。PrivateSubCommand1_Click()考点清单栏目索引DimiAsIntegerDima,b,cAsIntegerFor(1)a=i100b=i10Mod10c=iMod10If(2)ThenList1.AddItemStr(i)NextEndSub(1)程序中划线处(1)应填入。(2)程序中划线处(2)应填入。考点清单栏目索引解析解析(1)枚举算法在列举的过程中,不能遗漏任何一个可能的解,寻找3位的水仙花数,100到999都是可能解。因此列举所有可能解的语句应该是Fori=100To999。(2)If语句用于检验当前列举的可能解i是不是正确解。水仙花数的验证条件:它的每一位上的数字的n次幂之和等于它本身,本程序要求找出3位的水仙花数,因此n=3,变量a、b、c是i的百位、十位和个位上的数字,因此验证条件是a3+b3+c3=i。答案答案(1)i=100To999(2)a3+b3+c3=i考点清单栏目索引考向突破从目前出现的真题看,直接考枚举算法的不多,常考字符串的处理,一般题型为:输入一串字符串,字符串中有一些特殊字符做为间隔符号,利用该间隔符号,将字符串中的字符提取,并作进一步的数据分析或处理。从代码特点和思想方法上分析,该类问题也利用了枚举算法的思想。一、字符串问题相关知识1.字符大小的比较字符(包括字符串)在计算机中存储的是每个字符的内码值。字符比大小实际上是比较字符的ASCII码值。如“a”“b”,“ab”“abc”,“abc”“abd”,“acde”=“a”Andch=“A”Andch=“0”Andch=“A”Andch=“a”Andch=“A”Andch=“a”Andch=“z”)考点清单栏目索引4.字符转换二、字符串基本操作1.判断是否对称f=truen=Len(s)Fori=1Ton2IfMid(s,i,1)Mid(s,n-i+1,1)Then功能表达式大写转小写Chr(Asc(ch)+32)小写转大写Chr(Asc(ch)-32)求字母的字母序小写字母:Asc(ch)-96或Asc(ch)-Asc(“a”)+1大写字母:Asc(ch)-64或Asc(ch)-Asc(“A”)+1考点清单栏目索引f=false:ExitForEndIfNexti最后判断f的值,如果是true,则对称,否则不对称。2.字符串反转n=Len(s)Fori=1Tons1=Mid(s,i,1)+s1Nexti得到的字符串s1是s的反串。3.插入字符串在字符串s中,在第n个位置插入字符串c:考点清单栏目索引s1=Mid(s,1,n-1)+c+Mid(s,n,Len(s)-n+1)如s=“hppynewyear”,n=2,c=“aa”,则s1=“haappynewyear”。4.删除字符串在字符串s中,删除子串s1:i=1DoWhilei=AAndch=aAndch=0Andch=9Thenp=Elset=考点清单栏目索引p=0Ifch=-Thenflag=-1ElseIfch=+Thenflag=1EndIfEndIfNextiLabel1.Caption=Str(t)EndSub(3)若文本框Text1中输入内容的结束符“=”缺失(即输入内容为12+28-15+50),单击“计算”按钮后,标签Label1上显示的内容是。考点清单栏目索引解析解析本题的解题关键在于理解非数字字符的操作。For语句遍历字符串值,If语句判断字符类型。(1)略。(2)分析判断条件可知,要执行数字相连。原值p乘10加新出现的值Val(ch)组成新值。非数字符号出现,要把前值放入累加器t中,flag存放前值符号,因此要累加flag*p。(3)由于“=”缺失,造成最后一个数50没有被累加。答案答案(1)C(2)p*10+Val(ch)t+flag*p(3)25考点清单栏目索引考点三考点三排序算法及程序实现排序算法及程序实现考向基础1.冒泡排序的基本思想把待排序的n个元素的数组看成是垂直堆放的一列数据,从最下面的一个元素起,自下而上地比较相邻的两个元素中的数据,将较小的数据换到上面。重复这一过程,直到处理完最后两个元素中的数据,称为一遍加工。第一遍加工完成后,最小的数据已经上升到第一个元素的位置。然后对余下的n-1个元素重复上述处理过程,直至最后进行余下两个数据的比较和交换。n个数需要n-1遍排序。以数据130,20,98,15,67,3为例,从小到大冒泡排序的操作过程如下:考点清单栏目索引原始数据130209815673第1遍排序后313020981567第2遍排序后315130209867第3遍排序后315201306798第4遍排序后315206713098第5遍排序后315206798130考点清单栏目索引2.冒泡排序的程序实现Fori=1Ton-1n个数需要n-1遍排序Forj=nToi+1Step-1从后往前,两两比较,直到a(i+1)和a(i)比较完Ifa(j)a(j-1)Then比较相邻的两个数temp=a(j-1):a(j-1)=a(j):a(j)=temp小的数在后面,则交换EndIfNextjNexti外循环“Fori=1Ton-1”中的变量i表示第i遍冒泡排序,n个数需要n-1遍排序。由内循环“Forj=nToi+1Step-1”可看出,冒泡比较的方向是从后往前,两两比较,第i遍的比较次数是n-i次,交换次数最多是n-i次,交换次数最少是0次。考点清单栏目索引从小到大排序(升序),If语句中条件表达式为:a(j)a(j-1)。例1有如下程序段:Fori=1To2Forj=5Toi+1Step-1Ifa(j)a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti数组元素a(1)到a(5)的值依次为“95,88,66,80,75”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为()A.66,75,95,88,80B.66,75,80,95,88C.95,88,66,80,75D.95,88,80,75,66考点清单栏目索引解析解析此题为冒泡排序,升序排序,排序两遍。答案为A。答案答案A3.选择排序的基本思想在所有的元素中选出最小(大)的数据,把它与第一个数据交换,然后在其余的元素中再选出最小(大)的数据与第二个数据交换。以此类推,直至所有数据排序完成。n个数需要n-1遍排序。以数据130,20,98,15,67,3为例,从小到大选择排序的操作过程如下:考点清单栏目索引原始数据130209815673第1遍排序后320981567130第2遍排序后315982067130第3遍排序后315209867130第4遍排序后315206798130第5遍排序后315206798130考点清单栏目索引4.选择排序的程序实现选择排序的代码如下:Fori=1Ton-1k=iForj=i+1TonIfa(j)a(k)Thenk=jNextjIfkiThentemp=a(i):a(i)=a(k):a(k)=tempEndIfNexti外循环“Fori=1Ton-1”中的变量i表示第i遍选择排序,n个数需要n-1遍排序。考点清单栏目索引矩形框内代码用于寻找数据元素a(i)到a(n)的最小值,变量k记录当前找到的最小值的位置,即数组元素的下标,则a(k)就是当前找到的最小的数组元素。它的思想方法是先假设数组的第i项是最小的(第i遍排序),因此k记为i,然后把从第i+1项开始的所有数组元