信息學(xué)科中程序填空問題的解題技巧探究

1、信息學(xué)科中程序填空問題的解題技巧探究摘要：信息學(xué)科中程序填空題閱讀量巨大，學(xué)生需要消耗大量時間來理解題意，而近幾年對計(jì)數(shù)思想的考查，更標(biāo)志著程序填空題的難度從代碼層面到思維深度的跨越。筆者經(jīng)過對程序填空題的研究歸納，總結(jié)出六點(diǎn)解題技巧，讓學(xué)生盡快理解出題人設(shè)計(jì)意圖及算法核心思想，提高解題效率。關(guān)鍵詞：計(jì)數(shù)思想;篩法求質(zhì)數(shù);有效思考浙江省2021年4月份信息技術(shù)選考卷第17題中，考查了計(jì)數(shù)思想的應(yīng)用，而計(jì)數(shù)排序并沒有作為一個專門的內(nèi)容在信息學(xué)科指導(dǎo)意見中出現(xiàn)，我們通過分析這道加試題來了解計(jì)數(shù)思想的算法思想。【加試題】小王編寫了一個依據(jù)成績計(jì)算名次的VB程序，成績?yōu)?到100之間的整數(shù)。算法的根本

2、思想：先統(tǒng)計(jì)每個分?jǐn)?shù)的個數(shù)，然后按照分?jǐn)?shù)從高到低依次計(jì)算每個有效分?jǐn)?shù)該分?jǐn)?shù)的個數(shù)不為0對應(yīng)的名次，分?jǐn)?shù)相同時名次并列。最高分為第1名，該分?jǐn)?shù)的名次與個數(shù)之和為下一個有效分?jǐn)?shù)的名次，以此類推。程序用數(shù)組A存放每個分?jǐn)?shù)對應(yīng)的個數(shù)，數(shù)組B存放每個分?jǐn)?shù)對應(yīng)的名次。例如，下表中最高分100有2個，并列第1名，那么分?jǐn)?shù)96的名次為分?jǐn)?shù)100的名次加上分?jǐn)?shù)100的個數(shù)，即第3名。程序運(yùn)行時，學(xué)生數(shù)據(jù)顯示在列表框List1中，單擊“計(jì)算按鈕Command1，計(jì)算結(jié)果顯示在列表框List2中，程序運(yùn)行界面如以下圖。實(shí)現(xiàn)上述功能的VB程序如下，請答復(fù)以下問題：1如表所示，假設(shè)分?jǐn)?shù)93的個數(shù)為2，那么該分?jǐn)?shù)對應(yīng)的名

3、次為 。2請?jiān)诋嬀€處填入適宜的代碼。DimsName1To50AsString存放學(xué)生姓名DimsScore1To50AsInteger存放學(xué)生分?jǐn)?shù)DimrecCountAsIntegr存放學(xué)生人數(shù)本過程從數(shù)據(jù)庫中讀取學(xué)生數(shù)據(jù)，存儲在相應(yīng)的變量中，并在List1中顯示，代碼略整數(shù)轉(zhuǎn)換成長度固定的字符串FunctionadsxAsInteger，nAsIntegerAsStringDimsxAsString，nxAsInteger，iAsIntegersx=Strx：nx=LensxFori=1Ton-nxsx=+sxNextiEndFunctionPrivateSubCommand1

4、_ClickDimA0To100AsInteger，B0To100AsInteger存放每個分?jǐn)?shù)的個數(shù)和名次DimmcAsInteger，scoreAsInteger，iAsIntegerFori=0To100Ai=0NextiFori=1Torecount計(jì)算每個分?jǐn)?shù)的個數(shù)Nextimc=1Fori=100To0Step-1計(jì)算每個分?jǐn)?shù)的名次IfAi 0 ThenBi=mcEndIfNextiList2.Clear：List2.AddItem姓名分?jǐn)?shù)名次：List2.AddItem-Fori=1TorecCountScore=sScorei：mc=BsScoreiList2.AddItems

5、Namei+adsscore，5+第+adsmc，3+名NextiEndSub冒泡和選擇排序是基于比較的排序，計(jì)數(shù)排序是基于元素鍵值的排序，其核心思想是將待排序關(guān)鍵字作為數(shù)組下標(biāo)，將數(shù)組值表示為對應(yīng)下標(biāo)數(shù)字出現(xiàn)的次數(shù)。以此題為例，Ai中的值表示分?jǐn)?shù)i出現(xiàn)的次數(shù)，其初始值為0，表示在排序開始時每一個分?jǐn)?shù)都未出現(xiàn)過，再枚舉每個學(xué)生的分?jǐn)?shù)，表示該分?jǐn)?shù)出現(xiàn)了一次，將該分?jǐn)?shù)對應(yīng)的計(jì)數(shù)加1，故處應(yīng)填入AsScorei=AsScorei+1，此空也是計(jì)數(shù)排序核心思想的表達(dá)。假設(shè)只有三個學(xué)生，其分?jǐn)?shù)分別為75、87、75，那么每次A數(shù)組的變化過程如下：此時如果我們需要對三個學(xué)生的成績按照從大到小排序的話，我們

6、只需要從100分?jǐn)?shù)的上界枚舉到0分?jǐn)?shù)的下界，第一個遇到非0的Ai為A87，其值為1，表示出現(xiàn)了一個87。其后還有兩個75，那么排序后的結(jié)果為87、75、75。而此題還要計(jì)算每個分?jǐn)?shù)的排名，我們只需將相應(yīng)的排名變量對Ai做一個累加即可，即第處的答案為mc=mc+Ai。第處考查的是VB中函數(shù)返回值的使用，答案為ads=sx。計(jì)數(shù)排序算法于1954年由HaroldH.Seward提出。它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時，它的復(fù)雜度為n+k其中k是整數(shù)的范圍，快于任何基于比較的排序算法。當(dāng)然這也是算法設(shè)計(jì)中，以犧牲空間為代價來提高時間效率的一種常見處理方法。近幾次技術(shù)選考中，也出現(xiàn)過求質(zhì)數(shù)的應(yīng)用，

7、包括判斷一個數(shù)是否是質(zhì)數(shù)以及預(yù)處理出一定范圍的質(zhì)數(shù)。判斷一個數(shù)是否為質(zhì)數(shù)問題主要考查學(xué)生對枚舉算法的掌握情況以及數(shù)的整除問題的一個簡單應(yīng)用，而求出一定范圍內(nèi)的質(zhì)數(shù)時，常使用篩法求質(zhì)數(shù)，也是計(jì)數(shù)思想的一種應(yīng)用。假設(shè)需求出1000000以內(nèi)的所有質(zhì)數(shù)，其算法主要過程如下。一、定義布爾型數(shù)組f1to1000000，fi表示i是否為質(zhì)數(shù)。二、將f數(shù)組初始化為true，預(yù)設(shè)每個數(shù)都是質(zhì)數(shù)。三、i從2開始枚舉到1000000，如果fi等于true，那么fi是質(zhì)數(shù)，且所有i的倍數(shù)都不是質(zhì)數(shù)，將fi的倍數(shù)賦值為false。如果fi等于false，那么直接枚舉下一個i。四、當(dāng)i枚舉結(jié)束，此時f數(shù)組中值為true

8、的數(shù)是質(zhì)數(shù)，反之不是質(zhì)數(shù)。當(dāng)然1為特殊情況，需要特判。觀察以上算法，易發(fā)現(xiàn)在計(jì)數(shù)思想中需要使用額外的輔助存儲空間，其空間范圍為待統(tǒng)計(jì)數(shù)值的大小，即如果數(shù)值過大，那么程序無法申請對應(yīng)的空間，即使空間足夠，逐個枚舉每個元素也會導(dǎo)致程序運(yùn)行過慢。因此我們需要根據(jù)題目給定的數(shù)據(jù)規(guī)模與限制條件來選擇適宜的算法來解決問題。計(jì)數(shù)思想的考查，標(biāo)志著技術(shù)科目選考的考查內(nèi)容從傳統(tǒng)的選擇排序，冒泡排序，二分查找等常見算法框架提升到對變量、數(shù)理邏輯思維等更深層次的領(lǐng)域，作為整張卷子的壓軸題，考查內(nèi)容也更為靈活。而在考場上，程序填空題往往題目描述及代碼閱讀量都非常大，局部學(xué)生僅僅為了讀懂題目就消耗了大量的時間，哪怕最后

9、勉強(qiáng)讀懂，倉促拿分，也會導(dǎo)致后面的通用模塊來不及解答。筆者經(jīng)過對程序填空題的研究歸納，結(jié)合其特點(diǎn)，總結(jié)出以下六點(diǎn)思考技巧，讓學(xué)生在短時間內(nèi)盡量摸準(zhǔn)算法核心思想，提高正確率。一、了解輸入輸出內(nèi)容。二、確定核心變量含義。三、變量使用前需要初始化。四、初始化后的變量大概率是要被使用的。五、循環(huán)的初始和結(jié)束條件。六、函數(shù)的返回值是否符合要求。帶著以上六點(diǎn)去思考，可以讓學(xué)生有針對性地考慮問題，減少無效思考時間，在短時間內(nèi)做出正確的解答。下面再結(jié)合一個例題進(jìn)行講解：小明編寫了一個字符串加密程序，功能如下：在文本框Text1中輸入明碼，單擊加密按鈕Command1后，在文本框Text2中顯示加密后的密文。加

10、密算法如下。1將明碼中每個字符的八位二進(jìn)制ASCII碼缺乏八位的左端補(bǔ)0，湊足八位分成兩段高4位一段，低4位為另一段，如大寫字母“C的二進(jìn)制ASCII值為01000011，分段后為0100，0011。2將高位段左邊4位左移一位，并將4位里原最高位移到最低位處如0100左移后為1000，再轉(zhuǎn)化為十六進(jìn)制數(shù)如1000轉(zhuǎn)化為8。3對低位段右4位按2所示轉(zhuǎn)化，如001101106。4順次連接兩位十六進(jìn)制數(shù)，得到該字符的暗碼，如“C的暗碼為“86。5將每個字符的暗碼按照明碼的順序連接。實(shí)現(xiàn)上述功能的VB程序如下，請?jiān)诋嬀€處填入適宜代碼。PrivateSubCommand1_Click局部變量定義Dimd

11、1To8AsInteger數(shù)組d存儲字符ASCII碼二進(jìn)制從左到右的各位數(shù)碼DimmwAsStringmw存儲暗碼mw=Fori=1ToLenText1.Textc=MidText1.Text，i，1Forj=1To8dj=0Nextjm=AsccDoWhilem>0dk=mMod2：m=m2：k=k-1Loopx=d1：y=d5Forj=1To3dj=dj+1Nextjd4=x：d8=ymw=mw+btohdNextiText2.Text=mwEndSub以下函數(shù)是將數(shù)組元素中的二進(jìn)制數(shù)轉(zhuǎn)換成對應(yīng)的十六進(jìn)制數(shù)FunctionbtohmAsIntegerAsString將數(shù)組m作為函數(shù)的

12、參數(shù)局部變量定義str=0123456789ABCDEF：s=0：ch=Fori=1To8s=s*2+miIfi=4Thench=Midstr，s+1，1：s=0NextiEndFunction該題篇幅較長，且題面描述的五步加密算法非常復(fù)雜，如果從題目描述出發(fā)，再去揣摩出題人的代碼對應(yīng)的實(shí)際含義，非常費(fèi)時。下面筆者嘗試結(jié)合提出的六點(diǎn)思考技巧來解決此題。首先快速通看全題，第空相對獨(dú)立，該函數(shù)要將m數(shù)組中的二進(jìn)制轉(zhuǎn)化成對應(yīng)的十六進(jìn)制數(shù)再通過函數(shù)值返回，觀察函數(shù)段中并沒有出現(xiàn)函數(shù)返回值處理，故此空顯然是關(guān)于函數(shù)返回值的處理，即關(guān)于btoh的賦值語句。而m中總共8位2進(jìn)制數(shù)，對應(yīng)2位十六進(jìn)制數(shù)，且程序

13、中在i=4時對這兩個十六進(jìn)制數(shù)做了一個隔斷，第一個數(shù)存在ch中，而i=8時并沒有額外處理，此時第2個十六進(jìn)制數(shù)還在Midstr，s+1，1中，故此處的答案只能為btoh=ch+Midstr，s+1，1。再觀察第空，注意到下方的while循環(huán)中，有一行代碼為k=k-1，而此時k并沒有初始化，故大膽假設(shè)此處是關(guān)于k初值的賦值語句，結(jié)合代碼段前后文中關(guān)于d數(shù)組下標(biāo)的處理，此處的答案為k=8。題目需要處理的三個空中僅有第空是關(guān)于占據(jù)了題目一大局部的加密算法的處理，觀察x和y這兩個核心變量的處理，易知第空是處理剩余低位段那3位左移操作，且給出的dj=dj+1也已經(jīng)提醒和印證了我們的結(jié)論，故此空的答案為dj+4=dj+5，由于規(guī)模不大，我們也可再將j代回來進(jìn)行最后校驗(yàn)。至此，此題圓滿解決。在解決加試題的壓軸題環(huán)節(jié)，我們可以通過強(qiáng)化對計(jì)數(shù)排序等側(cè)重思維的算法訓(xùn)練，提高算法思維能力，也