《信息奥赛课课通》课件第10单元ppt.ppt

高等教育出版社高等教育出版社 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第 10 单元单元 位运算及标准模板库位运算及标准模板库作者：林厚从作者：林厚从信息学奥赛课课通（信息学奥赛课课通（C+C+）高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第 1 课课 位运算位运算学习目标学习目标1.理解与掌握理解与掌握 C+中的位运算。中的位运算。2.灵活应用位运算优化程序。灵活应用位运算优化程序。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 任何信息在计算机中都是采用二进制表示的，数据在计算任何信息在计算机中都是采用二进制表示的，数据在计算机中是以补码形式存储的，位运算就是直接对整数在内存中的机中是以补码形式存储的，位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作，不二进制位进行运算。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。同时，一个整数的各个二往可以优化理论时间复杂度的系数。同时，一个整数的各个二进制位互不影响，利用位运算的一些技巧可以帮助我们简化程进制位互不影响，利用位运算的一些技巧可以帮助我们简化程序代码。序代码。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符C+提供了按位与（提供了按位与（&）、按位或（）、按位或（|）、按位异或）、按位异或（）、取反（）、取反（）、左移（）、左移（）这）这 6 种位运种位运算符。这些运算符只能用于整型操作数，即只能用于带符号算符。这些运算符只能用于整型操作数，即只能用于带符号或无符号的或无符号的 char、short、int 与与 long 类型。类型。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符（1）按位与（）按位与（&）“a&b”是指将参加运算的两个整数是指将参加运算的两个整数a和和b，按二进制位进行，按二进制位进行“与与”运算。如果两个相应的二进制位数字都为，则该位的运算。如果两个相应的二进制位数字都为，则该位的结果为结果为1；否则为；否则为0。这里的。这里的1可以理解为逻辑中的可以理解为逻辑中的true,0可以理可以理解为逻辑中的解为逻辑中的false。“按位与按位与”其实与逻辑上其实与逻辑上“与与”的运算规的运算规则一致。则一致。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符（2）按位或（）按位或（|）“a|b”是指将参加运算的两个整数是指将参加运算的两个整数a和和b，按二进制位进行，按二进制位进行“或或”运算。如果两个相应的二进制位数字有一个为，则该运算。如果两个相应的二进制位数字有一个为，则该位的结果为位的结果为1；否则为；否则为0。“按位或按位或”其实与逻辑上其实与逻辑上“或或”的运的运算规则一致。算规则一致。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符（3）按位异或（）按位异或（）“ab”是指将参加运算的两个整数是指将参加运算的两个整数a和和b，按二进制位进行，按二进制位进行“异或异或”运算。如果两个相应的二进制位数字不相同，则该位运算。如果两个相应的二进制位数字不相同，则该位的结果为的结果为1；否则为；否则为0。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符（4）取反（）取反（）“a”是指将整数是指将整数a的各个二进制位都取反，即的各个二进制位都取反，即1变为变为0，0变变为为1。“”是一元运算符。是一元运算符。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符（5）左移（）左移（）“ab”是指将整数是指将整数a的各个二进制位左移的各个二进制位左移b位，高位丢弃，位，高位丢弃，低位用低位用0补齐。需要注意的是补齐。需要注意的是b必须是非负整数。在高位没有必须是非负整数。在高位没有1丢弃的情况下，丢弃的情况下，a）“ab”是指将整数是指将整数a的各个二进制位右移的各个二进制位右移b位，低位丢弃。位，低位丢弃。对于无符号数，高位补对于无符号数，高位补0。对于有符号数，某些机器将对左边。对于有符号数，某些机器将对左边空出的部分用符号位填补（即空出的部分用符号位填补（即“算术移位算术移位”），而另一些机器），而另一些机器则对左边空出的部分用则对左边空出的部分用0填补（即填补（即“逻辑移位逻辑移位”）。同样，）。同样，b必须是非负整数。必须是非负整数。a1相当于相当于a/2。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符 位运算符也可以与赋值运算符组成复合运算符。例如位运算符也可以与赋值运算符组成复合运算符。例如a&=b 相当于相当于a=a&b，a=2相当于相当于a=a”和和“”的运算的运算优先级低于优先级低于“加减加减”，“&”的运算优先级低于的运算优先级低于“关系运算关系运算”而高于而高于“”,“”的优先级高于的优先级高于“|”，而，而“|”的优先级高的优先级高于于“&”和和“|”。为了避免出错，增强程序的可读性，利于。为了避免出错，增强程序的可读性，利于调试，建议在需要的地方添加括号来保证优先运算。比如调试，建议在需要的地方添加括号来保证优先运算。比如15-1，建议写成，建议写成1(5-1)，等价于，等价于14。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能2.位运算应用举例位运算应用举例位运算的应用场合非常广泛，如高效代替布尔型数组，位运算的应用场合非常广泛，如高效代替布尔型数组，表示集合、搜索算法中的状态判重（表示集合、搜索算法中的状态判重（hash）、动态规划算法）、动态规划算法中的状态压缩等。中的状态压缩等。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例1、阅读程序，写出程序的运行结果，体会位运算的思想。、阅读程序，写出程序的运行结果，体会位运算的思想。/p10-1-1#includeusing namespace std;int main()int x=3,y=8,z;x=y;y=x;x=y;cout x “y 1);cout z endl;return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例2、整数幂、整数幂判断一个数判断一个数 n 是不是是不是 2 的整数幂，比如的整数幂，比如 64=2 6，所以输，所以输出出“yes”，而，而 65 无法表示成无法表示成 2 的整数幂形式，所以输出的整数幂形式，所以输出“no”。n 在在 int 范围以内。范围以内。【问题分析问题分析】我们考虑一个数如果是我们考虑一个数如果是2的整数幂会有什么特殊性。观察的整数幂会有什么特殊性。观察发现发现64转换成二进制为转换成二进制为01000000，只有一个位是，只有一个位是1。将这个数。将这个数减去减去1，就变成，就变成00111111的形式，我们将这的形式，我们将这2个数做按位与运算，个数做按位与运算，发现结果为发现结果为0。分析发现，如果一个数不能表示成。分析发现，如果一个数不能表示成2的整数幂的整数幂形式，则以上过程的运算结果一定不为形式，则以上过程的运算结果一定不为0。所以，可以利用位。所以，可以利用位运算将算法的时间复杂度优化成运算将算法的时间复杂度优化成O(1)。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能/p10-1-2b#includeusing namespace std;int main()int n;cin n;if(n&(n-1)cout “no“endl;else cout “yes“endl;return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例3、找数、找数【问题描述问题描述】给出给出 n 个整数，个整数，n 为奇数，其中有且仅有一个数出现了奇数为奇数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间复杂度、常数空次，其余的数都出现了偶数次。用线性时间复杂度、常数空间复杂度找出出现了奇数次的那个数。间复杂度找出出现了奇数次的那个数。【输入格式输入格式】第一行一个整数第一行一个整数n，1n5106。接下来。接下来n 行，每行一个数。行，每行一个数。【输出格式输出格式】输出一行一个整数，表示出现了奇数次的那一个数。输出一行一个整数，表示出现了奇数次的那一个数。【输入样例输入样例】93 3 1 2 4 2 5 5 4【输出样例输出样例】1高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能【问题分析问题分析】从头到尾从头到尾“异或异或”一遍，最后得到的那个数就是出现了一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑一个数，结果不变。再考虑“异或异或”运算满足交换律，先异运算满足交换律，先异或、后异或都是一样的，因此这个算法显然正确。或、后异或都是一样的，因此这个算法显然正确。参考程序见教材参考程序见教材510-511页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第 2 课课 vector学习目标学习目标1.了解了解 C+的标准模板库。的标准模板库。2.掌握掌握 vector 容器的使用方法。容器的使用方法。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能标准模板库（标准模板库（Standard Template Library，STL）C+功能强大，为开发者提供了标准模板库，其中封装功能强大，为开发者提供了标准模板库，其中封装了很多实用的容器。容器可以理解成能够实现很多功能的系了很多实用的容器。容器可以理解成能够实现很多功能的系统函数，或者说用来存放数据的对象，开发者可以根据接口统函数，或者说用来存放数据的对象，开发者可以根据接口规范（调用格式）直接调用，而不用关心其内部实现的原理规范（调用格式）直接调用，而不用关心其内部实现的原理和具体代码，十分方便快捷。和具体代码，十分方便快捷。常见的容器有常见的容器有vector、stack、queue、map、set等。等。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能vector vector直接翻译为直接翻译为“向量向量”，一般说成，一般说成“变长数组变长数组”，也，也即即“长度根据需要而自动改变的数组。长度根据需要而自动改变的数组。在信息学竞赛中，有些题目需要定义很大的数组，这样在信息学竞赛中，有些题目需要定义很大的数组，这样会出现会出现“超出内存限制超出内存限制”的错误。比如，如果一个图的顶点的错误。比如，如果一个图的顶点太多，使用邻接矩阵就会超出内存限制，使用指针实现邻接太多，使用邻接矩阵就会超出内存限制，使用指针实现邻接表又很容易出错，而使用表又很容易出错，而使用vector实现简洁方便，还可以节省存实现简洁方便，还可以节省存储空间。储空间。使用使用vector，首先需要添加，首先需要添加vector头文件，即头文件，即#include，同时，必须要有，同时，必须要有“using namespace std”。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.vector 的定义的定义定义一个定义一个 vector 的方法如下：的方法如下：vector name;以上定义相当于定义了一个一维数组以上定义相当于定义了一个一维数组namesize，只是，只是size不确定，其长度可以根据需要而变化。其中不确定，其长度可以根据需要而变化。其中typename可可以是任何基本类型，例如以是任何基本类型，例如int、double、char、结构体等，也、结构体等，也可以是可以是STL标准容器，例如标准容器，例如vector、queue等。等。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能访问访问 vector 中的元素一般有两种方式。中的元素一般有两种方式。第一种是通过第一种是通过“下标下标”访问。访问。例如，对于容器例如，对于容器 vector v，可以使用，可以使用 vindex来访问来访问它的第它的第 index 个元素。其中，个元素。其中，0indexv.size()-1，v.size()表示表示 vector 中元素的个数。中元素的个数。第二种方式是通过第二种方式是通过“迭代器迭代器”访问。访问。可以将迭代器（可以将迭代器（iterator）理解为一种类似指针的变量。）理解为一种类似指针的变量。其定义为：其定义为：vector:iterator it;2.vector 的访问的访问 例如：例如：vector:iterator it=v.begin();for(int i=0;i=5;i+)printf(%d,*(it+i);高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能3.vector 的常用函数的常用函数（1）push_back()push_back(x)用来在用来在 vector 后面添加一个元素后面添加一个元素 x，时间复，时间复杂度为杂度为 0(1)。（2）size()如果是一维数组，如果是一维数组，size()用来获得用来获得 vector 中元素的个数；中元素的个数；如果是二维数组，如果是二维数组，size()用来获得用来获得vector 中第二维的元素个数，中第二维的元素个数，时间复杂度为时间复杂度为 0(1)。（3）pop_back()pop_back()用来删除用来删除 vector 的尾元素，时间复杂度为的尾元素，时间复杂度为 0(1)。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能3.vector 的常用函数的常用函数（4）clear()clear()用来清空用来清空 vector 中的所有元素，时间复杂度为中的所有元素，时间复杂度为 0(n)，其中，其中 n 为为 vector 中元素的个数。中元素的个数。（5）insert()insert(it，x)用来向用来向 vector 任意迭代器任意迭代器 it 处插入一个元素处插入一个元素 x，时间复杂度为，时间复杂度为 0(n)。（6）erase()erase()用来删除用来删除 vector 中的元素，有两种用法。一种是中的元素，有两种用法。一种是 erase(it)，删除迭代器，删除迭代器 it 处的元素；另一种是处的元素；另一种是 erase(first，last)，删除左闭右开区间，删除左闭右开区间first，last)内的所有元素。内的所有元素。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能4.vector 的应用举例的应用举例例例1、中间数、中间数【问题描述问题描述】依次读入若干正整数，如果是奇数个就输出最中间的那依次读入若干正整数，如果是奇数个就输出最中间的那个数；否则，输出中间两个数的和。以个数；否则，输出中间两个数的和。以 0 作为结束标志，但作为结束标志，但 0 不计数。不计数。【问题分析问题分析】参考程序见教材参考程序见教材516-517页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例2、上网统计、上网统计【问题描述问题描述】在一个网络系统中有在一个网络系统中有 N 个用户、个用户、M 次上网记录。每个用户可以自己次上网记录。每个用户可以自己注册一个用户名，每个用户名是一个只含小写字母且长度小于注册一个用户名，每个用户名是一个只含小写字母且长度小于 1000 的字的字符串。每个上网的账号每次上网都会浏览网页，网页名是以一个只含小符串。每个上网的账号每次上网都会浏览网页，网页名是以一个只含小写字母且长度小于写字母且长度小于 1000 的字符串，每次上网日志里都会有记录，现在请的字符串，每次上网日志里都会有记录，现在请统计每个用户每次浏览了多少个网页。统计每个用户每次浏览了多少个网页。【输入格式输入格式】第第 1 行包含两个用行包含两个用 1 个空格隔开的正整数个空格隔开的正整数 N（1N1000）和）和 M（1M5000）。）。第第 2M+1 行，每行包含行，每行包含 2 个用个用 1 个空格隔开的字符串，分别表示用个空格隔开的字符串，分别表示用户名和浏览的网页名。户名和浏览的网页名。【输出格式输出格式】共共 N 行，每行的第一个字符串是用户名，接下来的若干字符串是这行，每行的第一个字符串是用户名，接下来的若干字符串是这个用户依次浏览的网页名（之间用一个空格隔开）。按照用户名出现的个用户依次浏览的网页名（之间用一个空格隔开）。按照用户名出现的次序排序输出。次序排序输出。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能【输入样例输入样例】5 7goodstudyer bookshopalikespacea spacewebgoodstudyer bookshopblikespaceb spaceweblikespacec spaceweblikespacea juiceshopgameplayer gameweb【输出样例输出样例】goodstudyer bookshopa bookshopblikespacea spaceweb juiceshoplikespaceb spaceweblikespacec spacewebgameplayer gameweb高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能【问题分析问题分析】由于用户名和浏览的网页名长度不固定，用由于用户名和浏览的网页名长度不固定，用 vector 解解决比较方便，可以分别通过决比较方便，可以分别通过“下标下标”访问和访问和“迭代器迭代器”访问。访问。参考程序见教材参考程序见教材517-519页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例3、蛇形方阵、蛇形方阵【问题描述问题描述】输入输入 n，n100，输出，输出 n 阶蛇形方阵。例如阶蛇形方阵。例如 n=5 时，输时，输出如下：出如下：1 2 6 7 153 5 8 14 164 9 13 17 2210 12 18 21 2311 19 20 24 25【问题分析问题分析】定义一个二维数组，模拟蛇形方阵填数的过程。定义一个二维数组，模拟蛇形方阵填数的过程。具体程具体程序参见教材序参见教材520页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第 3 课课 stack学习目标学习目标掌握掌握 stack 容器的使用方法。容器的使用方法。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能stack的定义的定义 stack翻译为栈，是翻译为栈，是STL中实现的一个中实现的一个“后进先出后进先出”的容器，其只能通过的容器，其只能通过top()和和pop()来访问栈顶元素。在第七单来访问栈顶元素。在第七单元中，我们已经介绍过手工栈的定义和操作，它一般用来解元中，我们已经介绍过手工栈的定义和操作，它一般用来解决因为系统栈空间较小而导致的决因为系统栈空间较小而导致的“函数递归层数过深函数递归层数过深”出现出现程序运行崩溃的问题。程序运行崩溃的问题。使用使用stack前，要先添加前，要先添加stack头文件，即头文件，即#include，同时，必须要有，同时，必须要有“using namespace std”。定义一个定义一个 stack 的方法如下：的方法如下：stack name;其中，其中，typename 可以是任何基本类型或者容器，可以是任何基本类型或者容器，name 是栈的名字。是栈的名字。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.stack 的常用函数的常用函数（1）push()push(x)用来将用来将 x 压栈，时间复杂度为压栈，时间复杂度为 0(1)。（2）top()top()用来获得栈顶元素，时间复杂度为用来获得栈顶元素，时间复杂度为 0(1)。（3）pop()pop()用来弹出栈顶元素，时间复杂度为用来弹出栈顶元素，时间复杂度为 0(1)。（4）empty()empty()用来检测用来检测 stack 是否为空，空返回是否为空，空返回 true，否则返回，否则返回 false，时间复杂度为，时间复杂度为 0(1)。（5）size()size()用来返回用来返回 stack 内元素的个数，时间复杂度为内元素的个数，时间复杂度为 0(1)。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能2.stack 的应用举例的应用举例例例1、括号的匹配、括号的匹配【问题描述问题描述】栈在计算机科学领域有着广泛的应用。比如在编译和运栈在计算机科学领域有着广泛的应用。比如在编译和运行计算机程序的过程中，就需要用栈进行语法检查，如检查行计算机程序的过程中，就需要用栈进行语法检查，如检查 begin 和和 end、和和、（和）等是否匹配。、（和）等是否匹配。假设一个表达式只由小写英文字母、运算符（假设一个表达式只由小写英文字母、运算符（+，-，*，/）和左、右小括号构成，以）和左、右小括号构成，以“”作为表达式的结束符。作为表达式的结束符。请编程检查表达式中的左、右小括号是否匹配，若匹配，请编程检查表达式中的左、右小括号是否匹配，若匹配，则返回则返回“YES”；否则返回；否则返回“NO”，不必关心表达式中的其，不必关心表达式中的其他错误。他错误。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能【问题分析问题分析】用一个栈存放表达式中从左往右的左小括号。从左往右用一个栈存放表达式中从左往右的左小括号。从左往右按顺序扫描表达式的每个字符，若是按顺序扫描表达式的每个字符，若是“（”，则将它压栈；，则将它压栈；若是若是“）”，则执行一次出栈操作。当栈发生下溢（右括号，则执行一次出栈操作。当栈发生下溢（右括号多）或当表达式处理完毕而栈非空（左括号多）时，意味着多）或当表达式处理完毕而栈非空（左括号多）时，意味着表达式中的括号不匹配，则输出表达式中的括号不匹配，则输出“NO”；否则，表示小括号；否则，表示小括号完全匹配，就输出完全匹配，就输出“YES”。参考程序见教材参考程序见教材524页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例2、溶液模拟器、溶液模拟器【问题分析问题分析】小小 Y 虽有很多溶液，但还是没有办法配成想要的溶液，虽有很多溶液，但还是没有办法配成想要的溶液，因为万一倒错了就没有办法挽回了。他从网上下载了一个溶因为万一倒错了就没有办法挽回了。他从网上下载了一个溶液配置模拟器：模拟器在计算机中构造一种虚拟溶液，然后液配置模拟器：模拟器在计算机中构造一种虚拟溶液，然后可以虚拟地向当前虚拟溶液中加入一定浓度、一定质量的这可以虚拟地向当前虚拟溶液中加入一定浓度、一定质量的这种溶液，模拟器会快速地算出倒入后虚拟溶液的浓度和质量。种溶液，模拟器会快速地算出倒入后虚拟溶液的浓度和质量。模拟器的使用步骤如下：模拟器的使用步骤如下：（1）为模拟器设置一个初始质量和浓度）为模拟器设置一个初始质量和浓度 V0、C0%（0C0 100）。）。（2）进行一系列操作，模拟器支持两种操作：一种是）进行一系列操作，模拟器支持两种操作：一种是 P（v，c）操作，表示向当前的虚拟溶液中加入质量为）操作，表示向当前的虚拟溶液中加入质量为 v、浓、浓度为度为 c 的溶液；另一种是的溶液；另一种是 Z 操作，即撤销上一步操作，即撤销上一步 P 操作。操作。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能【输入格式输入格式】第第 1 行两个整数行两个整数 V0、C0。第第 2 行行 1 个整数个整数 n，n10000，表示操作数。，表示操作数。接下来的接下来的 n 行，每行一条操作，格式为：行，每行一条操作，格式为：P_v_c 或或 Z。其中其中“_”代表一个空格，当只剩初始溶液的时候，再撤销代表一个空格，当只剩初始溶液的时候，再撤销就没有用了。就没有用了。任意时刻质量都不会超过任意时刻质量都不会超过 231-1。【输出格式输出格式】输出输出 n 行，每行两个数行，每行两个数 Vi、Ci，之间用一个空格隔开，之间用一个空格隔开，其中其中 Vi 为整数，为整数，Ci 为实数（保留为实数（保留 5 位小数）。其中，第位小数）。其中，第 i 行表示第行表示第 i 次操作以后的溶液质量和浓度。次操作以后的溶液质量和浓度。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能【输入样例输入样例】100 1002P 100 0Z【输出样例输出样例】200 50.000 00100 100.000 00【问题分析问题分析】使用栈来模拟实现。读入撤销时，栈顶元素出栈；读使用栈来模拟实现。读入撤销时，栈顶元素出栈；读入溶液时，把新的溶液的质量和浓度压栈。每次操作完，入溶液时，把新的溶液的质量和浓度压栈。每次操作完，输出栈顶的质量和浓度。输出栈顶的质量和浓度。参考程序见教材参考程序见教材525-526页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例3、表达式求值、表达式求值【题目描述题目描述】给定一个只包含加法和乘法的算术表达