导读
信息学能够有助于孩子未来工作发展,提升孩子的综合能力。
这一期课,我们继续深入学习数据结构和算法,学的更深,学的更多!在此之前,我们需要先掌握好上一期的课程,打好基础,再深入这一期课程,这一节课,我们一起来简单回顾上一期课的一些重点内容。
1 基础数据结构回顾
首先我们先来复习一下数据结构吧。
1 数据结构总述
在前面的内容中,我们学习了数据结构的相关概念,学习了一些基础的线性结构,包括:
接下来,让我们一起来详细复习一下重点内容吧!
2 线性结构总结
1、顺序表
顺序表是最基本的线性结构,我们经常用数组来描述它。但是顺序表又和普通数组不一样,顺序表和普通数组的差别在如下几个方面:
顺序表的优缺点如下:
我们可以使用STL库中的vector数组来实现顺序表。
我们可以通过如下几篇文章,深入学习顺序表:
数据结构前导课 | 4 初试锋芒——顺序表写起来也很简单
数据结构前导课 | 5 小试牛刀——STL库之vector数组
2、链表
链表是线性表使用链式存储的经典代表,其优缺点如下:
链表主要有单链表、双向链表和循环链表:
链表更多的是出现在信息学初赛中的理论分析,在复赛中很少使用。真正使用,也是使用数组和索引去模拟链表。在STL库中,也提供了list链表供大家使用。
具体大家可以看如下的文章去复习:
数据结构前导课 | 6触类旁通——链表基本理论与信息学竞赛必考点
数据结构前导课 | 7 更进一步——STL库之List链表
3、栈
栈是一种受限制的线性表,只能在一端插入与删除,不能在另一端做操作。栈是先进后出的结构。
在STL库中,我们提供了stack来实现栈。栈最常用的操作就是获取栈顶元素,入栈和出栈。
具体请看:
4、队列
队列是一种受限制的线性表,普通队列只能在一端插入,另一端删除。栈是先进先出的结构。
在一些特定场景,会有一些特殊的队列,例如双端队列可以实现在两端的插入和删除。循环队列可以解决普通队列中出队导致空间浪费的问题。
在STL库中,我们提供了deque来实现双端队列。提供queue来实现普通队列,通过结合取余运算实现循环队列。
具体请看:
5、字符串
作为特殊的线性表,字符串也有其独特的性质,也有独立的方法,包括字符串的插入、截取、删除、获取字符串长度、比较等等。
具体请看:
2 基础算法回顾
接下来让我们回顾一下算法。
1 算法复杂度
算法复杂度是用来衡量算法性能的重要指标,也是信息学竞赛要求的硬性指标。
算法复杂度主要包括时间复杂度和空间复杂度。我们考虑最多的是时间复杂度。
具体请看:
2 排序算法
排序算法是我们很早就接触到的算法,这一期我们系统讲解了所有的排序算法。
1、排序算法的评价指标
排序算法有四个评价指标,除了上面的两个复杂度,还包括稳定性和适用性。
2、排序算法
我们学习了如下排序算法:
3、sort函数
一般来说,在竞赛中,我们直接使用sort函数即可,重点是排序的策略的设置。
排序算法我们通过三节课详细讲解,具体请看:
信息学集训 | 12 排序算法分析与sort函数详解
3 枚举算法
枚举算法是最基本的算法,就是将所有情况列举出来。
枚举算法的优点在于,枚举算法思想简单,并且能遍历所有情况,会找到全局最优解等。不会出现遗漏。
但缺点在于,要遍历所有情况,时间复杂度就会很高。
在竞赛中,如果大家找不到更好地方案,那就是用枚举算法,尽可能获得更高的分数。
具体请看:
4 贪心算法
贪心算法追求的是当前最优,因为不考虑后效性,所以思想比较简单,也容易实现。但是贪心算法在一些问题中难以获得全局最优解。
贪心算法重点是贪心策略的选择,有时候选择好的贪心策略能够得到最优解或者能够让算法性能更高。
具体请看:
5 分治算法
分治算法强调的是三个部分:
并且分治算法要满足如下几方面的原则:
这些原则与上面的三个部分,其实也是分别对应的。
具体请看:
6 高精度算法
上一期课,我们最后学习了高精度算法。高精度算法是上一期课中,算法最难的。不过高精度比较固定,适用范围也较小。
高精度要考虑这么几个问题:
具体请看:
3 算法题目实训
复习完知识,让我们一起来做几道题目吧!
1 求根号2的近似值
【题目】
编写一个算法,求
【分析】
考虑求近似值,可以使用分治-二分法。因为 ,所以我们初始两端为1和2,然后我们找1和2的中间1.5,如果1.5的平方比2大,说明 在1和1.5中间,然后我们找1和1.5的中间1.25……以此类推,直到满足精度要求即可。
【代码】
代码如下:
2 斐波那契数列
【题目】
小明学习了斐波那契数列,想自己设置前两个数,生成对应的序列,现在要你帮小明实现它的想法,并输出前10个斐波那契数列值;
【分析】
我们知道斐波那契数列前两个值是设定的,后面的值满足
【代码】
代码如下:
3 工作时长
【题目】
某工厂有10名员工,现在有项任务,领导要派3个人参加。已知这十名员工每人每天的工作量为 ,任务的总工作量为
注: 和
【分析】
时间最短,那就要效率最高的,也就是使用贪心策略选择三名效率最高的员工。
注意是几天,如果不是整天完成,要向上取整。
【代码】
代码如下:
4 作业
本节课的作业,就是复习上面的所有知识,并完成下面的题目!
1 a+b
实现高精度数据a和b的加法,a和b是整数,可正可负。
AI与区块链技术
长按二维码关注