第15课 算法（上）
理解算法的概念，掌握解析、枚举、排序、查找算法的特征。能够用这些算法实现简单的Python程序。
一、算法与算法的表示
（一）、使用计算机解决问题的一般过程
1、使用计算机解决问题，一般分为3个阶段
（1）分析问题，建立模型。在解决问题之前，要对问题有清晰的描述和分析。描述的问题必须具备3个特征：指明定义问题范畴的所有假设；清晰的说明已知信息；说明何时解决问题，并根据分析情况构建数学模型。
（2）设计算法。确定让计算机怎么做，这是整个过程中的核心部分。
（3）实现算法并验证结果。用计算机运行设计好的算法程序解决问题，并对结果进行检测、分析和验证。
2、程序由以下两部分构成（1）指令部分。指令是为控制计算机操作而做出的一组符号，每条指令可以控制计算机执行一个操作。由若干条指令适当组成的序列，也就是“程序代码”，描述了解决问题的具体过程。
（2）数据部分。包括计算所需要的原始数据、计算的中间结果以及最终结果。
3、设计程序时，需要考虑以下问题
（1）数据的存储。计算所需的原始数据、中间产生的数据、以及最终结果需要存放在不同的变量中。
（2）计算的过程。首先确定解决问题的方法，接着把该方法步骤化，并用计算机能够实现的指令来实现对应的步骤。
（二）、算法及算法的表示
1、算法的概念
算法就是对解题方法的精确且完整的描述，即解决问题的方法和步骤。
2、算法的特征
（1）有穷性：执行步骤是有限的。
（2）确定性：每个步骤的含义是确切的。
（3）可行性：每个步骤是可行的，并且在有限的时间内完成。
（4）有0个或多个输入：初始数据可从外界输入，也可含于算法之中。
（5）有1个或多个输出：算法一定要有结果且以一定方式输出。
3、算法的3种表示
（1）自然语言。自然语言是指人们日常生活中使用的语言，它通俗易懂，但缺乏直观与简洁，容易产生歧义。
（2）流程图。流程图也叫作“程序框图”，它是算法的一种图形化表示方法。与自然语言相比， 它描述的算法直观、形象，更容易理解。
（3）常用的流程图组件有以下几种：处理框（长方形）：框中需指出要处理的内容，该框有一个输入和一个输出；输入/输出框（平行四边形）：用来表示数据的输入或计算结果的输出；判断框（菱形）：用来表示分支情况，一个输入，一个及以上输出；连接框（圆形）：用来连接画不下而中断的流程线；流程线（箭头）：用来指出流程控制方向，即程序走向；起始框（椭圆形）：用来表示程序的开始或结束。
（4）程序设计语言。程序设计语言就是也就是我们常说的“编程语言”。常见的编程语言有Scratch、Python、C++、Java、PHP等。
4、算法的3种基本结构
（1）顺序结构。在算法执行流程中，执行完一个步骤之后，依次执行下一个步骤。
（2）选择结构。也称分支结构或判断结构。在算法执行过程中，对某个情况e进行判断，如果结果为真，执行Y分支；否则，执行N分支。
（3）循环结构。在算法执行过程中，对某个情况e进行判断，当结果为真时，执行Y指向流程线下的步骤；然后再次判断e的情况，如果结果还为真，继续执行Y执行流程线下的步骤，并继续判断情况e的真假；重复上述步骤，直到情况e的结果为假，执行N指向流程线下的其它语句（即：跳出循环）。
二、解析算法
如果告诉你一个具体日期，你能算出这一天是星期几吗？
除了查看日历，我们还可以使用基姆拉尔森进行计算：
W = (D +2M + 3(M+1)/5 +Y + Y/4 - Y/100 + Y/400) mod 7
W表示4位数字的年，M表示月，D表示日。
注意：
（1）该公式中，要把1月和2月分别当做上一年的13月和14月处理，例如：2024年1月16日要换成2023年13月16日之后再代入公式；
（2）该公式的运行结果与星期几的对应关系为：0代表星期日、1代表星期一、6代表星期六。
1、解析算法的概念
（1）解析：用数学公式描述客观事物之间的数量关系。
（2）解析算法：用解析的方法找出表示问题的前提条件与结果之间的数学表达式，并通过表达式的计算来实现问题的求解。
例如：计算以速度v做匀速直线运动的一个物体，在t秒内经过的距离s，则可通过公式 s = vt 得到。
2、解析算法的程序实现
（1）建立正确的数学模型（确立正确的数学计算公式）。
（2）将数学表达式转换为Python表达式。
用Python编制解析算法程序时，必须要保证计算过程描述的正确性。
3、示例演示
某书店出租图书的收费标准如下：借书1天内，收费2元；借书超过1天的，超过部分按照每天0.8元收费。最后费用按照四舍五入折算成整数。程序算法如下图所示：
参考代码：
n = eval(input("请输入借书天数"))
if not n < 1:if n == 1:s = 2else:s = 2 + (n - 1) * 0.8print("费用(元): ", round(s))
else:print("输入有误！")
三、枚举算法
有一张模糊的单据，上面有一个5位数的编号，其百位和十位上的数字无法辨认，如下图所示。但是，直到这个5位数是37或67的倍数。请你编写程序，找出所有满足条件的5位数，并统计这些5位数的个数。
1、枚举算法的概念
枚举算法又叫穷举算法，其基本思想是把问题所有的解一一罗列出来，并对每一个可能得解进行判断，以确定这个可能的解是否为问题的真正解。若是，就采纳这个解，否则就抛弃它。即使中途已经找到了符合的解，也要继续找下去，将所有可能都找完才结束。
2、枚举算法的程序实现
（1）列举与检查过程，既不重复也不遗漏。
（2）尽可能的使可能解的范围最小，以提高解决问题的效率。
（3）用循环语句（for语句）在一定范围内列举所有可能解。
（4）用选择语句（if语句）判断和选择真正的解。
3、枚举算法的一般格式
循环结构（for 语句）：
循环体内判断（if 语句）
4、示例演示
陈萍萍忘记了支付宝密码，他急需在30分钟内完成货款支付，请用Pytho编程帮他找回密码。他零星记得自己的支付密码信息：（1）密码是6位数字，前面两位是85；
（2）最后两位数字相同；
（3）能被13和33整除。
参考代码：
for i in range(10000):
s = 850000 + i
if s % 13 == 0 and s % 33 == 0:
a = s % 10
b = s // 10 % 10
if a == b:
print(s)
四、模拟考题
(一）单选题：
1、小杨同学在研究某项课题时搜集了很多数据，她想写一个简单计算机程序来统计、分析这些数据，则实现这一过程的一般步骤为（ ）。
A、分析问题、设计算法、编写程序、调试运行程序
B、编写程序、分析问题、设计算法、调试运行程序
C、编写程序、调试运行程序、分析问题、设计算法
D、设计算法、调试运行程序、编写程序、分析问题
2、下列是用计算机解决“计算圆周率”问题的几个步骤，正确序列是（ ）
（1）编写计算机程序，用计算机进行处理
（2）分析问题，确定计算机解题任务为“计算圆周率”
（3）构建数学模型，设计算法
A、1 2 3
B、3 1 2
C、2 1 3
D、2 3 1
3、计算圆面积的算法描述如下：
（1）输入圆的半径r
（2）计算圆的面积S
（3）输出结果
（4）结束
上述描述算法的方法属于（ ）。
A、流程图
B、伪代码
C、自然语言
D、机器语言
4、以下关于算法描述错误的是（ ）。
A、算法必须在有限的步骤内完成
B、算法每个步骤的含义必须是确切的
C、算法必须要有输入，但可以没有输出
D、算法可以没有输入，但必须要有输出
5、计算长方体体积的算法描述如下：
（1）输入长方体的长（z）、宽（w）、高（h）
（2）计算长方体体积 v = zwh
（3）输出结果
（4）结束
上述算法属于（ ）。
A、枚举算法
B、排序算法
C、解析算法
D、递归算法
6、下列问题适合用解析算法的是（ ）。
A、将13张纸牌按照从小到大的顺序排列
B、统计100以内，各位数字总和恰好为10的偶数的个数
C、计算一辆汽车行驶100千米的油耗
D、寻找本年级身高最高的同学
7、有如下问题：
（1）已知圆柱体的半径r和高度h，使用公式V = πr²h 求出此圆柱体积。
（2）已知班级中每位同学的期中考试成绩总分为s，按照s的值从大到小的顺序进行成绩排名。
（3）已知圆的周长为s，利用公式r=s/(2π)求半径r。
属于解析算法的是（ ）。
A、1， 2
B、1， 3
C、3， 4
D、2， 4
8、出租车计价规则：3千米以内，收费10元；超出3千米，每千米加收2元。假定千米数为x，收费金额为y。解决此问题的公式和流程图如下所示：
流程图加框内部分的算法属于（ ）。
A、解析算法
B、排序算法
C、枚举算法
D、递归算法
9、问题如下图所示，用计算机解决该问题，比较适合使用（ ）。
A、排序算法
B、枚举算法
C、解析算法
D、查找算法
10、用50元钱兑换面值为1元、2元、5元的纸币共25张。每张纸币不少于1张，请问有多少种兑换方案。求解这个问题，最合适的算法是（ ）。
A、排序算法
B、递归算法
C、枚举算法
D、解析算法
11、如果一个自然数恰好等于它的因子之和，这个数就称为“完全数”。例如：6就是一个“完全数”，因为6的因子为1、2、3，而6=1+2+3。设计一个算法找出1000以内所有的“完全数”，那么求解这个问题，主要使用到的算法是（ ）。
A、递归算法
B、排序算法
C、解析算法
D、枚举算法
12、下列问题适合使用枚举算法解决的是（ ）。
A、计算本月的电费
B、计算全班男同学的平均身高
C、查找100以内所有能被2和3整除的整数
D、200米短跑比赛成绩排名
13、用枚举算法求解“找出所有满足各位数字之和等于7的三位数”时，在下列所有列举的数值范围内，算法执行效率最高的是（ ）。
A、0~999
B、100~999
C、100~700
D、106~700
(二）判断题
1、使用计算机解决问题的一般过程是：设计算法、调试运行程序、编写程序、分析问题。（ ）
2、质数是指在大于1的自然数中，除了1和它本身以外，不再有其它因数的自然数。小明想编写程序求出1~2000之内的质数的个数，他应采用解析算法。（ ）
(三）编程题
1、有一盒乒乓球，9个9个的数，最后余下7个；5个5个的数，最后余下2个；4个4个的数，最后余下1个。问这盒乒乓球至少有多少个？
2、小明请你帮忙寻找100~999的所有“水仙花数”，并统计个数。“水仙花数”是指各位数字的立方和等于该数本身的3位数，例如：153=111 + 555 + 333。要求输出结果如下所示：
153
360
361
407
请编写程序实现上述功能，或补全代码。
for i in range( ___1___ ):x = ia = x % 10x = ___2___b = x % 10c = x // 10if ( ___3___ ):print(i)
3、把1296拆分成a、b、c、d四个正整数，如果a加上2，b减去2，c乘以2，d除以2，则4个结果相等。现在请你编写程序，求出这四个数。补全下面的代码：
for a in range(1, ___1___ ):b = ___2___for c in range(1, 1296-a-b):d = ___3___if (b-2 == c*2) and (a+b+c+d == ___4___ ):print(a, b, c, d)
–>参考答案往下翻<–
–>参考答案<–
一、单选题:
1~5：A、D、C、C、C
6~10：C、B、A、A、C
11~13：D、C、D、
二、判断题：
1~2：✘、✘
三、编程题：
1、参考代码（1）：
n = 16
while True:if n % 9 == 7 and n % 5 == 2 and n % 4 == 1:print(n)breakn += 1
参考代码（2）：
n = 16
while True:if n % 5 == 2:breakn += 9
while True:if n % 4 == 1:breakn += 45
print(n)
2、参考答案：
（1）100, 1000 （或等效答案）
（2）x // 10 （或等效答案）
（3）a3 + b3 + c**3 == i （或等效答案）
3、参考答案：
（1）1296
（2）a + 4
（3）c * 4
（4）1296