资源简介

4.1算法及其特征
第4单元 计算与问题解决
学 习 目 标
3.运用恰当的方式描述算法。
2.了解算法的基本要素和重要特征。
1.熟悉将解决问题的方法归结为一系列清晰、准确的步骤的过程。
4.运用Python语言实现简单算法，解决问题，
了解算法的基本要素和重要特征。（重点）
运用Python语言实现简单算法，解决问题，（难点）

面试第一题：“一个房间里有3盏灯，房间外有3个开关分别控制这3盏灯，在只允许进房间一次的情况下，如何判断哪个开关控制那盏灯？
任务一 活动1 寻找“开关对应关系”(P86-P87)
图4.1.1 开关对应关系
第一步：
第二步：
第三步：
第四步：
第五步：
小组讨论后，写出步骤：
第一步：打开1、2两个开关
第二步：过2分钟后关闭1号开关
第三步：进房间，亮着的灯是由2号开关控制
第四步：摸一下另外两盏不亮的灯，发热的灯泡是由1号开关控制
第五步：不亮又不热的灯是由3号开关控制
步骤如下：
完善“开关对应关系”流程图
关1号开关
灯亮？
灯热？
该灯由2号开关控制
该灯由1号开关控制
该灯由3号开关控制
1. 有穷性
算法必须能在执行有限个步骤后终止。
2. 确切性
算法中的每次运算都有明确的定义，具有无二义性，并且可以通过计算得到唯一的结果。
3. 输入项
一个算法有0个或多个输入，所谓0个输入是指算法本身给出了初始条件。
4. 输出项
算法一定要有输出。至少产生一个输出。
5. 可行性
算法中执行的任何计算都可以在有限时间内完成（有效性），算法中的运算都必须是可以实现的。
算法的特征
算法描述：3种
用自然语言描述算法
用流程图描述算法
代码描述算法
For I=1 to N
if n能被3、5、7整除余数为2、3、2
then
输出n
exit for
end if
next
For I=1 to N
if n能被3、5、7整除余数为2、3、2
then
输出n
exit for
end if
next
面试第二题：有4个分别装了4种药丸的药瓶，每颗药丸都有单颗标准质量，其中有一个药瓶中的所有药丸都被污染了。每颗被污染的药丸比正常药丸增重1克。只允许称量一次，请判断出哪个药瓶中的药被污染了。互相讨论该问题的解决步骤，试将P89横线补充完整。
任务一 活动2 寻找“被污染的药丸”(P88-P89)
任务一 活动3 寻找“误删的ID号”(P89-P90)

面试第三题：学校历届校友的数据存储在学校网络中心服务器中(共10000条，无重复数据)，某管理员由于误操作删除了一位校友的ID号(8位整数)。恰好在备份文件中保存了所有人员的ID号(无重复数据，无序)。怎样快速找出被误删的ID号以便恢复数据?
误删的 号的流程图
ID
target=0 #设置初始值f1=open(r"copy.txt") #打开备份文件list1=f1.readlines() #读取每行数据for line in list1: #依次处理列表list1中的数据 target= target^int(line) #将读取的数据做异或运算f1.close #关闭备份文件f2=open(r"trouble.txt") #打开故障文件list2=f2.readlines() #按行读取故障文件for line in list2: #依次处理列表list2中的数据 target= target^int(line) #将读取的数据做异或运算f2.close #关闭备份文件print("被删除的ID号是:", target) #输出被删除的ID号
根据流程图及提示信息补充P90代码，结果如下:
这次面试的冠军在A、B、C、D四位同学中。A说：“不是我。”B说：“是C。”C说：“是D。”D说：“C说的不对。” 已知四人中有一人说了假话。你能判断到底谁是冠军吗？
任务二 求解“谁是冠军”
枚 举
解析：利用枚举法，逐一假设A、B、C、D是冠军，判断是否正确。
{FABFCF23-3B69-468F-B69F-88F6DE6A72F2}冠 军
A说：“不是我。”
B说：“是C。”
C说：“是D。”
D说：“C说的不对。”
A
×
×
×
√
B
√
×
×
√
C
√
√
×
√
D
√
×
√
×
枚 举
用程序求谁是冠军时，我们需要把每个人说的话转化成计算机能够执行的表达式。如A说：“不是我。”可以表示为“i!='A'”，其中i为枚举的冠军选手编号。
枚 举
分析以下代码的含义，理解解题思路，并在横线上填写语句的功能。
champion=['A','B','C','D'] #设置选手列表
for i in champion: #______________________________
cond=(i!='A')+(i=='C') + (i=='D')+(i!='D') #___________________
if cond==3:
print("冠军是:",i)
枚 举
请在Python中输入代码并运行程序，看看谁是冠军。
答案 冠军是: C
枚 举
有一种算法是把所有可能的答案一一列举，合适就保留，不合适就丢弃。这种方法称作“枚举”或“穷举”。
枚举法解决问题的一般结构：循环+判断。
优势：易证明正确性
枚 举
1. 找出三位正整数中能被7整除的整数。
参考答案：
for i in range(100,1000):
if i%7==0:
print(i)
巩固提升
2. 在一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”。即一个数除以3余2，除以5余3，除以7余2，求这个数。
参考答案：
i=0
while (i%3!=2 or i%5!=3 or i%7!=2):
i=i+1
print(i)
巩固提升

展开更多......

收起↑