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

第11课　简单算法及其程序实现 第三章│算法的程序实现 ——3.3　简单算法及其程序实现，教材第97～100页 新课程目标 1．掌握解析算法和枚举算法的基本思想。　2.根据需要选用合适的算法(解析算法、枚举算法)编程来实现问题的求解。 目录 CONTENTS 教材整体感悟 知本与探源 01 02 命题整体感知 尝试与研析 01 教材整体感悟 知本与探源 教材整体感悟 知本与探源 1．解析算法 (1)解析算法的基本思想是指根据问题的____________与____________之间的关系，找出求解问题的数学表达式，并通过表达式的计算来实现问题的求解。 (2)编制解析程序时，必须保证计算过程描述的正确性。特别是把数学表达式转换成Python表达式时，必须注意这种转换的正确性，否则容易产生运算结果错误或运行过程错误。 前提条件 所求结果 教材整体感悟 知本与探源 2．枚举算法 (1)枚举算法的基本思想是把问题所有可能的解一一列举，然后判断每一个列举出的可能解是否为正确的解。 (2)在枚举算法的程序实现中，逐一列举出每一个可能解，判断其是否为正确解的过程可采用循环结构来实现。而在利用问题提供的约束条件筛选、判断解的过程中则需要用到分支结构。 教材整体感悟 知本与探源 1．设计解析算法的一般步骤 (1)明确问题的前提条件；(2)明确要求的解；(3)寻找条件与结果之间的关系式，确保数学表达式的正确性；(4)在编程中正确描述数学表达式。 2．枚举算法的优缺点和注意事项 (1)优点：对现实生活的直接描述，易于理解，容易证明算法的正确性。 (2)缺点：枚举算法需要考察多个变量的大量状态，效率比较低。 (3)注意事项：要做到既不遗漏任何一个解，也不重复枚举；尽可能结合 教材整体感悟 知本与探源 解析算法，减少枚举变量和枚举变量的范围，提高效率。 3．Python文件读写操作 (1)open()函数用于打开由参数指定的文件对象，并通过参数指定打开方式。例如： f＝open(”test.text”，”r”)　#以读文件模式(参数”r”)打开文件test.txt f＝open(”test.text”，”w”)　#以写文本文件模式(参数”w”)打开文件test.txt 教材整体感悟 知本与探源 (2)read()方法用于将文件中的全部内容读取到内存。例如： f．read()　　　　#一次性读取文件的全部内容 f．read(size)　　#每次最多读取size个字节的内容 (3)readline()方法可以从文件中读取一行，并返回字符串。 readlines()方法可以一次性读取整个文件的内容，并按行返回到list。 (4)close()用于关闭文件，如f.close()。 02 命题整体感知 尝试与研析 命题整体感知 尝试与研析 例1请阅读以下材料，并回答问题。 材料一：珠穆朗玛峰的高度为8848.86 米。 材料二：有个科学猜想节目：如果有一张足够大的纸，其厚度为0.1 毫米，对折一次纸的厚度增加1 倍。设一张纸的厚度为h，对折k 次，那么纸的厚度为h×2k。 材料三：纸对折多少次后可以超过珠穆朗玛峰的高度的算法流程图如图所示： 命题整体感知 尝试与研析 (1)材料二中，纸的厚度为h，对折k 次，由此可得出纸的厚度为h×2k，这个过程属于用算法解决问题的_____(单选，填字母：A.抽象与建模；B.设计算法；C.描述算法)。 A 命题整体感知 尝试与研析 (2)材料三的流程图中加虚线框的过程属于算法控制结构中的________结构。 (3)实现上述功能的Python程序段如下，请在横线处填入合适的代码。 h＝0.0001 k＝0 while ________________： k＝k＋1 循环 h<＝8848.86 命题整体感知 尝试与研析 h＝h*2 print(”需要对折”，k，”次”) (4)解决此问题的算法是______________(选填：解析算法/枚举算法)。 【解析】 (1)用数学符号描述解决问题的计算模型，属于抽象与建模。 (2)有比较框，有环状结构，属于循环结构。 (3)珠穆朗玛峰的高度为8848.86 米，当折叠高度小于或等于该高度时，继续循环。 解析算法 命题整体感知 尝试与研析 (4)根据问题的前提条件与所求结果之间的关系，找出求解问题的数学表达式，属于解析算法。 命题整体感知 尝试与研析 变式 编程求s＝e＋ ，其中e是自然常数，可以在math模块中调用，n！为阶乘，n！＝1×2×3×4×…×(n－1)×n。输入n的值，执行程序后，输出结果s。请回答下列问题。 (1)实现上述功能的Python程序段如下，请在横线处填入合适的代码。 import math　#导入math模块 def f(n)： sum＝0 命题整体感知 尝试与研析 t＝①____ for i in range(②_____________)： t＝t*③_____________ return sum n＝int(input(”输入n的值： ”)) s＝④________ 1 1，n＋1 math.e/i f(n) 命题整体感知 尝试与研析 print(s) (2)下列代码与程序段中加框处代码的功能相同的有________(多选，填字母)。 A．sum＝sum＋t B．sum＋＝t C．sum＝t D．sum＝int(sum＋t) AB 命题整体感知 尝试与研析 【解析】 (1)利用函数调用和迭代算法求解表达式的值，sum初始值为0，需要加上第一项(e/1！)，t的初始值为1；range是左闭右开，故②答案为1，n＋1。③为迭代思想，其中e使用math.e。④为函数调用。 (2)sum用于累加结果。 命题整体感知 尝试与研析 例2票据中模糊数字推断问题：一张票据上有一个由4 位数字组成的编号，甲说数字编号的前两位数字相同，但都不是零；乙说数字编号的后两位数字是相同的，但与前两位不同；丙说数字编号是一个整数的二次方。请根据以上线索推断出编号，回答下列问题。 (1)问题分析 只要一一列举出4 位数字AABB 中A 与B 的所有可能组合，保证A≠B 且A≠0，再验证二次方问题，就可以得到问题的解。一一列举、逐一验证属于用_____(单选，填字母：A.枚举算法；B.解析算法)求解。 A 命题整体感知 尝试与研析 (2)设计算法 其算法的流程图如下，请将虚线框处的算法补充完整，判断输出可能的四位数K。 命题整体感知 尝试与研析 (3)编程实现 实现上述功能的Python程序段如下，请在横线处填入合适的代码，并在加框处填入合适的语句块。 import math A＝1 while A<10： B＝0 命题整体感知 尝试与研析 while B<10： if A！＝B： K＝A*1000＋A*100＋B*10＋B C＝①_____________________ ② B＝B＋1 A＝A＋1 int(math.sqrt(K)) 命题整体感知 尝试与研析 命题整体感知 尝试与研析 变式1 王老师有一张重要的发票不慎落水，发票编号由一个五位数组成，中间的百位和十位这2个数字变模糊了，如图所示。王老师只记得这个五位数是37或67的倍数。 编写程序，找出所有可能的数字，并统计满足条件的个数。实现该功能的Python程序段如下，请在横线处填入合适的代码。 c＝0 命题整体感知 尝试与研析 for i in range(100)： n＝①_______________ if②______________________________： 　 print(n) 　 ③______________ print('共找到'，c，'个数字！') 25006＋i*10 n%37＝＝0 or n%67＝＝0 c＋＝1 命题整体感知 尝试与研析 【解析】 ①列举范围：25□□6，其中□□的范围为00～99，故i的范围为0～99，添加在十位，需乘10；②判断条件：该数能被37或67整除；③统计满足条件的个数。 命题整体感知 尝试与研析 变式2[2024·上虞中学检测]小华忘记了某邮箱的登录密码， 该登录密码共有8位，前3位是他姓名拼音首字母的缩写，后5位是一个由3开头的五位数。他记得若将这个五位数经过平方计算后，可得到一个每位数字各不相同的十位数。例如，五位数“32043”经平方计算后得到“1026753849”，“1026753849”是一个每位数字各不相同的十位数，则“32043”就是一个符合要求的密码的后5位。 编写程序，查找所有符合要求的密码后5位。实现该功能的Python程序段如下，请在横线处填入合适的代码。 命题整体感知 尝试与研析 for i in range(30000，40000)： n＝①______________ a＝[0]*10 while n！＝0： x＝n%10 a[x]＝1 ②______________ i**2 或 i*i n＝n//10 命题整体感知 尝试与研析 y＝0 for j in range(0，10)： y＋＝a[j] if ③_______________： 　　 print(i) 【解析】 i循环罗列了密码的范围，①空为求该5位数的平方；内层的while循环作用是提取各个位置上的数值，并利用列表a统计该数值是否 y＝＝10 命题整体感知 尝试与研析 出现，出现了x则将a[x]的值设为1，②空为更新n的值(去除末尾)；j循环将列表a中的数值累积到y中，如果每个数字都出现，则y值为10，则密码成立，③空判断y是否与10相等。 命题整体感知 尝试与研析 |随|堂|检|测| 1．某班班主任用班费为班级学生购买了两种错题本，现在要公布班费使用情况，但发现存放时不小心有两滴墨水滴在了收据上，使得部分数据无法识别，如图所示。由于当时没有标注这两种错题本的数量，导致无法计算出总金额。班主任只记得总金额是17的倍数。请计算出总金额及两种错题本可能购买的数量。 实现上述功能的Python程序段如下，请在横线处填入合适的代码。 命题整体感知 尝试与研析 for k in range(0，10)： m＝①_______________ if ②_______________： print(”总金额为： ”＋str(m)) print(”可能购买的数量： ”) for i in range(1，int(m/13＋1))： for j in range(1，int(m/8＋1))： 1401＋k*10 m%17＝＝0 命题整体感知 尝试与研析 if ③___________________： 　　　 print(”错题本1”＋str(i)＋”本，错题本2”＋str(j)＋”本”) 【解析】 通过枚举算法，找出真正的解。①列举金额的取值；②判断m是否为17的倍数；③继续枚举错题本1和错题本2的数量，通过总金额进行验证。 13*i＋8*j＝＝m 命题整体感知 尝试与研析 2．[2024·义乌中学检测]尼科彻斯定理：任何一个大于或等于1 的整数的立方等于一串连续奇数之和，如33＝7＋9＋11。编写一个Python 程序验证尼科彻斯定理，执行程序后，输入一个大于或等于1 的整数，输出的验证结果如图所示： 请回答下列问题。 (1)若输入数字2，则输出的结果是________________。 2**3＝3＋5 命题整体感知 尝试与研析 (2)实现该功能的Python程序段如下，请在横线处填入合适的代码。 n＝int(input(”请输入一个大于或等于1 的整数： ”)) for i in range(1，n**3＋1，2)： sum1＝0 t＝i while sum1<n**3： ①_________________ sum1＋＝t 命题整体感知 尝试与研析 t＋＝2 if sum1＝＝n**3： break s＝str(n)＋”**”＋str(3)＋”＝” while sum1>0： sum1－＝i if ②________________： sum1＝＝0 命题整体感知 尝试与研析 　s＋＝str(i) else： 　　　s＋＝str(i)＋”＋” i＝③___________ print(s) 【解析】 (1)整数的立方等于一串连续奇数之和，23＝8＝3＋5。 (2)i的取值范围是1到n**3之间的奇数。t从i开始，每次加2，累加到sum1 i＋2 命题整体感知 尝试与研析 中；如果条件sum1＝＝n**3成立，则满足条件；接着i开始输出连续奇数。 命题整体感知 尝试与研析 3．[2024·绍兴鲁迅中学检测]对于一个长度为10 的随机整数列表，如果给定一个区间[st，en]，可以通过循环求出区间之和，代码如下，运行结果如图1 所示： import random #uniform(x，y)的功能是生成[x，y]区间内的随机实数，lis 为包含10 个 图1　 命题整体感知 尝试与研析 随机数的列表 lis＝[int(random.uniform(－10，10)) for i in range(10)] print(lis) st＝int(input(”请输入区间起点： ”)) en＝int(input(”请输入区间终点： ”)) summ＝0 for i in range(st，en＋1)： 命题整体感知 尝试与研析 summ＋＝lis[i] print(”区间之和为： ”，summ) 请回答下列问题。 (1)对于如图1 所示的列表，区间[7，9]的和为_______。 (2)但当要查询的区间变多时，每一次计算都需要执行一次循环语句，小杜认为可以用求和的方式存储区间[0，k]之和，再通过减法计算目标区间之和。例如，区间[0，en]之和减去区间[0，st]之和就是区间[st＋1，en]之和。请在横线处填入合适的代码，实现该功能。 －5 命题整体感知 尝试与研析 import random lis＝[int(random.uniform(－10，10)) for i in range(10)] he＝[0]*10 for i in range(len(lis))： he[i]＝①___________________ #he[i]存储区间[0，i]之和 while True： st＝int(input(”请输入区间起点： ”)) he[i－1]＋lis[i] 命题整体感知 尝试与研析 en＝int(input(”请输入区间终点： ”)) print(”区间和为： ”，②____________________) 掌握了该方法后，小杜打算利用程序计算给定区间中哪个子区间(规定子区间的起点大于0，终点小于9)的和最大，期望的运行结果如图2 所示，实现该功能的程序段如下。 he[en]－he[st－1] 图2 命题整体感知 尝试与研析 #列表的生成与区间和的计算略，其中区间[0，i]的和存放在he[i]中 st＝int(input(”请输入子区间起点(大于0): ”)) en＝int(input(”请输入子区间终点(小于9): ”)) max_st＝st max_en＝en for i in range(st，en＋1)： 命题整体感知 尝试与研析 for j in range(i，en＋1)： 　temp_sum＝he[j]－he[i－1] 　if temp_sum>max_sum： max_st，max_en＝i，j max_sum＝temp_sum print(”最大子区间之和为： ”，max_sum，”，起点为”，max_st，”，终点为”，max_en) 命题整体感知 尝试与研析 (3)该算法属于______(单选，填字母：A.枚举算法；B.解析算法)。 (4)上述程序段中加框处代码有误，请改正： ______________________________。 【解析】 (1)[0，9，－8，－1，1，2，－2，－5，1，－1] 　　　　　0　1 　2　　3　4 5 　6　 7　8　9 区间[7，9]的和为－5＋1－1＝－5 (2)①he[i]存储区间[0，i]之和，则当前项h[i]的累积值为前一项的累积值 A max_sum＝he[en]－he[st－1] 命题整体感知 尝试与研析 与当前项之和；②区间[0，en]之和减去区间[0，st－1]之和就是区间[st，en]之和。 (3)逐个判断每个子区间之和，找出值最大的区间，属于枚举算法。 (4)利用循环罗列各个子区间，再比较查找和的值最大的子区间，则max_sum应该为整个子区间的和。 温馨提示：请完成高效作业11 感谢聆听，再见！ ＋＋…＋ 【解析】 (1)关键字“一一列举、逐一验证”，属于枚举算法。 (2)用于是否是真正的解，需要使用分支结构来判断是否符合丙的说法。 (3)根据流程图设计程序，①将的整数部分存入C中；②通过分支结构判断是否符合丙的说法。 $$