第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 = 2
else:
s = 2 + (n - 1) * 0.8
print("费用(元): ", 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 = i
a = x % 10
x = ___2___
b = x % 10
c = x // 10
if ( ___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)
break
n += 1
参考代码(2):
n = 16
while True:
if n % 5 == 2:
break
n += 9
while True:
if n % 4 == 1:
break
n += 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