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

这是一份高中信息技术学考复习第3章算法的程序实现课时13解析算法与枚举算法课件，共27页。PPT课件主要包含了课标梳理·微知著，教材研析·固基础，问题的前提条件，要求的解，flagTrue，Text，Mlen等内容，欢迎下载使用。

1.基本思想根据问题的前提条件与所求结果之间的关系,找出求解问题的数学表达式,并通过表达式的计算来实现问题的求解。2.解题思路
t=flat(input('请输入时间:'))v0=flat(input('请输入初速度:'))a=flat(input('请输入加速度:'))s=v0? t+a? t? ? 2/2print('位移为',s,'米')
典例1 编写Pythn程序,实现如下功能:输入直角三角形2条直角边长,应用勾股定理求出斜边长并输出,程序代码如下。在划线处填上合适的代码。
a=flat(input('请输入直角三角形直角\边a长:'))b=flat(input('请输入直角三角形直角\边b长:'))print('斜边长为',________________________________)
(a * * 2+b * * 2) * * 0.5
1.基本思想罗列出所有可能的解,不能遗漏,不能重复,并对每个可能的解进行判断,是正确的解采纳(输出、计数……),不是的抛弃。2.语法结构?　循环:罗列出所有可能的解?　分支:判断是否是正确的解(循环体中通过if后的条件进行判断)
3.范例:输出所有个位上是1,同时又是7的倍数三位正整数,并将满足条件的数的个数输出(如图1所示)。
4.优化(1)为了提高效率,要使罗列的解的范围尽可能小 需要判断的次数(循环次数)少。(2)范例:如图2所示。
典例2 编写Pythn程序,实现如下功能:输出所有正的2位奇妙平方数(某数的平方与其逆序数的平方互为逆序数,则该数为奇妙平方数,例如122=144, 212=441,则12为奇妙平方数)。程序代码如下。在划线处填上合适的代码。
#自定义函数cp用于检测参数n1和n2是否互逆def cp(n1,n2):flag=Falsen1=str(n1)
n2=str(n2)if len(n1)==len(n2):fr i in range(len(n1)):if ①________________________________: flag=Truebreakelse:②________________return flag#以下fr循环遍历所有2位正整数c=0fr i in range(10,100,1):b=0a=i
n1[i]!=n2[len(n1)-1-i]
#以下while循环用于获取i当前遍历到的2位正整数的逆序数while a>0:　b=b? 10+a % 10　a=a//10if ③____________________________________________ and i!=b: print(str(i)+'的平方:'+str(i? ? 2)+'<——>'+str(b)+'的平方:'+str(b**2))　c+=1print('共有'+str(c)+'个2位奇妙平方数')
cp(i**2,b**2)==False(或者nt 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写入文件“ut.txt”。
(1)主程序。text=readfile(″in.txt″)#读入文件key=input(″请输入要查找的字符串:″)new=input(″请输入要替换的字符串:″)result=[]fr line in text:newline=replace(key,new,line)#替换result.append(newline)#添加到列表writefile(″ut.txt″,result)#写入文件该程序段采用的算法是____(单选,填字母:A.解析算法/B.枚举算法)。 
(2)读写文本文件,如下的readfile函数,逐行读取文本文件数据存入列表并返回。请在划线处填入合适的代码。def readfile(filename):f=pen(″filename″,encding=″utf-8″) #打开文件text=[]line=f.readline() #从文件中读取一行while line:　text.append(line) #添加到列表　line=f.readline()f.clse()return ________________def writefile(filename,text): #将text写入filename文件,代码略
(3)查找字符串,如下的findstr函数,在字符串line中从begin位置开始查找key在字符串line中的位置,请在划线处填入合适的代码。def findstr(key,line,begin):fr i in range(begin,len(line)-len\(key)+1):if________________________________: return ireturn -1
line[i:i+len(key)]==key
(4)替换字符串。如下的replace函数,在字符串line中检索所有的字符串key并替换为new,请在划线处填入合适的代码。def replace(key,new,line):begin=0while beginbreak(答案不唯一)
解析 (1)枚举算法的基本思想是把问题所有可能的解一一列举,然后判断每一个列举出的可能解是否为正确的解。在枚举算法的程序实现中,逐一列举出每一个可能解,判断其是否为正确解的过程可采用循环结构来实现。而在利用问题提供的约束条件筛选、判断解的过程中则需要用到分支结构。从题干“……逐行读取文本内容到列表text……”,推断出(1)答案为B。(2)根据题干“逐行读取文本文件数据存入列表并返回”,观察列表相关语句“text=[]”和“text.append(line)”,答案为text。
(3)自定义函数findstr的功能是在字符串line中查找key,如果找到了返回第一次出现key的索引,如果不存在key,返回-1。从语句“fr i in range(begin,len(line)-len(key)+1)”看出fr循环语句遍历索引,因此从line中选择从i开始长度为len(key)的字符,和key进行比较,答案为line[i:i+len(key)]==key。(4)自定义函数replace的功能是在字符串line中检索所有的字符串key并替换为new,程序使用了while循环从begin开始遍历字符串line,调用自定义函数findstr在字符串line中查找key,返回值为ps,ps==-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。他编写Pythn程序,对书中人物同时出现的情况进行简单分析,人物及其别名(如“孟德”是“曹操”的别名)作同一人处理。运行程序,用户输入“曹操|孟德　刘备|玄德”,输出结果如图所示,图中[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中每个人物(含别名)出现的次数,结果存入字典ttal,如ttal={″曹操″:[2,5,7,…],″刘备″:[50,47,0,…]},表示曹操在第1,2,3,…章回分别出现了2,5,7,…次代码略‴num,result=calculate(ttal)mlen=getMaxLen(result)print(″人物同时出现的章回数为:″,\num,″,章回依次为:″)print(result)print(″人物同时出现的最大连续章回数\是:″,mlen)
(2)定义函数calculate(ttal),功能是统计列表names中人物同时出现的章回数,以及同时出现的章回,结果示例如第12题图所示,请在划线处填入合适的代码。def calculate(ttal):num,length=0,0　#num保存120个章回中人物同时出现的章回数result=[]　#result[i][0]、result[i][1]分别存储第i+1段章回的起、止章回号k=-1fr i in range(0,120): 　 if allIn(ttal,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=0fr item in result:t=item[1]-item[0]+1if t>________________: 　mlen=treturn mlen
(4)定义函数allIn(ttal,cn),功能是判断列表names中人物是否同时出现在cn章回中,若同时出现,返回True,请在划线处填入合适的代码。def allIn(ttal,cn):fr item in names:　 if ________________________:  return False　 return True
ttal[item][cn]==0