第3章 第14课 算法的程序实现综合-【精彩三年】2024-2025学年高中信息技术必修第一册课程探究与巩固PPT课件（浙教版2019）

第14课　算法的程序实现综合 第三章│算法的程序实现 ——3　算法的程序实现，教材第70～108页 新课程目标 基于Python程序设计语言，合理利用模块和函数，通过简单算法解决问题。 目录 CONTENTS 01 命题整体感知 尝试与研析 01 命题整体感知 尝试与研析 命题整体感知 尝试与研析 例1查找与替换。从键盘上分别输入要查找和替换的字符串，对文本文件进行查找与替换，替换后保存到新的文本文件中。 完成查找与替换功能的思路：首先可从待检索文本文件“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.枚举算法)。 (2)读写文本文件。编写如下的readfile()函数，逐行读取文本文件数据存入列表并返回，请在横线处填入合适的代码。 def readfile(filename)： f＝open(filename，encoding＝”utf——8”) #打开文件 text＝[] line＝f.readline() #从文件中读取一行 B 命题整体感知 尝试与研析 while line： text.append(line) #添加到列表 line＝f.readline() f．close() return__________ def writefile(filename，text)： #将text写入filename文件，代码略 text 命题整体感知 尝试与研析 (3)查找字符串。编写如下的findstr()函数，从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<len(line)－len(key)＋1： pos＝findstr(key，line，begin) if pos＝＝－1： 命题整体感知 尝试与研析 __________________________ else： line＝line[0：pos]＋new＋line[pos＋len(key)：len(line)] begin＝pos＋len(key) return line 【解析】 (1)枚举算法指根据问题的本身性质，一一列举问题所有的情况并逐个进行判断，从中挑出符合条件的解。本题读取每一行，并一一查 break 或 begin＋＝1 命题整体感知 尝试与研析 找是否有待替换的字符串，如有则进行替换并放入结果中，属于枚举算法。 (2)本处为函数的返回值部分，从文件中读取每一行后，将该行字符串添加到列表text中，因此最后返回的是列表text。 (3)该自定义函数的功能为查找line字符串中是否有key字符串。若有，则返回起点位置i; 若没有，则检查整个line字符串后返回－1。为查找key在字符串line中的位置，for循环从begin开始，每次循环从i下标位置截取长度为len(key)的字符串与key字符串比较，若相等，则返回i下标，故答案 命题整体感知 尝试与研析 为line[i：i＋len(key)]＝＝key。 (4)若查找函数的返回值pos为－1，则说明从当前位置出发查找整个line字符串并未找到key字符串，故结束该自定义函数并返回line字符串。 命题整体感知 尝试与研析 变式 针对选考 [2024·春晖中学检测]某APP为增加用户活跃度，采用“签到得积分换奖品”的形式来吸引用户。签到积分的规则与玩法如下：①第1天签到得1分，第2天签到得2分，第3天签到得3分，……，第7天及7天以上签到得7分；一旦中途漏签，签到积分从1分开始重新计算；积分在每年最后一天结束时清零。现在用“1”和“0”表示签到和未签到，如某用户下载APP后第1天到第9天的签到记录为“101111011”，则这9天共获得14积分。②APP每年会给用户一次补签一天的机会，补签之后积分的连续性可以持续，例如上面的9天中如果补签第7天增加积分最多，补签 命题整体感知 尝试与研析 后9天的签到记录将变为“101111111”，积分将达到29分。为了找出一年中最佳的补签日，设计如下程序：从文件中读取一年365天(2月以28天计)的签到记录并以字符串形式输出，然后统计出全年的积分，并分析出补签增加积分最多的那天的日期及将这一天补签后可增加的积分数，程序输出效果如下图所示： 命题整体感知 尝试与研析 请回答下列问题。 (1)若第1天到第18天的签到记录为“101110111001101111”，则补签第______天可增加的积分最多。 (2)请在横线处填入合适的代码。 def tongji(s): #统计字符串中的积分 sum，pre＝0，0 for i in range(len(s))： 6 命题整体感知 尝试与研析 if s[i]＝＝”1”： if pre<7： pre＋＝1 sum＋＝pre else： ①_____________ return sum pre＝0 命题整体感知 尝试与研析 def check(ss)： month＝{1：31，2：28，3：31，4：30，5：31，6：30，7：31，8： 31，9：30，10：31，11：30，12：31} max，index＝0，0 for i in range(len(ss))： if ss[i]＝＝”0”： head＝i－1 命题整体感知 尝试与研析 tail＝i＋1 while head>＝0 and ss[head]＝＝”1”： head－＝1 while tail<＝len(ss)－1 and ss[tail]＝＝”1”： tail＋＝1 s1＝ss[head＋1：tail] ②____________________________________________ s2＝ss[head＋1：i]＋”1”＋ss[i＋1：tail] 命题整体感知 尝试与研析 jfzj＝tongji(s2)－tongji(s1) if jfzj>max： max＝jfzj index＝i k＝1 day＝index＋1 while ③_________________： day>month[k] 命题整体感知 尝试与研析 day＝day－month[k] k＋＝1 result＝”补签”＋str(k)＋”月”＋str(day)＋”日增加积分最多！可增加” ＋str(max)＋”分。 ” return result #将全年记录以字符串的形式保存到变量jl 中并输出，代码略 print(”年积分： ”，tongji(jl)) 命题整体感知 尝试与研析 res＝check(jl) print(res) 【解析】 (1)可以看出，101110111001101111 改为101111111001101111，即修改第6 天的值，连续1 的天数最多。 (2)①结合题意，当天数小于7 时，当日积分先加1 再累计；若遇到“0”则重新开始计分；else 分支处理遇“0”的情况，即pre 恢复初值，填pre＝0 。 ②check() 函数用于统计积分改变后的差值最大值。字符串操作中，可以 命题整体感知 尝试与研析 模拟一组数据，跟踪几个指针的最终位置，使之后的代码易于理解。 例如，如图所示，当遇到字符串中的0 时，head 指针向前找0，tail 指针向后找0。 此时若将第i 位字符改为“1”， [head＋1，tail－1]范围内连续为1，此时可以计算两种情况下积分的差值。s2 为将第i 位字符改为“1”后的字符串： 命题整体感知 尝试与研析 故②空建立s2 字符串，填s2＝ss[head＋1：i]＋”1”＋ss[i＋1：tail]。 ③check() 函数最终返回的是一年中的某一天，接下来要计算出day 对应的年、月、日。方法是通过day＝day－month[k]不断向后计算月份，直到无法减出完整月份，填day>month[k]。 命题整体感知 尝试与研析 例2[2023·浙江6月选考]某仓库有一排连续相邻的货位，编号依次为0～n－1，用于放置A、B 两种类型的箱子，A 型箱子占2 个相邻货位，B 型箱子占1 个货位。编写程序，根据已完成的放置或搬离操作，输出空货位数及还可以放置A 型箱子的最多数量(不移动已放置的箱子)。请回答下列问题。 箱子类型 操作类型 货位编号 B 放置 5 A 放置 2，3 B 放置 0 A 放置 7，8 A 搬离 2，3 命题整体感知 尝试与研析 (1)若n 为10，开始时货位全空，经过如上表所示的放置或搬离操作后，不移动已放置箱子的情况下，还可放置A 型箱子的最多数量为_____个。 (2)实现上述功能的部分Python 程序如下，请在横线处填入合适的代码。 # 读取货位总数，存入n，代码略 cnt1＝n lst＝[0]*n #货位状态，0 表示对应的货位为空 while True： 2 命题整体感知 尝试与研析 #读取本次已操作的数据：箱子类型、操作类型、货位编号起始值， 分别存入变量t、d 和s，代码略 if t＝＝'A'： 　　　w＝2 　 ①________________________________： 　　　w＝1 　 else: # t 不是'A'或'B'时退出循环 elif t＝＝'B‘ 或elif t＝＝''B'' 命题整体感知 尝试与研析 　　　break 　 if d＝＝'P': # d 为P 时表示放置，否则表示搬离 　　　②______________________________ 　 else： 　 cnt1＋＝w 　 lst[s]＝1－lst[s] 　 if t＝＝'A'： cnt1－＝w 或cnt1＝cnt1－w 命题整体感知 尝试与研析 　　　lst[s＋1]＝1－lst[s＋1] i, cnt2＝0，0 while i<n－1： 　 if lst[i]＝＝0 and lst[i＋1]＝＝0： 　　　③___________________ 　　　cnt2＋＝1 　 i＋＝1 i＋＝1 或i＝i＋1 命题整体感知 尝试与研析 print('当前空货位数： ', cnt1，', 还可放置A 型箱子的最多数量为： '，cnt2) 【解析】 (1)10 个空位放置情况如下图所示： A 型箱子一个要占2 个相邻货位，最多可放2 个。 (2)搬离时cnt1＋＝w，变量w为应搬离的数量，那么当t＝＝'B'时，搬离 命题整体感知 尝试与研析 数量应为1，故①处填：elif t＝＝'B'。搬离时空位加w，则放置时空位减w，②处填：cnt1－＝w。统计连续两个空位的个数，统计完后i 要向后跳2，故③处填：i＋＝1。 命题整体感知 尝试与研析 变式 针对选考[2024·金华一中检测]某物流配送站需要向n个顺序分布的站点配送货物(起点编号为0，n个站点编号为1到n)，相邻两个站点间的路段有各自的载重上限(单位：吨)，货车运货时不可超重。 现有m件货物(货物编号为1到m)需要发送到不同的站点，已知每件货物的目的地(站点编号)和质量(单位：吨)；配送系统按货物编号顺序分批装车安排配送。为减少运输成本，物流公司需要尽量减少配送次数，配送系统根据m件货物的信息和n条路的载重上限，输出运输次数最少的分批装车的方案。 命题整体感知 尝试与研析 例如，共有5件货物，每件货物的目的地和质量依次为(5，3；2，4；4，2；1，2；3，3)。共有5个站点，每一段的载重上限为8，10，6，8，9。如下图所示： 货物编号m 1 2 3 4 5 目的站点 5 2 4 1 3 货物质量/吨 3 4 2 2 3 站点编号n 1 2 3 4 5 前往该站点的 载重上限/吨 8 10 6 8 9 命题整体感知 尝试与研析 配送以上货物最少可以分2次运输。第1次运输货物1、2(若再增加货物则会在第1个路段超重)，第2次再运输剩余的货物。 请回答下列问题。 (1)若4件货物信息为3，5；4，2；1，3；2，2，且4段公路载重上限为15，9，9，3，则货车_________ (选填：可以/不可以)一次性将所有货物运送至目的地。 (2)实现上述功能的Python程序段和运行界面如下，请在横线处填入合适的代码。 可以 命题整体感知 尝试与研析 请输入货物信息(目的地和重量之间用逗号隔开，货物之间用分号隔开)： 5，3；2，4；4，2；1，2；3，3 请输入每段公路的载重上限(用逗号隔开)： 8，10，6，8，9 第1次运输： 货物1到2 第2次运输： 货物3到5 运输完毕，共运输2次 命题整体感知 尝试与研析 item＝[]；w＝[] n＝m＝0 #输入货物信息保存在item[]中，且item[i][0]保存第i件货物的目的地，item[i][1]保存第i件货物的质量，货物数量存入m，站点数量存入n。代码略 #每段公路的载重上限保存在列表w[]中，且w[i]保存第i段公路的载重上限。代码略 命题整体感知 尝试与研析 def check(a，b)：　#check(a，b)用于检测编号a到b的货物是否可以一次运送 　　　s＝0；flag＝True 　　　f＝[0]*100 　　　for i in range(a，b＋1)： s＋＝①______________ 　　　for i in range(a，b＋1)： item[i][1] 命题整体感知 尝试与研析 f[item[i][0]]＋＝item[i][1] 　for i in range(1，n＋1)： if s>w[i]： 　　　　　　flag＝False 　　　　　　break 　　　else： 　　　　　　if f[i]>0： 命题整体感知 尝试与研析 ②_______________ 　 return flag i＝1；j＝1；x＝0 while i<＝m： 　　　　while j<＝m and check(i，j)＝＝True： j＋＝1 　　　　x＋＝1 s－＝f[i] 命题整体感知 尝试与研析 　　　　print(”第”＋str(x)＋”次运输： 货物”＋str(i)＋”到”＋str(j－1)) 　　　　③___________ print(”运输完毕， 共运输”＋str(x)＋”次”) 【解析】 (1)由于第1段公路的载重上限是15吨，货物的总质量是12吨，满足要求；第1站卸货3吨，第2段的载重上限是9吨，货物的总质量是9吨，满足要求；第2站卸货2吨，第3段的载重上限是9吨，货物的总质量是7吨，满足要求；第3站卸货5吨，第4段的载重上限是3吨，货物的总质量是2吨，满足要求。故货车可以一次性将所有货物运送至目的地。 i＝j 命题整体感知 尝试与研析 (2)主程序枚举各种货物区间，调用函数check(a，b)，用于检测编号a到b的货物是否可以一次运送；③空更新i值，由于i 到j－1范围内的货物已经运输，则i从之后开始；①空求解a到b范围内的货物质量之和；列表f存储该站点的卸货质量，f[a]存储在站点a的卸货质量，②空更新目前的载货质量，由总质量减去站点卸货质量。 命题整体感知 尝试与研析 例3设计一个答题卡填涂识别程序(答题卡样式如图1 所示，每张答题卡共计5 个选择题)。具体算法思想如下： ①读取答题卡图像，根据图像像素点灰度值(根据RGB 值计算得到，若小于设定阈值则表示已填涂)，确定单个像素点是否被填涂；然后根据 图1 命题整体感知 尝试与研析 单个选项填涂区域内像素点的填涂比例，确定当前选项是否被填涂。如果填涂比例超过70%，表示选项已被填涂。 ②建立答题卡坐标模型(如图2)，计算每个选项坐标位置；根据坐标位置遍历每个选项，读取并存储选项值。 图2 命题整体感知 尝试与研析 实现上述功能的Python 程序如下： from PIL import Image x0＝39；y0＝18 #初始化(x0，y0)像素点坐标 fw＝23；fh＝13 #初始化选项填涂区宽度和高度 ch＝”ABCD”；s＝”” def judge(x，y): #判断一个选项是否被填涂 count＝0 命题整体感知 尝试与研析 for i in range(x，x＋fw＋1)： for j in range(y，y＋fh＋1)： R，G，B＝pixels[i，j] #提取填涂区i 行j 列位置像素点的RGB 值 if 0.299*R＋0.587*G＋0.114*B<132: #设定灰度阈值为132 count＋＝1 return #选项区域内像素点填涂比例 >＝70% 表示该选 项已被填涂 命题整体感知 尝试与研析 tw＝35；th＝22 image＝Image.open(”答题卡1.bmp”) #用Image 模块打开答题卡1 图片 pixels＝Image.load() ①_______________ #设定答题卡题数 for row in range(num)： flag＝False for col in range(4)： num＝5 命题整体感知 尝试与研析 a＝x0＋tw*col ②_________________ if judge(a，b)＝＝True： ③_______________ flag＝True if flag＝＝False： s＋＝”#” b＝y0＋th*row s＋＝ch[col] 命题整体感知 尝试与研析 print(s) 请回答下列问题。 (1)执行该程序，识别图1 答题卡1，输出结果为“CBDCA”，则识别答题卡2，输出结果为_____________。 (2)请根据题目要求，在横线处填入合适的代码。 (3)程序中加框处代码有误，请改正：______________________。 【解析】 (1) 根据题目和程序可知答题卡2 中第3 题没有填涂，用“#”代 AB#DC count>＝fw*fh*0.7 命题整体感知 尝试与研析 替，因此答题卡2 识别的结果是AB#DC。 (2)①处设定答题卡题数，故该处代码是num＝5。第1 个for 循环中，row 枚举每个选择题，col 枚举每个选择题的列(4 个选项)，变量a 存储第row 行第col 列左上角坐标的横坐标，纵坐标存在变量b 中，从图2中可知b的表达式为y0＋row*th，故②处代码是b＝y0＋row*th。有了选项A、B、C、D 的左上角坐标，可以调用自定义函数judge()来判断该选项是否被填涂，③处代码表示该col 列被填涂了，输出相应的选项“ABCD”，因变量ch 存储常量“ABCD”，同时每题的填涂情况都要记录，故该处 命题整体感知 尝试与研析 的代码是s＋＝ch[col]。 (3)加框处的代码用于判断区域是否被填涂。依据题目要求是填涂比例超过70%表示选项已被填涂，故该处代码应该是count>＝fw*fh*0.7。 命题整体感知 尝试与研析 |随|堂|检|测| 1． [2024·东阳中学检测]某Python 程序功能如下：输入由大小写字母组成的字符串s，将s中的字符按照大小写重新排列，大写字母在左，小写字母在右，且同类大小写字母间保持原相对顺序，输出转换后的字符串res，并计算大小写字母个数相差的绝对值。程序运行界面如图所示： 请输入字符串： bcdkAABJk 转换后： AABJbcdkk 大小写字母个数相差1个 命题整体感知 尝试与研析 请回答下列问题。 (1)如果输入abcAABBab，则转换后新的字符串为________________。 (2)某同学尝试了两种思路，分别处理大写字母和小写字母，请在横线处填入合适的代码。 s＝input(”请输入字符串： ”) idx＝[] c＝0 AABBabcab 命题整体感知 尝试与研析 res＝”” for ch in s： if ”A”<＝ch<＝”Z”： 　idx.append(c) 　 else： res＝①_______________ #拼接小写字母 　 c＋＝1 res＋ch 命题整体感知 尝试与研析 delta＝②______________________________________________ #计算大小写字母个数相差的绝对值 for i in idx[－1：：－1]: #拼接大写字母 res＝③_____________ print(”转换后： ”，res) print(”大小写字母个数相差”，delta，”个”) 【解析】 (1)由题干描述结合题图可知，大写字母按照原相对顺序全部写 abs(len(res)－len(idx)) 或 abs(len(idx)－len(res)) s[i]＋res 命题整体感知 尝试与研析 在左边，小写字母全部写在右边。 (2)①根据if条件和中文提示可知，此处要求拼接字符；②求长度差的绝对值；③根据range的参数是从后往前可知，应该逆向向左拼接大写字母。 命题整体感知 尝试与研析 2．小明运用Python完成了以下功能： (1)随机产生100个4位正整数，存放在列表list1中。 (2)将列表list1中的数据除去千位和个位(若百位是0，则将百位设置为1)后存放在列表list2中。 (3)将列表list2中的数据除去所有的非素数存放在列表list3中。 (4)将列表list3中的数据删除所有重复的数据后存放在列表list4中。 (5)将列表list4中的数据排序(从小到大)后存放在列表list5中。 命题整体感知 尝试与研析 (6)在列表list5中查数并显示其在列表中的位置。 实现上述功能的Python程序如下，请在横线处填入合适的代码。 import random list1＝[]；list2＝[]；list3＝[]；list4＝[]；list5＝[] #随机产生100个4位正整数 for i in range(100): a＝①________________________________ random.randint(1000，9999) 命题整体感知 尝试与研析 list1.append(a) print(list1) #除去千位和个位(若百位是0，则将百位设置为1) for i in list1: a＝i//10%100 if a<10: ②________________ b＝10＋a 命题整体感知 尝试与研析 else: b＝a list2.append(b) print(list2) #除去所有的非素数 def prime(n): p＝True 命题整体感知 尝试与研析 for i in range(2，n): if n%i＝＝0: 　　　　③_____________________________ 　　　　break return p for i in list2: if prime(i): p＝False或其他等价答案 命题整体感知 尝试与研析 list3.append(i) print(list3) #删除所有重复的数据 for i in range(len(list3)－1): t＝list3[i] if ④__________________________________： list4.append(t) t not in list4或其他等价答案 命题整体感知 尝试与研析 print(list4) #查数 k＝int(input(”请输入待查找的数值： ”)) for i in range(len(list4))： if k＝＝list4[i]： 　 print(str(k)＋”： 位于列表中第”＋⑤___________＋”个位置！ ”) 　 break str(i＋1) 命题整体感知 尝试与研析 else： print(”查无此数！ ”) 【解析】 ①随机产生4位正整数，4位正整数的范围为[1000，9999]。 ②a<10，则表示百位为0，需要设置为1。 ③prime()函数判断是否是素数，n%i＝＝0成立，说明不是素数。 ④删除所有重复的数据，如果已经在list4中，则重复，不需要保留。 ⑤查找k在list4中的位置。 命题整体感知 尝试与研析 3．某校举办了“语文作文现场赛”，参赛学生的姓名和成绩存储在文本文件“gra.txt”中，如图1 所示(每一行记录一位学生的姓名和成绩，以“：”分隔)。陈老师利用Python 程序对作文成绩进行处理，统计出各个分数等级的人数，并输出结果。程序运行界面如图2 所示。 图1　　　　　　 　　　　图2　 命题整体感知 尝试与研析 实现上述功能的Python 程序如下，请在横线处填入合适的代码。 def cla(x): #判断成绩等级 if x>＝50： return ”A” elif x>＝40： 　 return ”B” elif x>＝30： 命题整体感知 尝试与研析 　 return ”C” else： 　 return ”D” gra＝[] #存储各个整型成绩数据 num＝[0]*4 f＝open(”①____________”，encoding＝”utf——8”) lines＝f.readlines() #将对象f 的数据按行存入列表lines 中 gra.txt 命题整体感知 尝试与研析 f．close() #关闭文件 for line in lines: #循环读取列表lines 中的每个元素，并做相应处理 a＝line.strip().split(”：”) #去除结尾的换行符并以冒号为分割符进 行分割后返回列表 gra.append(②_______________________) for i in range(len(gra)): #统计各等级的人数 t＝③_______________ int(a[1])或int(a[－1]) cla(gra[i]) 命题整体感知 尝试与研析 num[ord(t)－65]＋＝1 print(”成绩分布如下： ”) for i in range(len(num)): #输出统计结果 print(chr(i＋65)＋”等级有”＋④________________＋”人”) 【解析】 ①打开文件“gra.txt”；②由代码注释中可得列表gra存储的为各个整型成绩数据，所以使用append()函数添加的也是整型成绩数据，列表a(正向索引)第0号索引的元素为同学姓名(字符串型)、第1号索引的 str(num[i]) 命题整体感知 尝试与研析 元素为同学成绩(字符串型)；列表a(负向索引)第－2号索引的元素为同学姓名(字符串型)、第－1号索引的元素为同学成绩(字符串型)，要将成绩加入到列表gra中；③由num[ord(t)－65]＋＝1可知，t为当前学生成绩对应的等级，所以需要从列表gra中取出每位同学的成绩作为参数传入自定义函数cla()中返回对应的等级；④可得成绩对应的等级有A、B、C、D共4种等级，列表num存储4种等级对应的人数并且为整型，程序最后输出的结果为字符串，故需转换数据类型。 温馨提示：请完成高效作业14 感谢聆听，再见！ $$