浙江省高三信息技术学考总复考点突破课件解析算法与枚举算法

解析算法与枚举算法课标梳理教材重点课标要求学业质量水平简单算法及其程序实现1.理解解析算法、枚举算法的思想,能用解析、枚举的方法来设计算法2.用程序来实现解析算法、枚举算法以及其他简单的算法2-1算法程序实现的综合应用通过综合解决实际问题,编写实行性程序,培养编程解决问题的能力2-2教材研析1解析算法及其程序实现1.基本思想根据问题的前提条件与所求结果之间的关系,找出求解问题的数学表达式,并通过表达式的计算来实现问题的求解。2.解题思路问题的前提条件

要求的解

t=float(input('请输入时间:'))v0=float(input('请输入初速度:'))a=float(input('请输入加速度:'))s=v0

t+a

t

2/2print('位移为',s,'米')典例1编写Python程序,实现如下功能:输入直角三角形2条直角边长,应用勾股定理求出斜边长并输出,程序代码如下。在划线处填上合适的代码。a=float(input('请输入直角三角形直角\边a长:'))b=float(input('请输入直角三角形直角\边b长:'))print('斜边长为',________________________________)(a**2+b

**2)

**0.52枚举算法及其程序实现1.基本思想罗列出所有可能的解,不能遗漏,不能重复,并对每个可能的解进行判断,是正确的解采纳(输出、计数……),不是的抛弃。2.语法结构

循环:罗列出所有可能的解

分支:判断是否是正确的解(循环体中通过if后的条件进行判断)3.范例:输出所有个位上是1,同时又是7的倍数三位正整数,并将满足条件的数的个数输出(如图1所示)。4.优化(1)为了提高效率,要使罗列的解的范围尽可能小

需要判断的次数(循环次数)少。(2)范例:如图2所示。典例2编写Python程序,实现如下功能:输出所有正的2位奇妙平方数(某数的平方与其逆序数的平方互为逆序数,则该数为奇妙平方数,例如122=144,212=441,则12为奇妙平方数)。程序代码如下。在划线处填上合适的代码。#自定义函数cp用于检测参数n1和n2是否互逆defcp(n1,n2):flag=Falsen1=str(n1)n2=str(n2)iflen(n1)==len(n2):foriinrange(len(n1)):if①________________________________:

flag=Truebreakelse:②________________returnflag#以下for循环遍历所有2位正整数c=0foriinrange(10,100,1):b=0a=in1[i]!=n2[len(n1)-1-i]flag=True#以下while循环用于获取i当前遍历到的2位正整数的逆序数whilea>0:

b=b

10+a%10

a=a//10if③____________________________________________andi!=b:

print(str(i)+'的平方:'+str(i

2)+'<——>'+str(b)+'的平方:'+str(b**2))

c+=1print('共有'+str(c)+'个2位奇妙平方数')cp(i**2,b**2)==False(或者notcp(i**2,b**2))解析

①自定义函数cp用于判断参数n1和n2是否互逆,在两数位数一样的前提下,从n1中左起和n2中右起取的数对只要有1对不相等,就不为互逆,终止判断,若所有数对都相等,则n1和n2互逆。②标志位flag初值为False代表开始判断前默认互逆,若n1和n2的数字个数不同,肯定不互逆,将标志位的值改为True。③调用cp函数判断数i的平方和它逆序数b的平方是否互逆,如果函数返回结果为False,则代表二者的平方数互逆,若同时满足i和其逆序数b不相等,则可判定i为奇妙平方数。典例3(2022浙江7月学考)查找与替换。从键盘上分别输入要查找和替换的字符串,对文本文件进行查找与替换,替换后保存到新的文本文件中。完成查找与替换功能的思路是:首先可从待检索文本文件“in.txt”逐行读取文本内容到列表text,然后从键盘上输入查找的字符串key和替换的字符串new,对列表text中的元素逐个进行查找并替换,结果保存到列表result,最后将result写入文件“out.txt”。(1)主程序。text=readfile(″in.txt″)#读入文件key=input(″请输入要查找的字符串:″)new=input(″请输入要替换的字符串:″)result=[]forlineintext:newline=replace(key,new,line)#替换result.append(newline)#添加到列表writefile(″out.txt″,result)#写入文件该程序段采用的算法是____(单选,填字母:A.解析算法/B.枚举算法)。

B(2)读写文本文件,如下的readfile函数,逐行读取文本文件数据存入列表并返回。请在划线处填入合适的代码。defreadfile(filename):f=open(″filename″,encoding=″utf-8″)#打开文件text=[]line=f.readline()#从文件中读取一行whileline:

text.append(line)#添加到列表

line=f.readline()f.close()return________________defwritefile(filename,text):#将text写入filename文件,代码略Text(3)查找字符串,如下的findstr函数,在字符串line中从begin位置开始查找key在字符串line中的位置,请在划线处填入合适的代码。deffindstr(key,line,begin): foriinrange(begin,len(line)-len\(key)+1): if________________________________:

returnireturn-1line[i:i+len(key)]==key(4)替换字符串。如下的replace函数,在字符串line中检索所有的字符串key并替换为new,请在划线处填入合适的代码。defreplace(key,new,line): begin=0 whilebegin<len(line)-len(key)+1:

pos=findstr(key,line,begin)

ifpos==-1:

___________________

else:line=line[0:pos]+new+\line[pos+len(key):len(line)]begin=pos+len(new) returnlinebreak(答案不唯一)解析

(1)枚举算法的基本思想是把问题所有可能的解一一列举,然后判断每一个列举出的可能解是否为正确的解。在枚举算法的程序实现中,逐一列举出每一个可能解,判断其是否为正确解的过程可采用循环结构来实现。而在利用问题提供的约束条件筛选、判断解的过程中则需要用到分支结构。从题干“……逐行读取文本内容到列表text……”,推断出(1)答案为B。(2)根据题干“逐行读取文本文件数据存入列表并返回”,观察列表相关语句“text=[]”和“text.append(line)”,答案为text。(3)自定义函数findstr的功能是在字符串line中查找key,如果找到了返回第一次出现key的索引,如果不存在key,返回-1。从语句“for

i

in

range(begin,len(line)-len(key)+1)”看出for循环语句遍历索引,因此从line中选择从i开始长度为len(key)的字符,和key进行比较,答案为line[i:i+len(key)]==key。(4)自定义函数replace的功能是在字符串line中检索所有的字符串key并替换为new,程序使用了while循环从begin开始遍历字符串line,调用自定义函数findstr在字符串line中查找key,返回值为pos,pos==-1成立,说明当前行不存在key,直接跳出循环或终止循环即可。答案可以是break或begin=len(line)-len(key)+1或begin+=len(line)或begin=len(line),能跳出循环的语句均可。典例4(2023浙江7月学考)小张收集了章回体小说《三国演义》的第1章回至第120章回的120个文件,其文件名依次sg1.txt、sg2.txt、…、sg120.txt。他编写Python程序,对书中人物同时出现的情况进行简单分析,人物及其别名(如“孟德”是“曹操”的别名)作同一人处理。运行程序,用户输入“曹操|孟德刘备|玄德”,输出结果如图所示,图中[11,28]表示曹操,刘备在第11章回至第28章回同时出现。人物同时出现的章回数为:72,章回依次为:[[1,2],[5,6],[11,28],[31,45],[47,52],[54,58],[60,74],[77,82],[106,106],[119,120]]人物同时出现的最大连续章回数是:18A(2)定义函数calculate(total),功能是统计列表names中人物同时出现的章回数,以及同时出现的章回,结果示例如第12题图所示,请在划线处填入合适的代码。defcalculate(total): num,length=0,0

#num保存120个章回中人物同时出现的章回数 result=[]

#result[i][0]、result[i][1]分别存储第i+1段章回的起、止章回号 k=-1 foriinrange(0,120):

ifallIn(total,i):_________________________iflength==0:num+=1(或num=num+1)begin=i+1

result.append([begin,begin])

#在列表result末尾添加一个元素

k+=1length+=1result[k][1]=i+1

else:length=0returnnum,result(3)定义函数getMaxLen(result),功能是统计最大连续章回数,请在划线处填入合适的代码。defgetMaxLen(result): mlen=0 foriteminresult: t=item[1]-item[0]+1 ift>________________:

mlen=treturnmlenMlen(4)定义函数allIn(total,cno),功能是判断列表names中人物是否同时出现在cno章回中,若同时出现,返回True,请在划线处填入合适的代码。defallIn(total,cno): foriteminnames: