CCF 2022 初賽——CSP-J閱讀程序1解析

白二娃

中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）推出的CSP認(rèn)證（Certified Softwmare Professional Junior/Senior，非專業(yè)軟件能力認(rèn)證，簡(jiǎn)稱CSP-J/S），目的是評(píng)價(jià)計(jì)算機(jī)專業(yè)人士或準(zhǔn)專業(yè)人士計(jì)算機(jī)科學(xué)的基礎(chǔ)能力——算法和編程能力。CSP-J面向初中以下，CSP-S面向高中生。進(jìn)入CSP-J復(fù)賽獲獎(jiǎng)有助于升入更好的中學(xué)。

自2020年以來(lái)全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）僅面向高中生，CSP代替了NOIP的位置。升級(jí)路線就成了CSP-J/S初賽→CSP-J/S復(fù)賽→全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）→省內(nèi)選拔（省選）→全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽 （NOI國(guó)賽）。

全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽（NOI），是全國(guó)最高水平的信息學(xué)大賽。所有選手前50名將參加國(guó)家集訓(xùn)隊(duì)，集訓(xùn)隊(duì)隊(duì)員可以獲得保送、自主招生、降檔錄取等政策優(yōu)待。

集訓(xùn)隊(duì)選出5名隊(duì)員組成國(guó)家隊(duì)，參加亞太信息學(xué)奧林匹克（APIO）、國(guó)際信息學(xué)奧林匹克競(jìng)賽（IOI）為國(guó)爭(zhēng)光。

參加CSP與學(xué)習(xí)少兒編程是有一些區(qū)別的，CSP的學(xué)習(xí)目的是競(jìng)賽和升學(xué)，學(xué)習(xí)的內(nèi)容是系統(tǒng)的計(jì)算機(jī)知識(shí)，選用的是大學(xué)教材，將大學(xué)計(jì)算機(jī)專業(yè)課程里面基礎(chǔ)性的和思維性的，下沉到青少年階段進(jìn)行學(xué)習(xí)。信息學(xué)競(jìng)賽相對(duì)于數(shù)學(xué)競(jìng)賽的數(shù)學(xué)要求要低一些，對(duì)數(shù)學(xué)天分的要求相對(duì)較低，適合思維靈活、動(dòng)手能力強(qiáng)，有較好編程基礎(chǔ)學(xué)生從初中開(kāi)始正式學(xué)習(xí)，到高一開(kāi)始正式參賽到高三獲獎(jiǎng)，幫助升學(xué)。而少兒編程的學(xué)習(xí)更多是以培養(yǎng)編程思維和編程能力為目標(biāo)。

我們已經(jīng)在第39期完成了第一部分的選擇題，下面進(jìn)入第二部分難度更高的閱讀程序題。

本次考試的閱讀程序題難度高于第三大題的完善程序題，同學(xué)們?cè)趯?shí)際考試時(shí)可以先做第三部分完善程序。

今天來(lái)分析閱讀程序的第一題，該題含有6小問(wèn)

閱讀程序（程序輸入不超過(guò)數(shù)組或字符串定義的范圍;判斷題正確填√，錯(cuò)誤填×;除特殊說(shuō)明外，判斷題1.5分，選擇題3分，共計(jì)40分）

假設(shè)輸入的x、y均是不超過(guò)15的自然數(shù)，完成下面的判斷題和單選題。

16. 刪去第7行與第13行的unsigned，程序行為不變。（ ）

17. 將第7行與第13行的short均改為char，程序行為不變。（ ）

18. 程序總是輸出一個(gè)整數(shù)“0”。（ ）

19. 當(dāng)輸入為“2 2”時(shí)，輸出為“10”。（ ）

20. 當(dāng)輸入為“2 2”時(shí)，輸出為“59”。（ ）

21. 當(dāng)輸入為“13 8”時(shí)，輸出為（ ）

A.“0” B.“209” C.“197” D.“226”

本題主要考查位運(yùn)算，要求掌握C++的6個(gè)位操作運(yùn)算符的基本知識(shí)，并能讀懂代碼。這道題有兩種解法。

第一是筆算，因?yàn)閿?shù)據(jù)最大的是13和8，計(jì)算量不算太大，筆算可以出結(jié)果。

第二種是用dcba和DCBA代替4位的x、y，根據(jù)程序得到規(guī)律性的結(jié)果是DdCcBbAa，然后去計(jì)算題目要求的2 2和13 8。

位運(yùn)算是指按二進(jìn)制進(jìn)行的運(yùn)算。在系統(tǒng)軟件中，常常需要處理二進(jìn)制位的問(wèn)題。C語(yǔ)言提供了6個(gè)位操作運(yùn)算符。這些運(yùn)算符只能用于整型操作數(shù)，即只能用于帶符號(hào)或無(wú)符號(hào)的char、short、int與long類型。這里的與、或、非與邏輯運(yùn)算的規(guī)則一致，需要將對(duì)象轉(zhuǎn)換為二進(jìn)制后按位進(jìn)行運(yùn)算，如下表。

本題中用到了左移<<、右移>>、按位與&、按位或|，4個(gè)位運(yùn)算符。

按位與&：參加運(yùn)算的兩個(gè)數(shù)據(jù)，按二進(jìn)制位進(jìn)行“與”運(yùn)算。如果兩個(gè)相應(yīng)的二進(jìn)制位都為1，則該位的結(jié)果值為1;否則為0。

按位或|：兩個(gè)相應(yīng)的二進(jìn)制位中只要有一個(gè)為1，該位的結(jié)果值為1。借用邏輯學(xué)中或運(yùn)算的話來(lái)說(shuō)就是，一真為真。

左移<<：左移運(yùn)算符是用來(lái)將一個(gè)數(shù)的各二進(jìn)制位左移若干位，移動(dòng)的位數(shù)由右操作數(shù)指定（右操作數(shù)必須是非負(fù)值），其右邊空出的位用0填補(bǔ)，高位左移溢出則舍棄該高位。例如15<<2，即00001111（2），左移2位得00111100（2）。

右移>>：右移運(yùn)算符是用來(lái)將一個(gè)數(shù)的各二進(jìn)制位右移若干位，移動(dòng)的位數(shù)由右操作數(shù)指定（右操作數(shù)必須是非負(fù)值），移到右端的低位被舍棄，對(duì)于無(wú)符號(hào)數(shù)，高位補(bǔ)0。對(duì)于有符號(hào)數(shù)，某些機(jī)器將對(duì)左邊空出的部分用符號(hào)位填補(bǔ)（即“算術(shù)移位”），如果原來(lái)符號(hào)位為0（該數(shù)為正），則左邊也是移入0。如果符號(hào)位原來(lái)為1（即負(fù)數(shù)），則左邊移入的是1。而另一些機(jī)器則對(duì)左邊空出的部分用0填補(bǔ)（即“邏輯移位”）。這取決于所用的計(jì)算機(jī)系統(tǒng)。本題中由于數(shù)字不超過(guò)15，所以不會(huì)產(chǎn)生影響。

首先注意到程序第7行：unsigned short x，y;

unsigned 表示無(wú)符號(hào)整型數(shù)據(jù)類型取值范圍是大于等于0的整數(shù)。數(shù)據(jù)類型包括：字符型（char）、整形（short、int、long）、浮點(diǎn)型（float， double），字節(jié)數(shù)如下表。說(shuō)明xy是2個(gè)字節(jié)的非負(fù)整數(shù)，2個(gè)字節(jié)16位。

題目給出了x、y均不超過(guò)15，15轉(zhuǎn)為二進(jìn)制為1111（2），因此x和y的二進(jìn)制最多4位。

解法一就是將2、2帶入硬算。

從代碼第9行 x = （x | x << 2） & 0x33; 開(kāi)始計(jì)算。2轉(zhuǎn)為二進(jìn)制00000010。0x33為十六進(jìn)制轉(zhuǎn)為二進(jìn)制00110011。計(jì)算結(jié)果為00000010，十進(jìn)制2。

結(jié)果00000010帶入第10行。0x55為十六進(jìn)制轉(zhuǎn)為二進(jìn)制01010101。結(jié)果為00000100，十進(jìn)制4。

y也是2，代碼11和12行運(yùn)算結(jié)果一樣為00000010，十進(jìn)制為2。

結(jié)果帶入代碼13行，計(jì)算結(jié)果z=00001100，十進(jìn)制為12。所以19和20題都應(yīng)該是錯(cuò)誤的。

解法二是用代數(shù)的方法找到適用于各種情況的規(guī)律。根據(jù)題意最大為15，占用4位，用dcba代替x，用DCBA代替y。

帶入代碼9行運(yùn)算，（d|b）表示這一位是db的或運(yùn)算結(jié)果，在和0x33進(jìn)行與運(yùn)算之后結(jié)果必然是0。這樣x的二進(jìn)制就從原來(lái)的dcba變成了dc00ba。

帶入第10行x = （x | x << 1） & 0x55;計(jì)算。結(jié)果變成0d0c0b0a。

把y設(shè)為DCBA，經(jīng)過(guò)同樣的計(jì)算，11、12行最終結(jié)果為0D0C0B0

A。那么13行的結(jié)果如圖，Z=DdCcBbAa。

16. 刪去第7行與第13行的unsigned，程序行為不變。（√）

解析：unsigned short占16位，刪掉unsigned以后只要能保證在非符號(hào)位的后15位以內(nèi)進(jìn)行操作都沒(méi)問(wèn)題。通過(guò)上述分析可以看到z的位數(shù)最多是8位，沒(méi)有超過(guò)15位。因此程序行為不變。

17. 將第7行與第13行的short均改為char，程序行為不變。（×）

解析︰這題的重點(diǎn)不在13行，而是在14行。改為字符型之后，cout<<z;會(huì)因?yàn)閦是char類型而輸出字符，不再輸出整數(shù)。

18. 程序總是輸出一個(gè)整數(shù)“0”。（×）

解析：通過(guò)上述分析可以看到如果x是dcba，y是DCBA，那么z是DdCcBbAa，并不是0。

19. 當(dāng)輸入為“2 2”時(shí)，輸出為“10”。（×）

20. 當(dāng)輸入為“2 2”時(shí)，輸出為“59”。（×）

當(dāng)輸入為“2 2”時(shí)，我們筆算的結(jié)果為12。

再用z是DdCcBbAa來(lái)驗(yàn)算一下，x：0010，y：0010。帶入得到z：00001100，即12，說(shuō)明我們得到的規(guī)律正確。所以兩題都打叉。

21.當(dāng)輸入為“13 8”時(shí)，輸出為（B）

A.“0” B.“209” C.“197” D.“226”

可以重復(fù)用筆算的方法，但有了之前總結(jié)的規(guī)律能更快得到結(jié)果。x=13=1101，y=8=1000。z=DdCcBbAa=11010001（下劃線的數(shù)字來(lái)自y）。二進(jìn)制轉(zhuǎn)十進(jìn)制結(jié)果為209，選B。

小結(jié)，跟隨我們的解題思路完成這道題之后你有什么感覺(jué)？這些題對(duì)于小學(xué)生、初中生來(lái)說(shuō)難度很高了。

說(shuō)信奧賽簡(jiǎn)單也只是相對(duì)于數(shù)理化奧賽來(lái)說(shuō)的，每一位能獲得高校青睞的選手都是萬(wàn)里挑一，天分、特長(zhǎng)、恒心、經(jīng)濟(jì)實(shí)力缺一不可。所以要慎重選擇競(jìng)賽這條路，如果不是真有頂尖的實(shí)力，還不如選擇學(xué)習(xí)普通編程為將來(lái)的學(xué)習(xí)和生活提供有效的幫助。