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

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

關鍵詞：計數(shù)思想;篩法求質數(shù);有效思考

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

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

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

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

（1）如表所示，若分數(shù)93的個數(shù)為2，則該分數(shù)對應的名次為 ?。

（2）請在畫線處填入合適的代碼。

Dim sName（ 1 To 50 ） As String 存放學生姓名

Dim sScore（ 1 To 50 ） As Integer 存放學生分數(shù)

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

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

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

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 存放每個分數(shù)的個數(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 計算每個分數(shù)的個數(shù)

②

Next i

mc = 1

For i = 100 To 0 Step -1 計算每個分數(shù)的名次

If A（i） <> 0 Then

B（i） = mc

③

End If

Next i

List2.Clear ： List2.AddItem ″姓名分數(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

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

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

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

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

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

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

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

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

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

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

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

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

一、 了解輸入輸出內容。

二、 確定核心變量含義。

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

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

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

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

帶著以上六點去思考，可以讓學生有針對性地考慮問題，減少無效思考時間，在短時間內做出正確的解答。下面再結合一個例題進行講解：

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

（1）將明碼中每個字符的八位二進制ASCII碼（不足八位的左端補0，湊足八位）分成兩段（高4位一段，低4位為另一段），如大寫字母“C”的二進制ASCII值為01000011，分段后為0100，0011。

（2）將高位段（左邊4位）左移一位，并將4位里原最高位移到最低位處（如0100左移后為1000），再轉化為十六進制數(shù)（如1000轉化為8）。

（3）對低位段（（右4位）按2）所示轉化，如0011→0110→6。

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

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

實現(xiàn)上述功能的VB程序如下，請在畫線處填入合適代碼。

Private Sub Command1_Click（）

部分變量定義

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

Dim mw As String mw存儲暗碼

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ù)組元素中的二進制數(shù)轉換成對應的十六進制數(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ā)，再去揣摩出題人的代碼對應的實際含義，非常費時。下面筆者嘗試結合提出的六點思考技巧來解決此題。

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

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

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

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

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

參考文獻：

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

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

作者簡介：

李建，浙江省杭州市，浙江省杭州市杭州第二中學。