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

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

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

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

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

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

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

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

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

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

Dim sScore（ 1 To 50 ） As Integer 存放學生分數

Dim recCount As Integr 存放學生人數

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

整數轉換成長度固定的字符串

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 存放每個分數的個數和名次

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 計算每個分數的個數

②

Next i

mc = 1

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

If A（i） <> 0 Then

B（i） = mc

③

End If

Next i

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

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

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

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

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

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

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

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

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

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

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

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

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

一、 了解輸入輸出內容。

二、 確定核心變量含義。

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

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

五、 循環的初始和結束條件。

六、 函數的返回值是否符合要求。

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

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

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

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

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

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

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

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

Private Sub Command1_Click（）

部分變量定義

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

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

以下函數是將數組元素中的二進制數轉換成對應的十六進制數

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

部分變量定義

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

該題篇幅較長，且題面描述的五步加密算法非常復雜，如果從題目描述出發，再去揣摩出題人的代碼對應的實際含義，非常費時。下面筆者嘗試結合提出的六點思考技巧來解決此題。

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

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

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

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

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

參考文獻：

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

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

作者簡介：

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