《信息奥赛课课通》课件第10单元ppt.ppt
《《信息奥赛课课通》课件第10单元ppt.ppt》由会员分享,可在线阅读,更多相关《《信息奥赛课课通》课件第10单元ppt.ppt(120页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、 高等教育出版社高等教育出版社 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第 10 单元单元 位运算及标准模板库位运算及标准模板库作者:林厚从作者:林厚从信息学奥赛课课通(信息学奥赛课课通(C+C+)高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会
2、精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第 1 课课 位运算位运算学习目标学习目标1.理解与掌握理解与掌握 C+中的位运算。中的位运算。2.灵活应用位运算优化程序。灵活应用位运算优化程序。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 任何信息在计算机中都是采用二进制表示的,数据在计算任何信息在计算机中都是采用二进制表示的,数据在计算
3、机中是以补码形式存储的,位运算就是直接对整数在内存中的机中是以补码形式存储的,位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作,不二进制位进行运算。由于位运算直接对内存数据进行操作,不需要转换成十进制,因此处理速度非常快,在信息学竞赛中往需要转换成十进制,因此处理速度非常快,在信息学竞赛中往往可以优化理论时间复杂度的系数。同时,一个整数的各个二往可以优化理论时间复杂度的系数。同时,一个整数的各个二进制位互不影响,利用位运算的一些技巧可以帮助我们简化程进制位互不影响,利用位运算的一些技巧可以帮助我们简化程序代码。序代码。高等教育出版社高等教育出版社信息学奥赛课课通
4、(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符C+提供了按位与(提供了按位与(&)、按位或()、按位或(|)、按位异或)、按位异或()、取反()、取反()、左移()、左移()这)这 6 种位运种位运算符。这些运算符只能用于整型操作数,即只能用于带符号算符。这些运算符只能用于整型操作数,即只能用于带符号或无符号的或无符号的 char、short、int 与与 long 类型。类型。高
5、等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符(1)按位与()按位与(&)“a&b”是指将参加运算的两个整数是指将参加运算的两个整数a和和b,按二进制位进行,按二进制位进行“与与”运算。如果两个相应的二进制位数字都为,则该位的运算。如果两个相应的二进制位数字都为,则该位的结果为结果为1;否则为;否则为0。这里的。这里的1可以理解为逻辑中的可
6、以理解为逻辑中的true,0可以理可以理解为逻辑中的解为逻辑中的false。“按位与按位与”其实与逻辑上其实与逻辑上“与与”的运算规的运算规则一致。则一致。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符(2)按位或()按位或(|)“a|b”是指将参加运算的两个整数是指将参加运算的两个整数a和和b,按二进制位进行,按二进制位进行“或或”运算
7、。如果两个相应的二进制位数字有一个为,则该运算。如果两个相应的二进制位数字有一个为,则该位的结果为位的结果为1;否则为;否则为0。“按位或按位或”其实与逻辑上其实与逻辑上“或或”的运的运算规则一致。算规则一致。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符(3)按位异或()按位异或()“ab”是指将参加运算的两个整数是指将参加运算的两个整
8、数a和和b,按二进制位进行,按二进制位进行“异或异或”运算。如果两个相应的二进制位数字不相同,则该位运算。如果两个相应的二进制位数字不相同,则该位的结果为的结果为1;否则为;否则为0。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符(4)取反()取反()“a”是指将整数是指将整数a的各个二进制位都取反,即的各个二进制位都取反,即1变为变为0
9、,0变变为为1。“”是一元运算符。是一元运算符。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符(5)左移()左移()“ab”是指将整数是指将整数a的各个二进制位左移的各个二进制位左移b位,高位丢弃,位,高位丢弃,低位用低位用0补齐。需要注意的是补齐。需要注意的是b必须是非负整数。在高位没有必须是非负整数。在高位没有1丢弃的情况下,丢弃的情
10、况下,a)“ab”是指将整数是指将整数a的各个二进制位右移的各个二进制位右移b位,低位丢弃。位,低位丢弃。对于无符号数,高位补对于无符号数,高位补0。对于有符号数,某些机器将对左边。对于有符号数,某些机器将对左边空出的部分用符号位填补(即空出的部分用符号位填补(即“算术移位算术移位”),而另一些机器),而另一些机器则对左边空出的部分用则对左边空出的部分用0填补(即填补(即“逻辑移位逻辑移位”)。同样,)。同样,b必须是非负整数。必须是非负整数。a1相当于相当于a/2。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神
11、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.位运算符位运算符 位运算符也可以与赋值运算符组成复合运算符。例如位运算符也可以与赋值运算符组成复合运算符。例如a&=b 相当于相当于a=a&b,a=2相当于相当于a=a”和和“”的运算的运算优先级低于优先级低于“加减加减”,“&”的运算优先级低于的运算优先级低于“关系运算关系运算”而高于而高于“”,“”的优先级高于的优先级高于“|”,而,而“|”的优先级高的优先级高于于“&”和和“|”。为了避免出错,增强程序的可读性,利于。为了避免出
12、错,增强程序的可读性,利于调试,建议在需要的地方添加括号来保证优先运算。比如调试,建议在需要的地方添加括号来保证优先运算。比如15-1,建议写成,建议写成1(5-1),等价于,等价于14。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能2.位运算应用举例位运算应用举例位运算的应用场合非常广泛,如高效代替布尔型数组,位运算的应用场合非常广泛,如高效代替布尔型数组
13、,表示集合、搜索算法中的状态判重(表示集合、搜索算法中的状态判重(hash)、动态规划算法)、动态规划算法中的状态压缩等。中的状态压缩等。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例1、阅读程序,写出程序的运行结果,体会位运算的思想。、阅读程序,写出程序的运行结果,体会位运算的思想。/p10-1-1#includeusing namespace std
14、;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 无法表示成无法表示
15、成 2 的整数幂形式,所以输出的整数幂形式,所以输出“no”。n 在在 int 范围以内。范围以内。【问题分析问题分析】我们考虑一个数如果是我们考虑一个数如果是2的整数幂会有什么特殊性。观察的整数幂会有什么特殊性。观察发现发现64转换成二进制为转换成二进制为01000000,只有一个位是,只有一个位是1。将这个数。将这个数减去减去1,就变成,就变成00111111的形式,我们将这的形式,我们将这2个数做按位与运算,个数做按位与运算,发现结果为发现结果为0。分析发现,如果一个数不能表示成。分析发现,如果一个数不能表示成2的整数幂的整数幂形式,则以上过程的运算结果一定不为形式,则以上过程的运算结果
16、一定不为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“end
17、l;return 0;高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能例例3、找数、找数【问题描述问题描述】给出给出 n 个整数,个整数,n 为奇数,其中有且仅有一个数出现了奇数为奇数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间复杂度、常数空次,其余的数都出现了偶数次。用线性时间复杂度、常数空间复杂度找出出现了奇数次的那个数。间复杂度找
18、出出现了奇数次的那个数。【输入格式输入格式】第一行一个整数第一行一个整数n,1n5106。接下来。接下来n 行,每行一个数。行,每行一个数。【输出格式输出格式】输出一行一个整数,表示出现了奇数次的那一个数。输出一行一个整数,表示出现了奇数次的那一个数。【输入样例输入样例】93 3 1 2 4 2 5 5 4【输出样例输出样例】1高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小
19、学图书室育人功能【问题分析问题分析】从头到尾从头到尾“异或异或”一遍,最后得到的那个数就是出现了一遍,最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质:两次异或同奇数次的数。这是因为异或有一个神奇的性质:两次异或同一个数,结果不变。再考虑一个数,结果不变。再考虑“异或异或”运算满足交换律,先异运算满足交换律,先异或、后异或都是一样的,因此这个算法显然正确。或、后异或都是一样的,因此这个算法显然正确。参考程序见教材参考程序见教材510-511页。页。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为
20、深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能第第 2 课课 vector学习目标学习目标1.了解了解 C+的标准模板库。的标准模板库。2.掌握掌握 vector 容器的使用方法。容器的使
21、用方法。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能标准模板库(标准模板库(Standard Template Library,STL)C+功能强大,为开发者提供了标准模板库,其中封装功能强大,为开发者提供了标准模板库,其中封装了很多实用的容器。容器可以理解成能够实现很多功能的系了很多实用的容器。容器可以理解成能够实现很多功能的系统函数,或者说用来存放数据
22、的对象,开发者可以根据接口统函数,或者说用来存放数据的对象,开发者可以根据接口规范(调用格式)直接调用,而不用关心其内部实现的原理规范(调用格式)直接调用,而不用关心其内部实现的原理和具体代码,十分方便快捷。和具体代码,十分方便快捷。常见的容器有常见的容器有vector、stack、queue、map、set等。等。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人
23、功能vector vector直接翻译为直接翻译为“向量向量”,一般说成,一般说成“变长数组变长数组”,也,也即即“长度根据需要而自动改变的数组。长度根据需要而自动改变的数组。在信息学竞赛中,有些题目需要定义很大的数组,这样在信息学竞赛中,有些题目需要定义很大的数组,这样会出现会出现“超出内存限制超出内存限制”的错误。比如,如果一个图的顶点的错误。比如,如果一个图的顶点太多,使用邻接矩阵就会超出内存限制,使用指针实现邻接太多,使用邻接矩阵就会超出内存限制,使用指针实现邻接表又很容易出错,而使用表又很容易出错,而使用vector实现简洁方便,还可以节省存实现简洁方便,还可以节省存储空间。储空间。
24、使用使用vector,首先需要添加,首先需要添加vector头文件,即头文件,即#include,同时,必须要有,同时,必须要有“using namespace std”。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.vector 的定义的定义定义一个定义一个 vector 的方法如下:的方法如下:vector name;以上定义相当于定义了一个一维数组
25、以上定义相当于定义了一个一维数组namesize,只是,只是size不确定,其长度可以根据需要而变化。其中不确定,其长度可以根据需要而变化。其中typename可可以是任何基本类型,例如以是任何基本类型,例如int、double、char、结构体等,也、结构体等,也可以是可以是STL标准容器,例如标准容器,例如vector、queue等。等。高等教育出版社高等教育出版社信息学奥赛课课通(信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息奥赛课课通 信息 奥赛课课通 课件 10 单元 ppt
限制150内