导读
信息学能够有助于孩子未来工作发展，提升孩子的综合能力。
这一期课，我们继续深入学习数据结构和算法，学的更深，学的更多！在此之前，我们需要先掌握好上一期的课程，打好基础，再深入这一期课程，这一节课，我们一起来简单回顾上一期课的一些重点内容。
1 基础数据结构回顾
首先我们先来复习一下数据结构吧。
1 数据结构总述
在前面的内容中，我们学习了数据结构的相关概念，学习了一些基础的线性结构，包括：
普通线性表：顺序表、链表
受限制的线性表：栈、队列
特殊线性表：
接下来，让我们一起来详细复习一下重点内容吧！
2 线性结构总结
1、顺序表
顺序表是最基本的线性结构，我们经常用数组来描述它。但是顺序表又和普通数组不一样，顺序表和普通数组的差别在如下几个方面：
顺序表要包含：数据域、长度、容量
顺序表的容量是可调节的
顺序表的优缺点如下：
【优点】
1、可以实现随机存取，访问数据效率高；
2、只需要定义结构存储数据，占用内存空间小。
【缺点】
1、增删数据时，需要移动大量元素，增删数据效率低；
2、需要计算机内存中有较大的完整空间，无法利用比顺序表容量小的空间，造成大量空间碎片。
我们可以使用STL库中的vector数组来实现顺序表。
我们可以通过如下几篇文章，深入学习顺序表：
数据结构前导课 | 4 初试锋芒——顺序表写起来也很简单
数据结构前导课 | 5 小试牛刀——STL库之vector数组
2、链表
链表是线性表使用链式存储的经典代表，其优缺点如下：
【优点】
1、增删数据时，无需移动元素，增删数据效率高；
2、节点无需相邻，对空间利用率更高。
【缺点】
1、顺序存取，访问数据需要从一个往后顺序寻找，效率低；
2、需要定义额外的空间，存储指向其后续节点的指针，浪费大量空间。
链表主要有单链表、双向链表和循环链表：
链表更多的是出现在信息学初赛中的理论分析，在复赛中很少使用。真正使用，也是使用数组和索引去模拟链表。在STL库中，也提供了list链表供大家使用。
具体大家可以看如下的文章去复习：
数据结构前导课 | 6触类旁通——链表基本理论与信息学竞赛必考点
数据结构前导课 | 7 更进一步——STL库之List链表
3、栈
栈是一种受限制的线性表，只能在一端插入与删除，不能在另一端做操作。栈是先进后出的结构。
在STL库中，我们提供了stack来实现栈。栈最常用的操作就是获取栈顶元素，入栈和出栈。
具体请看：
4、队列
队列是一种受限制的线性表，普通队列只能在一端插入，另一端删除。栈是先进先出的结构。
在一些特定场景，会有一些特殊的队列，例如双端队列可以实现在两端的插入和删除。循环队列可以解决普通队列中出队导致空间浪费的问题。
在STL库中，我们提供了deque来实现双端队列。提供queue来实现普通队列，通过结合取余运算实现循环队列。
具体请看：
5、字符串
作为特殊的线性表，字符串也有其独特的性质，也有独立的方法，包括字符串的插入、截取、删除、获取字符串长度、比较等等。
具体请看：
2 基础算法回顾
接下来让我们回顾一下算法。
1 算法复杂度
算法复杂度是用来衡量算法性能的重要指标，也是信息学竞赛要求的硬性指标。
算法复杂度主要包括时间复杂度和空间复杂度。我们考虑最多的是时间复杂度。
具体请看：
2 排序算法
排序算法是我们很早就接触到的算法，这一期我们系统讲解了所有的排序算法。
1、排序算法的评价指标
排序算法有四个评价指标，除了上面的两个复杂度，还包括稳定性和适用性。
2、排序算法
我们学习了如下排序算法：
1、插入排序：直接插入排序、折半插入排序、希尔排序
2、交换排序：冒泡排序、快速排序
3、选择排序：简单选择排序、堆排序
4、归并排序
5、基数排序
3、sort函数
一般来说，在竞赛中，我们直接使用sort函数即可，重点是排序的策略的设置。
排序算法我们通过三节课详细讲解，具体请看：
信息学集训 | 12 排序算法分析与sort函数详解
3 枚举算法
枚举算法是最基本的算法，就是将所有情况列举出来。
枚举算法的优点在于，枚举算法思想简单，并且能遍历所有情况，会找到全局最优解等。不会出现遗漏。
但缺点在于，要遍历所有情况，时间复杂度就会很高。
在竞赛中，如果大家找不到更好地方案，那就是用枚举算法，尽可能获得更高的分数。
具体请看：
4 贪心算法
贪心算法追求的是当前最优，因为不考虑后效性，所以思想比较简单，也容易实现。但是贪心算法在一些问题中难以获得全局最优解。
贪心算法重点是贪心策略的选择，有时候选择好的贪心策略能够得到最优解或者能够让算法性能更高。
具体请看：
5 分治算法
分治算法强调的是三个部分：
分：是指通过递归不断分解直到子问题可解。
治：是指可以通过某种算法解决子问题。
并：是指将所有子问题的解合并。
并且分治算法要满足如下几方面的原则：
1、问题必须是可分解的；
2、分解得到的子问题应该是同类型问题；
3、子问题必须相互独立；
4、子问题可以继续分解为更小的子问题。（非强制）
5、最小子问题必须是可解的
6、子问题的解能合并为父问题的解，并最终合并为该问题的解。
这些原则与上面的三个部分，其实也是分别对应的。
具体请看：
6 高精度算法
上一期课，我们最后学习了高精度算法。高精度算法是上一期课中，算法最难的。不过高精度比较固定，适用范围也较小。
高精度要考虑这么几个问题：
怎么存储：使用数组输出，然后转化为高精度
怎么输出：按位输出，设置输出函数
怎么运算：要自己写对应的运算算法
具体请看：
3 算法题目实训
复习完知识，让我们一起来做几道题目吧！
1 求根号2的近似值
【题目】
编写一个算法，求
【分析】
考虑求近似值，可以使用分治-二分法。因为 ，所以我们初始两端为1和2，然后我们找1和2的中间1.5，如果1.5的平方比2大，说明 在1和1.5中间，然后我们找1和1.5的中间1.25……以此类推，直到满足精度要求即可。
【代码】
代码如下：
#include<iostream>
using namespace std;
int main(){
float l=1,r=2,m;
while(2-l*l>0.001){
m = (l+r)/2;
if(m*m>2) r = m;
else l = m;
}
cout<<l<<endl;
return 0;
}
2 斐波那契数列
【题目】
小明学习了斐波那契数列，想自己设置前两个数，生成对应的序列，现在要你帮小明实现它的想法，并输出前10个斐波那契数列值；
【分析】
我们知道斐波那契数列前两个值是设定的，后面的值满足
【代码】
代码如下：
#include<iostream>
using namespace std;
int main(){
int a[10];
cin>>a[0]>>a[1];
for(int i = 2;i<10;i++){
a[i] = a[i-1]+a[i-2];
}
for(int i = 0;i<10;i++){
cout<<a[i]<<endl;
}
return 0;
}
3 工作时长
【题目】
某工厂有10名员工，现在有项任务，领导要派3个人参加。已知这十名员工每人每天的工作量为 ，任务的总工作量为
注： 和
【分析】
时间最短，那就要效率最高的，也就是使用贪心策略选择三名效率最高的员工。
注意是几天，如果不是整天完成，要向上取整。
【代码】
代码如下：
#include<iostream>
using namespace std;
int main(){
int a[10],A,t,day;
for(int i = 0;i<10;i++){
cin>>a[i];
}
cin>>A;
for(int i = 0;i<3;i++){
for(int j = i+1;i<10;i++){
if(a[i]<a[j]){
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
day = A/(a[0]+a[1]+a[2]);
if(A%(a[0]+a[1]+a[2])) day++; //向上取整
cout<<day<<endl;
return 0;
}
4 作业
本节课的作业，就是复习上面的所有知识，并完成下面的题目！
1 a+b
实现高精度数据a和b的加法，a和b是整数，可正可负。
AI与区块链技术
长按二维码关注
标签：信息学,01,int,赛培,链表,算法,排序,集训 From： https://blog.51cto.com/u_12001271/5973641