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

白二娃

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

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

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

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

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

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

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

今天來分析閱讀程序的第一題，該題含有6小問

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

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

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

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

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

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

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

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

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

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

第一是筆算，因為數(shù)據(jù)最大的是13和8，計算量不算太大，筆算可以出結(jié)果。

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

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

本題中用到了左移<<、右移>>、按位與&、按位或|，4個位運算符。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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