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

摘 要：信息學(xué)科中程序填空題閱讀量巨大，學(xué)生需要耗費(fèi)大量時(shí)間來理解題意，而近幾年對(duì)計(jì)數(shù)思想的考查，更標(biāo)志著程序填空題的難度從代碼層面到思維深度的跨越。筆者經(jīng)過對(duì)程序填空題的研究歸納，總結(jié)出六點(diǎn)解題技巧，讓學(xué)生盡快理解出題人設(shè)計(jì)意圖及算法核心思想，提高解題效率。

關(guān)鍵詞：計(jì)數(shù)思想;篩法求質(zhì)數(shù);有效思考

浙江省2017年4月份信息技術(shù)選考卷第17題中，考查了計(jì)數(shù)思想的應(yīng)用，而計(jì)數(shù)排序并沒有作為一個(gè)專門的內(nèi)容在信息學(xué)科指導(dǎo)意見中出現(xiàn)，我們通過分析這道加試題來了解計(jì)數(shù)思想的算法思想。

【加試題】小王編寫了一個(gè)依據(jù)成績計(jì)算名次的VB程序，成績?yōu)?到100之間的整數(shù)。算法的基本思想：先統(tǒng)計(jì)每個(gè)分?jǐn)?shù)的個(gè)數(shù)，然后按照分?jǐn)?shù)從高到低依次計(jì)算每個(gè)有效分?jǐn)?shù)（該分?jǐn)?shù)的個(gè)數(shù)不為0）對(duì)應(yīng)的名次，分?jǐn)?shù)相同時(shí)名次并列。最高分為第1名，該分?jǐn)?shù)的名次與個(gè)數(shù)之和為下一個(gè)有效分?jǐn)?shù)的名次，以此類推。程序用數(shù)組A存放每個(gè)分?jǐn)?shù)對(duì)應(yīng)的個(gè)數(shù)，數(shù)組B存放每個(gè)分?jǐn)?shù)對(duì)應(yīng)的名次。例如，下表中最高分100有2個(gè)，并列第1名，則分?jǐn)?shù)96的名次為分?jǐn)?shù)100的名次加上分?jǐn)?shù)100的個(gè)數(shù)，即第3名。

程序運(yùn)行時(shí)，學(xué)生數(shù)據(jù)顯示在列表框List1中，單擊“計(jì)算”按鈕Command1，計(jì)算結(jié)果顯示在列表框List2中，程序運(yùn)行界面如圖所示。

實(shí)現(xiàn)上述功能的VB程序如下，請(qǐng)回答下列問題：

（1）如表所示，若分?jǐn)?shù)93的個(gè)數(shù)為2，則該分?jǐn)?shù)對(duì)應(yīng)的名次為 ?。

（2）請(qǐng)?jiān)诋嬀€處填入合適的代碼。

Dim sName（ 1 To 50 ） As String 存放學(xué)生姓名

Dim sScore（ 1 To 50 ） As Integer 存放學(xué)生分?jǐn)?shù)

Dim recCount As Integr 存放學(xué)生人數(shù)

本過程從數(shù)據(jù)庫中讀取學(xué)生數(shù)據(jù)，存儲(chǔ)在相應(yīng)的變量中，并在List1中顯示，代碼略

整數(shù)轉(zhuǎn)換成長度固定的字符串

Function ads（ x As Integer ， n As Integer ） As String

Dim sx As String ， nx As Integer ， i As Integer

sx = Str（x） ： nx = Len（sx）

For i = 1 To n - nx

sx= ″ ″ + sx

Next i

①

End Function

Private Sub Command1_Click（）

Dim A（ 0 To 100 ） As Integer ， B（ 0 To 100 ） As Integer 存放每個(gè)分?jǐn)?shù)的個(gè)數(shù)和名次

Dim mc As Integer ， score As Integer ， i As Integer

For i = 0 To 100

A（i） = 0

Next i

For i = 1 To recount 計(jì)算每個(gè)分?jǐn)?shù)的個(gè)數(shù)

②

Next i

mc = 1

For i = 100 To 0 Step -1 計(jì)算每個(gè)分?jǐn)?shù)的名次

If A（i） <> 0 Then

B（i） = mc

③

End If

Next i

List2.Clear ： List2.AddItem ″姓名分?jǐn)?shù)名次″： List2.AddItem ″--″

For i = 1 To recCount

Score = sScore（i） ： mc = B（sScore（i））

List2.AddItem sName（i） + ads（score ， 5）+ ″第″ + ads（mc ， 3） + ″名″

Next i

End Sub

冒泡和選擇排序是基于比較的排序，計(jì)數(shù)排序是基于元素鍵值的排序，其核心思想是將待排序關(guān)鍵字作為數(shù)組下標(biāo)，將數(shù)組值表示為對(duì)應(yīng)下標(biāo)數(shù)字出現(xiàn)的次數(shù)。以本題為例，A（i）中的值表示分?jǐn)?shù)i出現(xiàn)的次數(shù)，其初始值為0，表示在排序開始時(shí)每一個(gè)分?jǐn)?shù)都未出現(xiàn)過，再枚舉每個(gè)學(xué)生的分?jǐn)?shù)，表示該分?jǐn)?shù)出現(xiàn)了一次，將該分?jǐn)?shù)對(duì)應(yīng)的計(jì)數(shù)加1，故②處應(yīng)填入A（sScore（i）） = A（sScore（i）） + 1，此空也是計(jì)數(shù)排序核心思想的體現(xiàn)。

假設(shè)只有三個(gè)學(xué)生，其分?jǐn)?shù)分別為75、87、75，則每次A數(shù)組的變化過程如下：

此時(shí)如果我們需要對(duì)三個(gè)學(xué)生的成績按照從大到小排序的話，我們只需要從100（分?jǐn)?shù)的上界）枚舉到0（分?jǐn)?shù)的下界），第一個(gè)遇到非0的A（i）為A（87），其值為1，表示出現(xiàn)了一個(gè)87。其后還有兩個(gè)75，則排序后的結(jié)果為87、75、75。

而此題還要計(jì)算每個(gè)分?jǐn)?shù)的排名，我們只需將相應(yīng)的排名變量對(duì)A（i）做一個(gè)累加即可，即第③處的答案為mc = mc + A（i）。第①處考查的是VB中函數(shù)返回值的使用，答案為ads = sx。

計(jì)數(shù)排序算法于1954年由Harold H. Seward提出。它的優(yōu)勢(shì)在于在對(duì)一定范圍內(nèi)的整數(shù)排序時(shí)，它的復(fù)雜度為Ο（n+k）（其中k是整數(shù)的范圍），快于任何基于比較的排序算法。當(dāng)然這也是算法設(shè)計(jì)中，以犧牲空間為代價(jià)來提高時(shí)間效率的一種常見處理方法。

近幾次技術(shù)選考中，也出現(xiàn)過求質(zhì)數(shù)的應(yīng)用，包括判斷一個(gè)數(shù)是否是質(zhì)數(shù)以及預(yù)處理出一定范圍的質(zhì)數(shù)。判斷一個(gè)數(shù)是否為質(zhì)數(shù)問題主要考查學(xué)生對(duì)枚舉算法的掌握情況以及數(shù)的整除問題的一個(gè)簡(jiǎn)單應(yīng)用，而求出一定范圍內(nèi)的質(zhì)數(shù)時(shí)，常使用篩法求質(zhì)數(shù)，也是計(jì)數(shù)思想的一種應(yīng)用。假設(shè)需求出1000000以內(nèi)的所有質(zhì)數(shù)，其算法主要過程如下。

一、 定義布爾型數(shù)組f[1 to 1000000]，f[i]表示i是否為質(zhì)數(shù)。

二、 將f數(shù)組初始化為true，預(yù)設(shè)每個(gè)數(shù)都是質(zhì)數(shù)。

三、 i從2開始枚舉到1000000，如果f[i]等于true，則f[i]是質(zhì)數(shù)，且所有i的倍數(shù)都不是質(zhì)數(shù)，將f[i的倍數(shù)]賦值為false。如果f[i]等于false，則直接枚舉下一個(gè)i。

四、 當(dāng)i枚舉結(jié)束，此時(shí)f數(shù)組中值為true的數(shù)是質(zhì)數(shù)，反之不是質(zhì)數(shù)。當(dāng)然1為特殊情況，需要特判。

觀察以上算法，易發(fā)現(xiàn)在計(jì)數(shù)思想中需要使用額外的輔助存儲(chǔ)空間，其空間范圍為待統(tǒng)計(jì)數(shù)值的大小，即如果數(shù)值過大，則程序無法申請(qǐng)對(duì)應(yīng)的空間，即使空間足夠，逐個(gè)枚舉每個(gè)元素也會(huì)導(dǎo)致程序運(yùn)行過慢。因此我們需要根據(jù)題目給定的數(shù)據(jù)規(guī)模與限制條件來選擇合適的算法來解決問題。

計(jì)數(shù)思想的考查，標(biāo)志著技術(shù)科目選考的考查內(nèi)容從傳統(tǒng)的選擇排序，冒泡排序，二分查找等常見算法框架提升到對(duì)變量、數(shù)理邏輯思維等更深層次的領(lǐng)域，作為整張卷子的壓軸題，考查內(nèi)容也更為靈活。而在考場(chǎng)上，程序填空題往往題目描述及代碼閱讀量都非常大，部分學(xué)生僅僅為了讀懂題目就耗費(fèi)了大量的時(shí)間，哪怕最后勉強(qiáng)讀懂，倉促拿分，也會(huì)導(dǎo)致后面的通用模塊來不及解答。筆者經(jīng)過對(duì)程序填空題的研究歸納，結(jié)合其特點(diǎn)，總結(jié)出以下六點(diǎn)思考技巧，讓學(xué)生在短時(shí)間內(nèi)盡量摸準(zhǔn)算法核心思想，提高正確率。

一、 了解輸入輸出內(nèi)容。

二、 確定核心變量含義。

三、 變量使用前需要初始化。

四、 初始化后的變量大概率是要被使用的。

五、 循環(huán)的初始和結(jié)束條件。

六、 函數(shù)的返回值是否符合要求。

帶著以上六點(diǎn)去思考，可以讓學(xué)生有針對(duì)性地考慮問題，減少無效思考時(shí)間，在短時(shí)間內(nèi)做出正確的解答。下面再結(jié)合一個(gè)例題進(jìn)行講解：

小明編寫了一個(gè)字符串加密程序，功能如下：在文本框Text1中輸入明碼，單擊”加密”按鈕Command1后，在文本框Text2中顯示加密后的密文。加密算法如下。

（1）將明碼中每個(gè)字符的八位二進(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）對(duì)低位段（（右4位）按2）所示轉(zhuǎn)化，如0011→0110→6。

（4）順次連接兩位十六進(jìn)制數(shù)，得到該字符的暗碼，如“C”的暗碼為“86”。

（5）將每個(gè)字符的暗碼按照明碼的順序連接。

實(shí)現(xiàn)上述功能的VB程序如下，請(qǐng)?jiān)诋嬀€處填入合適代碼。

Private Sub Command1_Click（）

部分變量定義

Dim d（ 1 To 8 ）As Integer 數(shù)組d存儲(chǔ)字符ASCII碼二進(jìn)制從左到右的各位數(shù)碼

Dim mw As String mw存儲(chǔ)暗碼

mw = ″ ″

For i = 1 To Len（Text1.Text）

c = Mid（Text1.Text， i， 1）

For j = 1 To 8

d（j） = 0

Next j

m = Asc（c）

①

Do While m > 0

d（k） = m Mod 2 ： m = m ＼ 2 ： k = k - 1

Loop

x = d（1） ： y = d（5）

For j = 1 To 3

d（j） = d（j + 1）

②

Next j

d（4） = x ： d（8） = y

mw = mw + btoh（d）

Next i

Text2.Text = mw

End Sub

以下函數(shù)是將數(shù)組元素中的二進(jìn)制數(shù)轉(zhuǎn)換成對(duì)應(yīng)的十六進(jìn)制數(shù)

Function btoh（ m（） As Integer ） As String 將數(shù)組m作為函數(shù)的參數(shù)

部分變量定義

str=″0123456789ABCDEF″ ： s = 0 ： ch = ″ ″

For i = 1 To 8

s = s * 2 + m（i）

If i = 4 Then ch = Mid（str， s+1， 1） ： s = 0

Next i

③

End Function

該題篇幅較長，且題面描述的五步加密算法非常復(fù)雜，如果從題目描述出發(fā)，再去揣摩出題人的代碼對(duì)應(yīng)的實(shí)際含義，非常費(fèi)時(shí)。下面筆者嘗試結(jié)合提出的六點(diǎn)思考技巧來解決此題。

首先快速通看全題，第③空相對(duì)獨(dú)立，該函數(shù)要將m數(shù)組中的二進(jìn)制轉(zhuǎn)化成對(duì)應(yīng)的十六進(jìn)制數(shù)再通過函數(shù)值返回，觀察函數(shù)段中并沒有出現(xiàn)函數(shù)返回值處理，故此空顯然是關(guān)于函數(shù)返回值的處理，即關(guān)于btoh的賦值語句。

而m中總共8位2進(jìn)制數(shù)，對(duì)應(yīng)2位十六進(jìn)制數(shù)，且程序中在i = 4時(shí)對(duì)這兩個(gè)十六進(jìn)制數(shù)做了一個(gè)隔斷，第一個(gè)數(shù)存在ch中，而i = 8時(shí)并沒有額外處理，此時(shí)第2個(gè)十六進(jìn)制數(shù)還在Mid（str， s+1， 1）中，故此處的答案只能為btoh = ch + Mid（str， s+1， 1）。

再觀察第①空，注意到下方的while循環(huán)中，有一行代碼為k = k - 1，而此時(shí)k并沒有初始化，故大膽假設(shè)此處是關(guān)于k初值的賦值語句，結(jié)合代碼段前后文中關(guān)于d數(shù)組下標(biāo)的處理，此處的答案為k = 8。

題目需要處理的三個(gè)空中僅有第②空是關(guān)于占據(jù)了題目一大部分的加密算法的處理，觀察x和y這兩個(gè)核心變量的處理，易知第②空是處理剩余低位段那3位左移操作，且給出的d（j） = d（j + 1）也已經(jīng)提醒和印證了我們的結(jié)論，故此空的答案為d（j + 4） = d（j + 5），由于規(guī)模不大，我們也可再將j代回來進(jìn)行最后校驗(yàn)。至此，本題圓滿解決。

在解決加試題的壓軸題環(huán)節(jié)，我們可以通過強(qiáng)化對(duì)計(jì)數(shù)排序等側(cè)重思維的算法訓(xùn)練，提高算法思維能力，也可通過面對(duì)具體題目時(shí)，帶線索的針對(duì)性思考，盡可能繞開大篇幅的背景和代碼描述，可以大大減少思考時(shí)間，減小題目的整體難度，在解決程序填空類問題時(shí)，達(dá)到事半功倍的效果。

參考文獻(xiàn)：

[1]楊繡丞，李彤，趙娜，等.計(jì)算排序算法設(shè)計(jì)與分析[J].計(jì)算機(jī)應(yīng)用研究，2014，31（3）：658-662.

[2]曹紅霞.程序設(shè)計(jì)模塊學(xué)業(yè)水平考試命題研究[J].中國信息技術(shù)教育，2014（23）：76-78.

作者簡(jiǎn)介：

李建，浙江省杭州市，浙江省杭州市杭州第二中學(xué)。