资源简介

(共19张PPT)
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1 算法及其特征
四、计算与问题解决
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
软件开发社团要招募新成员，报名的同学要经过面试才能加入，面试测试有四个关卡，一起来闯关吧！！
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4
3
2
6
1
5
起止框
表示一个算法的开始与结束
输入/输出框
表示从外部输入数据到计算机内部或者从计算机内部输出数据到计算机.
处理框
表示操作的内容.
判断框
表示判断的条件。满足条件，执行标识为是的路径，反之，执行标识为否的路径.
流程线
连接符
表示流程图的接续。在相互关系的流程图内，流程线将在具有相同字数或字母的另一连接符处继续下去.
60秒准备
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第一关：“寻找开关对应关系”
一个房间有三盏灯，房间外有三个开关分别控制这三盏灯，在只允许进房间一次的情况下，如何判断哪个开关控制哪盏灯？
思考：如何能使3盏灯处于不同的状态？
灯亮
灯灭
发热
不发热
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
①
②
③
思考：如何能使3盏灯处于不同的状态？
4.1算法及其特征
第一关：“寻找开关对应关系”
请完善以下“开关对应关系”流程图（P98图4.1.2)
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
开始
为开关和灯分别编码
开1号、2号开关，等待片刻
进房间
结束
是
是
否
否
关1号开关
该灯由2号开关控制
该灯由1号开关控制
该灯由3号开关控制
灯是否亮
灯是否发热
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
▼算法：
算法可能是一个计算公式，可能是一个赢得游戏的策略，也可能是一个解决综合问题的复杂方案。可以用自然语言、流程图、程序代码来描述。
4.1算法及其特征
1、“开关对应关系” 算法中有（ ）个输出项？
2、“开关对应关系”算法的执行结果是（ ）。
3、“开关对应关系”算法的执行步骤是（ ）。
A.0个
B.1个
C.多个
A.确定的
B.不确定
C.都可以
A.有限的
B.无限的
C.都可以
C
A
A
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
算法一定要有输出，任何算法都不能无功而返。
4、输出性
5、可行性
算法必须能在执行有限个步骤之后终止。
1、有穷性
算法中的每一次运算都有明确的定义，具有无二义性，并且也可以通过计算得到唯一的结果。
2、确切性
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身给出了初始条件。
3、输入性
算法中执行的任何计算都可在有限时间内完成，也称为有效性算法中的运算都必须是可以实现的。
算法
4.1算法及其特征
解决问题的方法和步骤；
描述算法的方法：自然语言和流程图
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第二关：寻找“被污染药丸”
有四个装了药丸的罐子，每个药丸都有一定的重量，其中有一个药罐被污染了。每片被污染的药丸比污染前增重 1 克。只允许称量一次，判断出哪个罐子的药被污染了。
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
如果从每个药瓶中取出一颗药丸分别进行称重，可以不可以判断出哪颗药丸被污染了 这样做符合条件吗？
注意：
讨论时间为3分钟，题目条件是“只能称量一次”。
①
②
③
④
4.1算法及其特征
第二关：寻找“被污染药丸”
定量分析
考虑1颗药丸的重量变化，如果药丸被污染，则增重 g，否则增重 g。
从某一个药瓶中取出n颗药丸，如果被污染，则增重 g，否则增重 g。
1
0
n
0
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
定量分析
如果我们从不同的药瓶中取出不同颗数的药丸：
如果增重 3g，则 号药瓶中的药丸被污染。
如果增重 g， 则 号药瓶中的药丸被污染。
n
n
①
②
③
④
4.1算法及其特征
第二关：寻找“被污染药丸”
取1颗 取2颗 取3颗 取4颗 ，共10颗药丸。
3
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
加时赛
回顾算法的特点，思考一下，在这个问题中，哪些信息属于输入、哪些信息属于输出呢？
请设计程序并运行，使输入10颗药丸的总重量及4种药丸的单颗准质量就可以看到结果，找到被污染的药丸。
d=int(input('请输入每颗药丸的标准重量：'))
w=int(input('请输入药丸称得的重量：'))
x=w-10*d
print('被污染的药瓶序号是：',x)
input("运行完毕，请按回车键退出...")
现象（可多选） 算法的特征
输入项： □0个输入 □1个输入 □多个输入
输出项： □0个输出 □1个输出 □多个输出
执行的结果：□确定的 □不确定的 □都可以
执行的步骤：□有限 □无限 □都可以
执行的时间：□有限 □无限 □都可以
0个或多个
输入
一定有输出
确切性
有穷性
可行性
√
√
√
√
√
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第三关 运用巧算，寻找“误删的ID号”
学校历届校友的数据存储在学校网络中心服务器中（共10000条，无重复数据），某管理员由于误操作删除了一位校友的ID号（8位整数）。恰好在备份文件中保存了所有人员的ID号（无重复数据，无序）。
怎样快速找出被误删的ID号以便恢复数据？
归纳ID号的特征
数据类型及大小范围：
数据在两个文件中出现的次数：
备份文件中ID号总和与故障文件中的ID号总和的差值为：
通过分析，发现计算备份文件中ID号总和与故障文件中的ID号总和的差值就是：
整型（int）
2次
被删除的ID
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第三关 运用巧算，寻找“误删的ID号”
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
4.1算法及其特征
第四关 求解“谁是冠军 ”
不是我
是C
是D
C说的不对
A
B
C
D
有一人说了假话。你能判断出到底谁是冠军吗？
枚举(穷举)法
把所有可能的答案一一列举，合适就保留，不合适就丢弃。
# 遍历champion列表
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
第四关 求解“谁是冠军 ”
4.1算法及其特征
1、枚举法：称为穷举法，是利用计算机运算速度快、精确度高的特点，把所有可能的答案一一列举，合适就保留,不合适就丢弃。
2.枚举法解决问题的一般结构:循环+判断。（确定穷举范围+确定验证条件）
3.枚举法需要逐一验证所有的可能情况，运算量比较大，解决问题的效率不够高。因此，使用枚举法解决问题时，需要考虑优化算法，选择恰当的枚举对象，尽量分析出问题中的隐含条件,缩小枚举范围，以提高解决问题的效率。
# 遍历champion列表
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
1、历经中外科学家姜长英、藤村幸三郎、清水达雄、马丁加达纳等几十年的努力，游戏解法已由六十多年前的87步减少至81步。
2、美国一个律师托马斯.莱曼(Thomas B.Lenann)发现一个新的解法，由加德纳公布在1964年3月《科学美国人》上，有81步，称加德纳解法。
3、华容道的最快走法在中国是100步，在日本是82步。后来美国人用计算机，使用穷举法找出了最终解法，不可能有再快的解法了，81步。美国人在用计算机找到最终解法后，跟中国人开玩笑说美国一位著名的博士找到了最终解法，这位博士名叫computer。
华容道
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
小结：算法的特征
有穷性
确切性
输出项
可行性
输入项
算法必须能在执行有限个步骤之后终止。
算法中的每一次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。
算法一定要有输出。任何算法都不能 “无功而返＂ 。
输入项。一个算法有0个或多个输入，以刻画运算对象的初始悄况，所谓0个输入是指算法本身给出了初始条件。
算法中执行的任何计算都可以在有限时间内完成（也称为 有效性）。
惊艳你的
世界
The future is coming and The future is coming
THANKS
THANKS
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276

展开更多......

收起↑