高中信息技术 学考复习 第3章 算法的程序实现 课时13 解析算法与枚举算法 课件（共27张PPT）

(共27张PPT)
第3章
课时13 解析算法与枚举算法
信息技术
课标梳理·微知著
教材重点 课标要求 学业质量水平
简单算法及
其程序实现 1.理解解析算法、枚举算法的思想,能用解析、枚举的方法来设计算法
2.用程序来实现解析算法、枚举算法以及其他简单的算法 2-1
算法程序实现
的综合应用 通过综合解决实际问题,编写实行性程序,培养编程解决问题的能力 2-2
教材研析·固基础
1
解析算法及其程序实现
1.基本思想
根据问题的前提条件与所求结果之间的关系,找出求解问题的数学表达式,并通过表达式的计算来实现问题的求解。
2.解题思路
问题的前提条件
要求的解
t=float(input('请输入时间:'))
v0=float(input('请输入初速度:'))
a=float(input('请输入加速度:'))
s=v0 t+a t 2/2
print('位移为',s,'米')
典例1 编写Python程序,实现如下功能:输入直角三角形2条直角边长,应用勾股定理求出斜边长并输出,程序代码如下。在划线处填上合适的代码。
a=float(input('请输入直角三角形直角\边a长:'))
b=float(input('请输入直角三角形直角\边b长:'))
print('斜边长为',________________________________)
(a * * 2+b * * 2) * * 0.5
2
枚举算法及其程序实现
1.基本思想
罗列出所有可能的解,不能遗漏,不能重复,并对每个可能的解进行判断,是正确的解采纳(输出、计数……),不是的抛弃。
2.语法结构
　循环:罗列出所有可能的解
　分支:判断是否是正确的解(循环体中通过if后的条件进行判断)
3.范例:输出所有个位上是1,同时又是7的倍数三位正整数,并将满足条件的数的个数输出(如图1所示)。
4.优化
(1)为了提高效率,要使罗列的解的范围尽可能小 需要判断的次数(循环次数)少。
(2)范例:如图2所示。
典例2 编写Python程序,实现如下功能:输出所有正的2位奇妙平方数(某数的平方与其逆序数的平方互为逆序数,则该数为奇妙平方数,例如122=144, 212=441,则12为奇妙平方数)。程序代码如下。在划线处填上合适的代码。
#自定义函数cp用于检测参数n1和n2是否互逆
def cp(n1,n2):
flag=False
n1=str(n1)
n2=str(n2)
if len(n1)==len(n2):
for i in range(len(n1)):
if ①________________________________:
flag=True
break
else:
②________________
return flag
#以下for循环遍历所有2位正整数
c=0
for i in range(10,100,1):
b=0
a=i
n1[i]!=n2[len(n1)-1-i]
flag=True
#以下while循环用于获取i当前遍历到的2位正整数的逆序数
while a>0:
　b=b 10+a % 10
　a=a//10
if ③____________________________________________ and i!=b:
print(str(i)+'的平方:'+str(i 2)+'<——>'+str(b)+'的平方:'+str(b**2))
　c+=1
print('共有'+str(c)+'个2位奇妙平方数')
cp(i**2,b**2)==False(或者not cp(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=[]
for line in text:
newline=replace(key,new,line)#替换
result.append(newline)#添加到列表
writefile(″out.txt″,result)#写入文件
该程序段采用的算法是____(单选,填字母:A.解析算法/B.枚举算法)。
B
(2)读写文本文件,如下的readfile函数,逐行读取文本文件数据存入列表并返回。请在划线处填入合适的代码。
def readfile(filename):
f=open(″filename″,encoding=″utf-8″) #打开文件
text=[]
line=f.readline() #从文件中读取一行
while line:
　text.append(line) #添加到列表
　line=f.readline()
f.close()
return ________________
def writefile(filename,text): #将text写入filename文件,代码略
Text
(3)查找字符串,如下的findstr函数,在字符串line中从begin位置开始查找key在字符串line中的位置,请在划线处填入合适的代码。
def findstr(key,line,begin):
for i in range(begin,len(line)-len\(key)+1):
if________________________________:
return i
return -1
line[i:i+len(key)]==key
(4)替换字符串。如下的replace函数,在字符串line中检索所有的字符串key并替换为new,请在划线处填入合适的代码。
def replace(key,new,line):
begin=0
while begin　 pos=findstr(key,line,begin)
　 if pos==-1:
___________________
　 else:
line=line[0:pos]+new+\line[pos+len(key):len(line)]
begin=pos+len(new)
return line
break(答案不唯一)
解析 (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]]
人物同时出现的最大连续章回数是:18
请回答下列问题:
(1)观察第12题图,可知曹操与刘备在第36章回中_____(单选,填字母:A.同时/B.没有同时)出现。
主程序如下:

输入姓名、别名,姓名存入列表names,如names=[″曹操″,″刘备″]
统计各个章回中,列表names中每个人物(含别名)出现的次数,结果存入字典total,如total={″曹操″:[2,5,7,…],″刘备″:[50,47,0,…]},表示曹操在第1,2,3,…章回分别出现了2,5,7,…次
代码略

num,result=calculate(total)
mlen=getMaxLen(result)
print(″人物同时出现的章回数为:″,\num,″,章回依次为:″)
print(result)
print(″人物同时出现的最大连续章回数\是:″,mlen)
A
(2)定义函数calculate(total),功能是统计列表names中人物同时出现的章回数,以及同时出现的章回,结果示例如第12题图所示,请在划线处填入合适的代码。
def calculate(total):
num,length=0,0　#num保存120个章回中人物同时出现的章回数
result=[]　#result[i][0]、result[i][1]分别存储第i+1段章回的起、止章回号
k=-1
for i in range(0,120):
　 if allIn(total,i):
_________________________
if length==0:
num+=1(或num=num+1)
begin=i+1
result.append([begin,begin])
#在列表result末尾添加一个元素
　 k+=1
length+=1
result[k][1]=i+1
　 else:
length=0
return num,result
(3)定义函数getMaxLen(result),功能是统计最大连续章回数,请在划线处填入合适的代码。
def getMaxLen(result):
mlen=0
for item in result:
t=item[1]-item[0]+1
if t>________________:
　mlen=t
return mlen
Mlen
(4)定义函数allIn(total,cno),功能是判断列表names中人物是否同时出现在cno章回中,若同时出现,返回True,请在划线处填入合适的代码。
def allIn(total,cno):
for item in names:
　 if ________________________:
return False
　 return True
total[item][cno]==0
解析 本题考查Python语言基础及字符串处理的综合知识。(1)观察图可知,第36回出现在[31,45]中,表明曹操与刘备这两个人物在36回同时出现,故选A。(2)由于num保存120个章回中人物同时出现的章回数,其初值为0,因此若检查到符合条件时,即调用函数allIn(total,cno)且其值为True时,计数器num加1,因此其表达式为num+=1。(3)此处统计最大连续章回数,变量mlen即为返回值。在循环中,将连续章回数t与最大值mlen进行比较,若有比最大值mlen更大的值t,则将t值赋值给mlen,故答案是mlen。(4)由于total={″曹操″:[2,5,7,…],″刘备″:[50,47,0,…]},表示曹操在第1,2,3,…章回分别出现了2,5,7,…次,根据这个信息可知total是一个字典,item是某人物名,cno是某章回号的值,因此若total[item][cno]==0,则表明人物item在章回号cno中出现的次数为0,故函数返回值为False,反之则返回True。