资源简介

(共20张PPT)
4.1算法及其特征
《软件社团纳新-探讨面试解决方案》
教师：***
01
知识回顾
01
知识回顾
算法是什么
01
知识回顾
流程图大作战
游戏规则
九宫格底下藏有流程图图例或基本结构的照片，小组抢答选择卡片数字，老师点击该卡片，卡片就会消失在荧幕上，猜出照片上的知识即可获胜。回答错误，继续抢答回答问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
项目自主探究
02
02
一个房间有3盏灯，房间外有3个开关分别控制这3盏灯。在只允许进房间一次的情况下，如何判断哪个开关控制哪盏灯
寻找“开关对应关系”
02
寻找“开关对应关系”
一个房间有3盏灯，房间外有3个开关分别控制这3盏灯。在只允许进房间一次的情况下，如何判断哪个开关控制哪盏灯
提示：
1.一盏打开的灯，视觉上来看，灯的状态是（ ）的；触觉上来看，灯的状态是（ ）的。所以，一盏灯有（ ）种状态。
2.如何使3盏灯处于不同的状态？请用自然语言描述你的算法：
第一步：
第二步：
第三步：
第四步：
亮/暗
冷/热
4
为开关和灯分别编号
开1号、2号两个开关，2分钟后关闭1号开关
进入房间，亮着的灯由2号开关控制
触摸不亮的灯，发热的由1号开关控制，不发热的灯由3号开关控制
该算法用到哪种结构？
02
寻找“开关对应关系”
关闭1号开关
灯亮
2号开关控制
发热
1号开关控制
3号开关控制
算法的特征
根据解决方案，判断下列算法特征的描述是否正确？
算法必须能在执行有限个步骤之后终止。
算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。
算法一定要有输入。
算法可以没有输出。
算法中的运算都必须是可以实现的。
有穷性
确切性
算法有0个或多个输人，0个输人是指算法本身给出了初始条件
输入项
算法一定要有输出。任何算法都不能“无功而返”。
输出项
可行性
02
寻找“被污染的药丸”
有4个装了药丸的瓶子，每颗药丸都有单颗标准质量，其中一个药瓶中所有药丸被污染了。每颗被污染药丸比污染前增重1克。只允许称量一次，判断出哪个瓶子的药被污染了。
1.1颗药丸被污染增重为1克,增重量为n克说明（ ）颗药丸被污染；
2.从1-4号药瓶依次取1-4颗药丸，共取出（ ）颗药丸；
3.设每颗正常药丸重d克，取出的药丸污染前总重（ ）克；实际称量取出的所有药丸重w；则比污染前增重x=（ ）克。
结论：被污染的药瓶序号为（ ）。
n
10
10d
w-10d
w-10d
02
寻找“被污染的药丸”
思考该问题中哪些信息属于输入，哪些信息属于输出？
输入：每颗正常药标准重量d、所有药丸重量w
输出：药瓶的序号w-10d
打开“寻找污染药丸.py”，补全并调试运行
d=int(input(“请输入每颗药丸的标准重量：”))
w=int(input(“请输入药丸称得的重量：”))
x=
print(“被污染的药瓶序号是：”,x)
input(“运行完毕，请按回车键退出.......”)
w-10d
注：10d 或 10*d；w的范围
对要解决的问题进行详细的分析，弄清楚问题的要求，包括需要输入什么数据，要得到什么结果，最后应输出什么。
分析问题
解决一个问题，可能有多种算法。例如,数学题常常有“一题多解”，应该通过分析、比较、挑选-种最优的算法。
设计算法
计算机只能接受并执行计算机程序设计语言编写的程序。当为解决一个问题确定了算法后，还必须将该算法用计算机程序设计语
言编写程序。这个过程成为“编码”或“编程”。
编写程序
编写完成的程序，不一定完全符合实际问题的要求，还必须在计算机上运行这个程序，排除程序中可能出现的错误，才能得到结果。
调试与维护
计算机解决问题过程
02
寻找“被污染的药丸”
02
寻找“误删的ID号”
学校历届校友的数据存储在校网络中心服务器中（共10000条），管理人员误删了一位校友的ID号（8位正数）。恰好在备份数据库中保存了一份所有人员ID号的文件（无重复、无序）。怎样快速找出被误删的ID号以便恢复数据？
活动要求：小组讨论，并展示方案。
1.数学建模：参与分析及处理的数据是ID号，其特征是无序，整数类型、8位、共10000个；ID号在校网络中心服务器中有（）条，备份数据库中有（）条；
2.设计算法
第一步：
第二步：
3.编写程序：打开“寻找被误删的ID号.py”,补全并调试运行
1.数学建模：参与分析及处理的数据是ID号，其特征是无序，整数类型、8位、共10000个；ID号在校网络中心服务器中有（ ）条，备份数据库中有（ ）条；
2.设计算法
第一步：
第二步：
第三步：
3.编写程序：打开“寻找被误删的ID号.py”,补全并调试运行
02
寻找“误删的ID号”
9999
10000
读取备份文件数据，求和
读取故障文件数据，求和
备份文件数据总和和-故障文件数据总和，结果即为被误删的ID号
02
寻找“误删的ID号”
瓶依
sum1=0 #设置初始值
sum2=0 #设置初始值
f1=open(r"copy.txt") #打开备份文件
list1=f1.readlines() #读取每行数据
for line in list1: #依次处理列表list1中的数据
sum1= sum1+int(line) #将读取的数据做求和运算
f1.close #关闭备份文件
#打开故障文件
list2=f2.readlines() #按行读取故障文件
for line in list2: #依次处理列表list2中的数据
sum2= sum2+int(line) #将读取的数据求和运算
#补全关闭备份文件
print("被删除的ID号是:", ) #补全输出被删除的ID号
input(“运行完毕，请按回车键退出.......”)
f2.close
f2=open(r"trouble.txt")
sum1-sum2
03
课堂小结
03
课堂小结
自然语言、流程图、程序语言
算法的描述方法
分析问题、设计算法、编写程序、调试与维护
程序设计基本流程
解决问题的方法与步骤
算法的概念
有穷性、确切性、输入项、输出项、可行性
算法的特征
03
课后作业
思考软件社团面试第三问的不同解决方案，并尝试根据自己的解决方案，编写程序代码。
下节课再见！

展开更多......

收起↑