当前位置: 首页 > article >正文

第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


http://www.kler.cn/a/370537.html

相关文章:

  • 【Unity3D】利用Hinge Joint 2D组件制作绳索效果
  • 微透镜阵列精准全检,白光干涉3D自动量测方案提效70%
  • SQL ON与WHERE区别
  • OpenCV相机标定与3D重建(60)用于立体校正的函数stereoRectify()的使用
  • 构建优雅、高效的 Nodejs 命令行工具 - Archons
  • Vue.js组件开发-实现输入框与筛选逻辑
  • 海外学子如何玩转反向代购,解锁财富密码!
  • 数据库的开发---实训报告
  • React Intl 的工作原理
  • Knife4j配置 ▎使用 ▎教程 ▎实例
  • Peach-9B-8k-Roleplay模型部署指南
  • 利用Kubernetes原生特性实现简单的灰度发布和蓝绿发布
  • 为什么架构设计禁止IP直连?
  • 网管平台(进阶篇):网管软件的配置方式
  • 数据库产品中SQL注入防护功能应该包含哪些功能
  • Golang | Leetcode Golang题解之第515题在每个树行中找最大值
  • Android 相机CameraX框架
  • 【面试】rabbitmq的主要组件有哪些?
  • 什么是时间戳?怎么获取?有什么用?
  • Django入门教程——用户管理实现
  • MySQL的权限系统
  • 【含文档】基于ssm+jsp的房屋租赁管理系统(含源码+数据库+lw)
  • 数字IC开发:布局布线
  • 动手学深度学习9.6. 编码器-解码器架构-笔记练习(PyTorch)
  • SQL Server 中,将单行数据转换为多行数据
  • 深度学习-BP算法详解