CCF 2022 初赛——CSP-J阅读程序1解析
2022-11-03白二娃
白二娃
中国计算机学会（CCF）推出的CSP认证（Certified Softwmare Professional Junior/Senior，非专业软件能力认证，简称CSP-J/S），目的是评价计算机专业人士或准专业人士计算机科学的基础能力——算法和编程能力。CSP-J面向初中以下，CSP-S面向高中生。进入CSP-J复赛获奖有助于升入更好的中学。
自2020年以来全国青少年信息学奥林匹克联赛（NOIP）仅面向高中生，CSP代替了NOIP的位置。升级路线就成了CSP-J/S初赛→CSP-J/S复赛→全国青少年信息学奥林匹克联赛（NOIP）→省内选拔（省选）→全国青少年信息学奥林匹克竞赛 （NOI国赛）。
全国青少年信息学奥林匹克竞赛（NOI），是全国最高水平的信息学大赛。所有选手前50名将参加国家集训队，集训队队员可以获得保送、自主招生、降档录取等政策优待。
集训队选出5名队员组成国家队，参加亚太信息学奥林匹克（APIO）、国际信息学奥林匹克竞赛（IOI）为国争光。
参加CSP与学习少儿编程是有一些区别的，CSP的学习目的是竞赛和升学，学习的内容是系统的计算机知识，选用的是大学教材，将大学计算机专业课程里面基础性的和思维性的，下沉到青少年阶段进行学习。信息学竞赛相对于数学竞赛的数学要求要低一些，对数学天分的要求相对较低，适合思维灵活、动手能力强，有较好编程基础学生从初中开始正式学习，到高一开始正式参赛到高三获奖，帮助升学。而少儿编程的学习更多是以培养编程思维和编程能力为目标。
我们已经在第39期完成了第一部分的选择题，下面进入第二部分难度更高的阅读程序题。
本次考试的阅读程序题难度高于第三大题的完善程序题，同学们在实际考试时可以先做第三部分完善程序。
今天来分析阅读程序的第一题，该题含有6小问
阅读程序（程序输入不超过数组或字符串定义的范围;判断题正确填√，错误填×;除特殊说明外，判断题1.5分，选择题3分，共计40分）
假设输入的x、y均是不超过15的自然数，完成下面的判断题和单选题。
16. 删去第7行与第13行的unsigned，程序行为不变。（ ）
17. 将第7行与第13行的short均改为char，程序行为不变。（ ）
18. 程序总是输出一个整数“0”。（ ）
19. 当输入为“2 2”时，输出为“10”。（ ）
20. 当输入为“2 2”时，输出为“59”。（ ）
21. 当输入为“13 8”时，输出为（ ）
A.“0” B.“209” C.“197” D.“226”
本题主要考查位运算，要求掌握C++的6个位操作运算符的基本知识，并能读懂代码。这道题有两种解法。
第一是笔算，因为数据最大的是13和8，计算量不算太大，笔算可以出结果。
第二种是用dcba和DCBA代替4位的x、y，根据程序得到规律性的结果是DdCcBbAa，然后去计算题目要求的2 2和13 8。
位运算是指按二进制进行的运算。在系统软件中，常常需要处理二进制位的问题。C语言提供了6个位操作运算符。这些运算符只能用于整型操作数，即只能用于带符号或无符号的char、short、int与long类型。这里的与、或、非与逻辑运算的规则一致，需要将对象转换为二进制后按位进行运算，如下表。
本题中用到了左移<<、右移>>、按位与&、按位或|，4个位运算符。
按位与&：参加运算的两个数据，按二进制位进行“与”运算。如果两个相应的二进制位都为1，则该位的结果值为1;否则为0。
按位或|：两个相应的二进制位中只要有一个为1，该位的结果值为1。借用逻辑学中或运算的话来说就是，一真为真。
左移<<：左移运算符是用来将一個数的各二进制位左移若干位，移动的位数由右操作数指定（右操作数必须是非负值），其右边空出的位用0填补，高位左移溢出则舍弃该高位。例如15<<2，即00001111（2），左移2位得00111100（2）。
右移>>：右移运算符是用来将一个数的各二进制位右移若干位，移动的位数由右操作数指定（右操作数必须是非负值），移到右端的低位被舍弃，对于无符号数，高位补0。对于有符号数，某些机器将对左边空出的部分用符号位填补（即“算术移位”），如果原来符号位为0（该数为正），则左边也是移入0。如果符号位原来为1（即负数），则左边移入的是1。而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。这取决于所用的计算机系统。本题中由于数字不超过15，所以不会产生影响。
首先注意到程序第7行：unsigned short x，y;
unsigned 表示无符号整型数据类型取值范围是大于等于0的整数。数据类型包括：字符型（char）、整形（short、int、long）、浮点型（float， double），字节数如下表。说明xy是2个字节的非负整数，2个字节16位。
题目给出了x、y均不超过15，15转为二进制为1111（2），因此x和y的二进制最多4位。
解法一就是将2、2带入硬算。
从代码第9行 x = （x | x << 2） & 0x33; 开始计算。2转为二进制00000010。0x33为十六进制转为二进制00110011。计算结果为00000010，十进制2。
结果00000010带入第10行。0x55为十六进制转为二进制01010101。结果为00000100，十进制4。
y也是2，代码11和12行运算结果一样为00000010，十进制为2。
结果带入代码13行，计算结果z=00001100，十进制为12。所以19和20题都应该是错误的。
解法二是用代数的方法找到适用于各种情况的规律。根据题意最大为15，占用4位，用dcba代替x，用DCBA代替y。
带入代码9行运算，（d|b）表示这一位是db的或運算结果，在和0x33进行与运算之后结果必然是0。这样x的二进制就从原来的dcba变成了dc00ba。
带入第10行x = （x | x << 1） & 0x55;计算。结果变成0d0c0b0a。
把y设为DCBA，经过同样的计算，11、12行最终结果为0D0C0B0
A。那么13行的结果如图，Z=DdCcBbAa。
16. 删去第7行与第13行的unsigned，程序行为不变。（√）
解析：unsigned short占16位，删掉unsigned以后只要能保证在非符号位的后15位以内进行操作都没问题。通过上述分析可以看到z的位数最多是8位，没有超过15位。因此程序行为不变。
17. 将第7行与第13行的short均改为char，程序行为不变。（×）
解析︰这题的重点不在13行，而是在14行。改为字符型之后，cout<<z;会因为z是char类型而输出字符，不再输出整数。
18. 程序总是输出一个整数“0”。（×）
解析：通过上述分析可以看到如果x是dcba，y是DCBA，那么z是DdCcBbAa，并不是0。
19. 当输入为“2 2”时，输出为“10”。（×）
20. 当输入为“2 2”时，输出为“59”。（×）
当输入为“2 2”时，我们笔算的结果为12。
再用z是DdCcBbAa来验算一下，x：0010，y：0010。带入得到z：00001100，即12，说明我们得到的规律正确。所以两题都打叉。
21.当输入为“13 8”时，输出为（B）
A.“0” B.“209” C.“197” D.“226”
可以重复用笔算的方法，但有了之前总结的规律能更快得到结果。x=13=1101，y=8=1000。z=DdCcBbAa=11010001（下划线的数字来自y）。二进制转十进制结果为209，选B。
小结，跟随我们的解题思路完成这道题之后你有什么感觉？这些题对于小学生、初中生来说难度很高了。
说信奥赛简单也只是相对于数理化奥赛来说的，每一位能获得高校青睐的选手都是万里挑一，天分、特长、恒心、经济实力缺一不可。所以要慎重选择竞赛这条路，如果不是真有顶尖的实力，还不如选择学习普通编程为将来的学习和生活提供有效的帮助。
