資源簡介

專項測試十一　綜合算法類
一、加密與解密類
1.某數據加密方法描述如下：
(1)輸入的數據僅限數字；
(2)對于輸入的一串由數字組成的字符串按下面方法進行處理：將值最大的數字與最后一個位置上的數字進行交換，值最小的數字與第一個位置上的數進行交換。若一串數字中出現多個最小(或最大)數，僅對出現的第一個最小(或最大)數進行處理。
(3)將處理后的每一位數字轉換為二進制數。
小明按照上述方法，設計了一個數字加密的VB程序，功能如下：單擊“加密”按鈕Command1，程序將文本框Text1中輸入的字符串進行處理和進制轉換，最后在標簽Label3中輸出加密結果。
程序運行效果如圖所示：
實現上述功能的VB程序如下，請回答下列問題：
(1)如果輸入的數據為“395”，則最后在標簽Label1中輸出的結果是________。
(2)為實現上述功能，請在劃線處填入合適的代碼。
Dim a(1 To 100) As Integer
Private Sub Command1_Click()
　Dim s1 As String, s2 As String, s3 As String
　Dim b(1 To 10) As Integer
　Dim i As Integer, t As Integer, j As Integer
　s1 ＝ get(Text1.Text)：s3＝“ ”
　For i ＝ 1 To Len(s1)
　 s2 ＝ “ ”
　 t ＝ 1
　 Do While a(i) < > 0
　　　 __________①__________
　　　 a(i) ＝ a(i) 2
　　　　　t ＝ t ＋ 1
　 Loop
　 For j ＝ t － 1 To 1 Step －1
　　　 s2 ＝ s2 ＋ Str(b(j))
　 Next j
　 __________②__________
　Next i
　Label3.Caption ＝ s3
End Sub
Function get(s As String) As String
　Dim f As String
　Dim i As Integer，min As Integer，max As Integer，k As Integer，n As Integer
　n ＝ Len(s)
　For i ＝ 1 To n
　 a(i) ＝ Val(Mid(s, i, 1))
　Next i
　max ＝ 1: min ＝ 1
　For i ＝ 2 To n
　 If a(i) > a(max) Then max ＝ i
　 If a(i) < a(min) Then min ＝ i
　Next i
　If max < > n Then
k ＝ a(max): a(max) ＝ a(n): a(n) ＝ k
　End If
　If min < > 1 Then
　k ＝ a(min): a(min) ＝ a(1): a(1) ＝ k
　End If
　For i ＝ 1 To n
　 f ＝ f& a(i)
　Next i
　________③________
End Function
解析　(1)數據395根據加密方法可知，首先變為數據359，然后將359的每位數字轉換為二進制數，數字3對應的二進制數為11，數字5對應的二進制數為101，數字9對應的二進制數為1001，因此生成的密文為111011001。
(2)劃線①處循環表示將數字a(i)轉換為二進制數，并存儲在數組b中，因此①處的語句為b(t) ＝ a(i) Mod 2；變量s2存放的是當前數字a(i)所對應的二制數，最后將每個數字的二制數按順序拼接在字符串s3中，因此劃線②處的語句為s3 ＝ s3 ＋ s2；自定義函數get的功能是將明文數字按加密方法變為密文數字，最后由函數名傳回函數值，因此③處語句為get ＝ f。
答案　(1)111011001　(2)①b(t) ＝ a(i) Mod 2　②s3 ＝ s3 ＋ s2　③get ＝ f
2.某數據壓縮方法描述如下：
(1)原始數據中，某數不為0且相鄰無重復，壓縮數據用該數據表示；
(2)原始數據中，某數為0且相鄰無重復，壓縮數據用兩個數表示，第1個為0，第2個為0；
(3)原始數據中，某數據相鄰有重復，壓縮數據用3個數表示：第1個為0，第2個為重復數的個數，第3個為該數本身；
根據上述壓縮方法，對應的解壓縮方法示例如圖a所示。
圖a
小明編寫了一個解壓縮VB程序，功能如下：窗體加載時，自動讀取壓縮數據，依次存儲在數組元素a(1)、a(2)、a(3)……中，壓縮數據的個數存儲在變量n中，壓縮數據顯示在文本框Text1中。單擊“解壓縮”按鈕Command1，程序對壓縮數據依次進行解壓縮處理，解壓縮數據顯示在文本框Text2中。程序運行界面如圖b所示。
圖b
(1)如果壓縮數據為“23，0，21，66，0，0，77，0，5，0”，則解壓縮數據的個數是________。
(2)實現上述功能的VB程序如下。請在劃線處填入合適代碼。
Dim a(1 To 100)As Integer　′存儲壓縮數據，最大處理個數為100
Dim b(1 To 1000)As Integer　′存儲解壓縮數據，最大處理個數為1000
Dim n As Integer′存儲壓縮數據的個數
Private Sub Form_Load()
　′壓縮數據由上述壓縮方法生成
　′本過程用于讀取壓縮數據并存儲在數組a，壓縮數據個數存儲在變量n中
　′代碼略
End Sub
Private Sub Command1_Click()
　Dim pa As Integer′存儲壓縮數組當前處理位置
　Dim pb As Integer′存儲解壓縮數組當前處理位置
　Dim firstdata As Integer，count As Integer，i As Integer
　pa＝1：pb＝1
Do While pa<＝n
　firstdata＝a(pa)
　If firstdata< >0 Then　′示例1情況處理
　 b(pb)＝firstdata
　 pa＝pa＋1：pb＝pb＋1
　 Else
　 count＝a(pa＋1)
　If count＝0 Then　′示例2情況處理
　　 b(pb)＝0
　　 pa＝________①________：pb＝pb＋1
　Else　′示例3情況處理
　　 For i＝1 To count
　　 ________②________
　　 Next i
　　 pa＝pa＋3：　pb＝pb＋count
　End If
　End If
Loop
Text2.Text＝Str(b(1))
For i＝2 To ________③________
Text2.Text＝Text2.Text＋“，”＋Str(b(i))
Next i
End Sub
解析　本題主要考查的是根據算法描述理解程序實現的能力。本題的關鍵是理解壓縮與解壓縮的關系，根據數據壓縮的算法來推導出解壓縮的算法。(1)壓縮數據為“23，0，21，66，0，0，77，0，5，0”，表示1個2、21個66、1個0、1個77、5個0，因此共有1＋21＋1＋1＋5＝29個；(2)本小題主要考核學生閱讀程序、理解算法實現的能力。三處填空側重考核數組和For循環語句的應用。變量pa表示存儲壓縮數據的數組正在處理的當前位置，變量pb表示存儲解壓縮數據的數組當前處理的位置，示例2表示第一個數據為0，并且第二個數據也為0的情況，則將0存儲在數組元素b(pb)中，然后移動pa到數組a中下一個待處理的數據位置上，因此①處代碼為pa＝pa＋2；示例3表示第一個數據為0，第二個數據count不為0第三個數據x任意的情況，則將連續count個數據x存儲在數組b中，第三個數據為a(pa＋2)，存放位置為pb＋i－1(i＝1，2，…，count)，因此②處語句為b(pb＋i－1)＝a(pa＋2)；所有數據解壓縮后，顯然pb為存放最后一個數據的后面，因此解壓縮的數據個數為pb－1，即③處代碼為pb－1。
答案　(1)29　(2)①pa＋2　②b(pb＋i－1)＝a(pa＋2)　③pb－1
二、名次計算
3.小王是一位高三的學生，學校剛進行了一次高考全真模擬考試，他的成績不太理想，特別是數學學科，為了更好的對數學成績進行分析，他編寫一個求數學成績在班級排名的VB程序， 學生姓名及數學成績存儲在數據庫文件“score.accdb”的math表中。
程序運行時，在列表框List1中顯示班級同學的姓名及數學成績，在文本框Text1中輸入數學成績，單擊“排名”按鈕(Command1)，在標簽Label4中顯示名次(按數學成績從高到低的名次)，程序運行界面如圖所示。
實現上述功能的VB程序如下，但加框處碼有誤，請改正。
Dim n As Integer　　′n表示學生人數
Dim sx(100) As Single　 ′數組sx存放數學成績
Dim xm(100) As String　 ′數組xm存放學生姓名
Private Sub Form_Load()
　 ′讀入n名學生成績和姓名，分別存儲在數組sx、xm中
　 ′代碼省略
End Sub
Private Sub Command1_Click()
Dim i As Integer, k As Integer, key As Single　　′變量k存放名次
key ＝ Val(Text1.Text)
　　　　　 ′①
For i ＝ 1 To n
If 　Then　　′②
　　　　k ＝ k ＋ 1
End If
Next i
Label4.Caption ＝ Str(k)
End Sub
程序中加框①處應改正為___________________________________________；
加框②處應改正為__________________________________________________。
解析　本題主要考查的是統計功能。根據語句Label4.Caption ＝ Str(k)可知，數學成績為key的排名為k，因此變量k的初值為1；當有人的數學成績比key大時，則名次往后一名，即k＝k＋1；數學成績存放在數組sx中，因此②處代碼為sx(i)>key。
答案　①k＝1　②sx(i)>key
4.小王編寫了一個依據成績計算名次的VB程序，成績為0到100之間的整數。算法的基本思想：先統計每個分數的個數，然后按照分數從高到低依次計算每個有效分數(該分數的個數不為0)對應的名次，分數相同時名次并列。最高分為第1名，該分數的名次與個數之和為下一個有效分數的名次，以此類推。程序用數組A存放每個分數對應的個數，數組B存放每個分數對應的名次。例如，下表中最高分100有2個，并列第1名，則分數96的名次為分數100的名次加上分數100的個數，即第3名。
分數
100
99
98
97
96
95
94
…
0
個數(A數組)
2
0
0
0
1
0
3
…
0
名次(B數組)
1
3
4
…
程序運行時，學生數據顯示在列表框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 Integer′存放學生人數
Private Sub Form_Load()
　′本過程從數據庫中讀取學生數據，存儲在相應的變量中，并在List1中顯示
　 ′代碼略
End Sub
　 ′整數轉換成長度固定的字符串
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　　′存放每個分數的個數
　Dim 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 recCount ′計算每個分數的個數
______②______
　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
解析　(1)本小題可用表格方式來求解，將具體分數填入表格，如下所示：
分數
100
99
98
97
96
95
94
93
0
個數(A數組)
2
0
0
0
1
0
3
2
0
名次(B數組)
1
3
4
7
容易求得93分的名次為7。
(2)本小題主要考查的是自定義函數。ads為自定義函數，函數的函數值是通過函數名來返回的，因此①處的語句為ads＝sx；本小題主要考查計數法計算每個分數的個數，數組a用于存放每個分數的個數，數組元素a(i)表示分數為i的個數，而學生分數存放在數組sScore中，因此②處語句為A(sScore(i))＝A(sscore(i))＋1；分數i的名次為mc，則分數i－1的名次為分數i的名次＋分數i的人數，因此③處語句為mc＝mc＋A(i)，也可以寫為mc＝A(i)＋B(i)。對于本小題，我們可以用上表數據代入驗證，100分的名次為1，共有2個100，則96分的名次為100分的名次＋100的個數，即為第3名，用此方法可求94分的名次，答案將再次得以驗證。
答案　(1)7　(2)①ads＝sx　②A(sScore(i))＝A(sScore(i))＋1　③mc＝A(i)＋B(i)或mc＝mc＋A(i)
三、綜合類
5.平面上有N(3≤N≤1，00)個房間圍成一圈，按順時針方向分別編號為1～N，相鄰的兩個房間之間均有一扇門，第i個房間居住人數為a(i)。初始時選擇一個房間，將所有人都聚集在該房間，接著每個人都按順時針方向走到相鄰的房間，直到走到居住的房間。一個人每經過一扇門花費 1 的能量，請確定初始房間，使得所有人花費的能量和最小。
例如：N＝5，a(1)＝4，a(2)＝7，a(3)＝8，a(4)＝6，a(5)＝4，最佳方案為：初始時所有人聚集在 2 號房間，花費的能量和：7*0＋8*1＋6*2＋4*3＋4*4＝48。
為了解決這個問題，小明編寫了一個VB程序。在窗體加載時，從數據庫中讀取N的值和編號為1到N的房間的居住人數，人數存儲在數組a中。點擊窗體上的按鈕Command1，程序枚舉每一種方案(不同的初始房間)，計算該方案下的能量和，在文本框Text1中輸出最優方案的初始房間編號，在文本框Text2中輸出最小能量和。
實現上述功能的VB代碼如下，請在程序劃線處填入合適的代碼。
Dim a(1 To 100) As Integer ′依次存儲編號為1到100的房間的最多居住人數
Private Sub Form_Load()
　′本過程從數據庫中讀取N的值和編號為1到N的房間的居住人數，存儲在數組a中
　′代碼略
End Sub
Private Sub Command1_Click()
　Dim i As Integer, j As Integer, w As Integer , k as Integer
　Dim t As Long, ans As Long
　k＝0 : ans ＝ 32767
　For i ＝ 1 To n
t ＝ 0
For j ＝ 0 To n － 1
______①______
　 If w ＝ 0 Then w ＝ n
　 t ＝______②______
Next j
If t < ans Then
　 k＝ i : ans ＝ t
End If
　Next i
　Text1.Text ＝ Str(k)
　Text2.Text ＝ Str(ans)
End Sub
解析　程序使用枚舉算法，For i是外層循環，用于枚舉每一種開始方案。i 表示開始時聚集的房間編號，可能值是1..n；程序枚舉每一種i的值(在i房間聚集開始的情況)計算消耗的能量和。對于所有人來講，不管在哪個房間開始，有人要經過1扇門，有人要經過2扇門……，最多的要經過n－1扇門。 程序中用j表示在當前聚集方案下要經過的門數。第1個加框處：w表示進過j扇門后到達的房間編號，由于房間環形分布從1開始編號，因此①處代碼為w＝(i＋j) Mod n；第2個加框處：從for j循環結束后的語句可以分析得到，在變量t中應該已經記錄該方案的總能量數，因此，此處語句實現該方案下消耗的能量求和t＝t＋a(w)*j ，其中：a(w)表示w號房間的人數，j表示這些人經過的門的數量。
答案　①w＝(i＋j) Mod n　②t＋a(w)*j
6.設計一個VB程序，實現如下功能：在文本框Text1中輸入一個整數數列(整數間用逗號分隔)，求該數列中連續相同整數最多的數(即相鄰的數相等)，并統計其個數。例如，輸入的整數數列為：1，1，1，2，2，3，3，3，3，4，5，5，5，5，5，5，5，則連續相同整數最多的是5，共有7個。
程序運行時，在文本框Text1中輸入整數序列，單擊“計算”按鈕Command1，在文本框Text2中輸出該數列中連續相同整數最多的數，在文本框Text3輸出個數。程序運行效果如圖所示。
算法說明：
(1)首先將字符串st中的每個整數存儲在數組a中，第k個整數存儲在數組元素a(k)中 。
(2)然后從第一個數開始，依次比較相鄰兩個數，若相等，則連續相同數的個數加1，繼續比較下一對數；若不相等但連續相同整數個數大于maxi，則將結果記錄在maxi，并將當前整數的個數重新計數，然后將當前整數賦給變量t，若不相等且連續相同整數個數不大于maxi，則當前整數的個數重新計數，并將當前整數賦給變量t，繼續比較下一對數。
實現上述功能的VB程序如下，請在劃線處填入合適的代碼。
delete函數說明：delete(st，x，y)為自定義函數，功能為在字符串st中刪除x位置開始的y長度的子串。
Private Sub Command1_Click()
　Dim a(1 To 100) As Integer, st As String
　Dim i As Integer, maxi As Integer, k As Integer，n As Integer, t As Integer
　st ＝ Text1.Text
　k ＝ 0
　i ＝ 1
　Do While i <＝ Len(st)
i ＝ 1
Do While Mid(st, i, 1) < > “，” And i <＝ Len(st)
　　________①______
Loop
k ＝ k ＋ 1
a(k) ＝ Val(Mid(st, 1, i － 1))
x ＝ delete(st, 1, i)
　Loop
　maxi ＝ 0
　t ＝ a(1)
　n ＝ 1
　For i ＝ 2 To k
If ______②______　 Then
　 n ＝ n ＋ 1
ElseIf n > maxi Then
　 maxi ＝ n
　 ______③______
　 n ＝ 1
　 t ＝ a(i)
Else
　 n ＝ 1
　 t ＝ a(i)
End If
　Next i
　If n > maxi Then
maxi ＝ n
ans ＝ t
　End If
　Text2.Text ＝ Str(ans)
　Text3.Text ＝ Str(maxi)
End Sub
Function delete(st As String, x As Integer, y As Integer) As String
　delete ＝ Mid(st, 1, x － 1) ＋ Mid(st, x ＋ y)
End Function
(1)程序運行時，在文本框Text1中輸入“1，2，2，3，3，4，4，4，4，4，4，4，4，4，5，5”，則在文本框Text3中輸出的內容為____________。
(2)為實現上述功能，在程序①、②、③劃線處填入適當的代碼。
解析　(1)出現相同相鄰數最多的數是4，共有9個，因此答案為9。(2)①處代碼的功能為從左往右依次取出一個字符，若是逗號，則將逗號前面的數字轉換為數值并存儲在數組a中，若不是逗號，則取出下一個字符，因此①處應填入的語句為i＝i＋1；②代碼表示相鄰的整數是否為相同的整數，若是則繼續和后面的整數比較，因此②應填入的語句為a(i) ＝ t。
答案　(1)9　(2)①i＝i＋1　②a(i) ＝ t　③ans ＝ t
四、貪心思想類
7.背包問題。小明編寫了一個求背包最大價值的VB程序，現有n件物品和體積為M的背包，每件物品都有編號、體積和價值，且每件物品都可以任意分割(即可以取走寶貝的一部分)，求裝滿后的背包的最大價值。
程序運行時，在文本框Text1中輸入物品的數量n，單擊“數據讀取”按鈕，則從數據庫讀取前n件物品的編號、價值和體積，分別存儲在數組id、jz、tj中，并顯示在列表框List1中；在文本框Text2中輸入背包的體積，單擊“求解”按鈕Command1后，在列表框List2中顯示依次所取的物品的相關信息，最后，在列表框List2中最后一行顯示背包的總價值。程序運行界面如下圖所示。
求背包最大價值的算法如下：
(1)首先計算出n件物品的單位價值(單位價值＝價值/體積)；
(2)將物品按單位價值降序排序；
(3)然后依次從單位價值最大的物品開始裝入背包，直到裝滿整個背包為止。
(4)輸出裝入背包的物品的相關信息。
實現上述功能的程序如下，請在程序劃線處填入合適的語句或代碼。
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
Dim id(1 To 20) As String　′存儲物品的id號
Dim jz(1 To 20) As Long，tj(1 To 20) As Long ′數組jz、tj分別存儲物品的價值和體積
Dim dwjz(1 To 20) As Single　′存儲物品的單位價值
Dim n As Integer　　　′表示物品數
Private Sub Command1_Click()
　 ′讀取數據庫表中前n條記錄的信息
End Sub
Private Sub Command2_Click()
　Dim m As Integer, i As Integer，j As Integer, p As Integer, tp1 As String, tp2 As Integer
　Dim tp3 As Single
　m ＝ Val(Text2.Text)
　For i ＝ 1 To n
dwjz(i) ＝ jz(i) / tj(i)
　Next i
　For i ＝ 1 To n － 1
For j ＝ n To i ＋ 1 Step －1
　 If ________①________Then
tp1 ＝ id(j): id(j) ＝ id(j － 1): id(j － 1) ＝ tp1
tp2 ＝ jz(j): jz(j) ＝ jz(j － 1): jz(j － 1) ＝ tp2
tp2 ＝ tj(j): tj(j) ＝ tj(j － 1): tj(j － 1) ＝ tp2
tp3 ＝ dwjz(j): dwjz(j) ＝ dwjz(j － 1): dwjz(j － 1) ＝ tp3
　 End If
Next j
　Next i
　i ＝ 1: p ＝ n
　ans ＝ 0
　List2.AddItem “編號”＋“　價值”＋“　　體積”＋“裝入背包的體積”
　Do While m > 0 And p>＝ 1
If m － tj(i) >＝ 0 Then
　 ans ＝ ans ＋ jz(i)
　 List2.AddItem id(i) & “　” & jz(i) & “　” & tj(i) & “　” & m
Else
　 ________②________
　 List2.AddItem id(i) & “　” & jz(i) & “　” & tj(i) & “　” & m
End If
m ＝ m － tj(i)
i ＝ i ＋ 1
　 ________③________
　Loop
　List2.AddItem “背包總價值為：” ＋Str(ans)
End Sub
解析　本題主要考查的是排序算法和貪心算法。貪心算法思想：首先將商品按單位價值降序排序，然后從單位價值的商品開始放入背包，直到放滿整個背包為止，此時背包的價值即為答案。根據算法可知，物品是按照單位價值降序排序，因此①處應填入的語句為dwjz(j) >dwjz(j － 1)；②處語句表示第i件物品部分裝入背包后的總價值，背包還剩下的體積為m，第i件物品的單位價值為dwjz(i)，因此背包的總價值為ans ＝ ans ＋ m * dwjz(i)；變量p表示共有物品的數量，處理完一件物品后，物品的數量將減少一件，因此③處語句為p＝p－1。
答案　①dwjz(j) >dwjz(j － 1) ②ans ＝ ans ＋
m * dwjz(i)　③p＝p－1
8.刪數問題。輸入一個數字串s，刪去其中k個數字(k<數字串中數字的個數)，使剩余數字在保持相對位置不變的情況下構成一個值最小的整數。例如，s＝“19990608”，k＝4，處理結果為：608。
刪數的算法如下：
1)如果k>0，則從前往后檢測相鄰字符，否則，轉3)；
2)①若所有相鄰字符都已非降序，則將串尾k個字符刪去，k值置0，轉1);
②若相鄰兩數存在逆序(即前一個數>后一個數)，則將前一個數刪除，k值變化，然后回到1)；
3)去掉串首的0，輸出結果。
按照上述算法思路，編寫了VB程序，功能如下：在文本框Text1中輸入數字串，在文本框Text2中輸入刪數的個數，單擊“處理”按鈕Command1，在文本框Text3中顯示最小的整數。程序運行界面如圖所示。
(1)如果輸入的數字串為“20160125”，刪除個數為4，則結果是________。
(2)實現上述功能的VB程序如下，請在劃線處填入合適代碼。
Private Sub Command1_Click()
Dim s As String, k As Integer, i As Integer, j As Integer, n As Integer
s ＝ Text1.Text
k ＝ Val(Text2.Text)　　　
n ＝ Len(s)
Do While k > 0
　i ＝ 1
　Do While i < n And ______①______
i ＝ i ＋ 1
　Loop
　If i ＝ n Then
______②______
n ＝ n － k
k ＝ 0
　Else
s ＝ delete(s, i, 1)
n ＝ n － 1
______③______
　End If
Loop
i ＝ 1
Do While n > 1 And Mid(s, 1, 1) ＝ “0”
　 s ＝ delete(s, 1, 1)
　 i ＝ i ＋ 1
　 n ＝ n － 1
Loop
　 Text3.Text ＝ s
End Sub
′自定義函數delete(st，x，y)的功能是在字符串st中刪除x位置開始的y長度的子串。
Function delete(st As String, x As Integer, y As Integer) As String
delete ＝ Mid(st, 1, x － 1) ＋ Mid(st, x ＋ y)
′mid函數第3個參數省略，則截取從開始位置向右到字符串結尾的所有字符
End Function
解析　本題主要考查的是貪心算法。(1)根據刪數規則可知，當輸入的數字串為“20160125”，刪除個數為4時，則先后刪除的數字為：2(最高位上的2)、6、1、5，因此結果為12。(2)程序①處表達式表示尋找一個非降序序列，因此①處語句為Val(Mid(s，i，1))<＝Val(Mid(s，i＋1，1))，也可以寫作Mid(s，i，1)<＝Mid(s，i＋1，1)；程序中②處代碼表示該數字序列為都已非降序時的情況，則刪除后面n個字符即可，因此②處應填入的語句為s ＝delete(s, n － k ＋ 1, k)；程序中③處代碼表示是字符序列為降序時操作，為降序時，則刪除降序序列的首字符，因此數字字符長度減1，刪除的數字字符數也相應減1，即k ＝ k － 1。
答案　(1)12　(2)①Mid(s，i，1)<＝Mid(s，i＋1，1)或Val(Mid(s，i，1))<＝Val(Mid(s，i＋1，1))
②s ＝delete(s, n － k ＋ 1, k)
③k ＝ k － 1
專項測試十一　綜合算法類
一、加密與解密類
1.某數據加密方法描述如下：
(1)輸入的數據僅限數字；
(2)對于輸入的一串由數字組成的字符串按下面方法進行處理：將值最大的數字與最后一個位置上的數字進行交換，值最小的數字與第一個位置上的數進行交換。若一串數字中出現多個最小(或最大)數，僅對出現的第一個最小(或最大)數進行處理。
(3)將處理后的每一位數字轉換為二進制數。
小明按照上述方法，設計了一個數字加密的VB程序，功能如下：單擊“加密”按鈕Command1，程序將文本框Text1中輸入的字符串進行處理和進制轉換，最后在標簽Label3中輸出加密結果。
程序運行效果如圖所示：
實現上述功能的VB程序如下，請回答下列問題：
(1)如果輸入的數據為“395”，則最后在標簽Label1中輸出的結果是________。
(2)為實現上述功能，請在劃線處填入合適的代碼。
Dim a(1 To 100) As Integer
Private Sub Command1_Click()
　Dim s1 As String, s2 As String, s3 As String
　Dim b(1 To 10) As Integer
　Dim i As Integer, t As Integer, j As Integer
　s1 ＝ get(Text1.Text)：s3＝“ ”
　For i ＝ 1 To Len(s1)
　 s2 ＝ “ ”
　 t ＝ 1
　 Do While a(i) < > 0
　　　 __________①__________
　　　 a(i) ＝ a(i) 2
　　　　　t ＝ t ＋ 1
　 Loop
　 For j ＝ t － 1 To 1 Step －1
　　　 s2 ＝ s2 ＋ Str(b(j))
　 Next j
　 __________②__________
　Next i
　Label3.Caption ＝ s3
End Sub
Function get(s As String) As String
　Dim f As String
　Dim i As Integer，min As Integer，max As Integer，k As Integer，n As Integer
　n ＝ Len(s)
　For i ＝ 1 To n
　 a(i) ＝ Val(Mid(s, i, 1))
　Next i
　max ＝ 1: min ＝ 1
　For i ＝ 2 To n
　 If a(i) > a(max) Then max ＝ i
　 If a(i) < a(min) Then min ＝ i
　Next i
　If max < > n Then
k ＝ a(max): a(max) ＝ a(n): a(n) ＝ k
　End If
　If min < > 1 Then
　k ＝ a(min): a(min) ＝ a(1): a(1) ＝ k
　End If
　For i ＝ 1 To n
　 f ＝ f& a(i)
　Next i
　________③________
End Function
2.某數據壓縮方法描述如下：
(1)原始數據中，某數不為0且相鄰無重復，壓縮數據用該數據表示；
(2)原始數據中，某數為0且相鄰無重復，壓縮數據用兩個數表示，第1個為0，第2個為0；
(3)原始數據中，某數據相鄰有重復，壓縮數據用3個數表示：第1個為0，第2個為重復數的個數，第3個為該數本身；
根據上述壓縮方法，對應的解壓縮方法示例如圖a所示。
圖a
小明編寫了一個解壓縮VB程序，功能如下：窗體加載時，自動讀取壓縮數據，依次存儲在數組元素a(1)、a(2)、a(3)……中，壓縮數據的個數存儲在變量n中，壓縮數據顯示在文本框Text1中。單擊“解壓縮”按鈕Command1，程序對壓縮數據依次進行解壓縮處理，解壓縮數據顯示在文本框Text2中。程序運行界面如圖b所示。
圖b
(1)如果壓縮數據為“23，0，21，66，0，0，77，0，5，0”，則解壓縮數據的個數是________。
(2)實現上述功能的VB程序如下。請在劃線處填入合適代碼。
Dim a(1 To 100)As Integer　′存儲壓縮數據，最大處理個數為100
Dim b(1 To 1000)As Integer　′存儲解壓縮數據，最大處理個數為1000
Dim n As Integer′存儲壓縮數據的個數
Private Sub Form_Load()
　′壓縮數據由上述壓縮方法生成
　′本過程用于讀取壓縮數據并存儲在數組a，壓縮數據個數存儲在變量n中
　′代碼略
End Sub
Private Sub Command1_Click()
　Dim pa As Integer′存儲壓縮數組當前處理位置
　Dim pb As Integer′存儲解壓縮數組當前處理位置
　Dim firstdata As Integer，count As Integer，i As Integer
　pa＝1：pb＝1
Do While pa<＝n
　firstdata＝a(pa)
　If firstdata< >0 Then　′示例1情況處理
　 b(pb)＝firstdata
　 pa＝pa＋1：pb＝pb＋1
　 Else
　 count＝a(pa＋1)
　If count＝0 Then　′示例2情況處理
　　 b(pb)＝0
　　 pa＝________①________：pb＝pb＋1
　Else　′示例3情況處理
　　 For i＝1 To count
　　 ________②________
　　 Next i
　　 pa＝pa＋3：　pb＝pb＋count
　End If
　End If
Loop
Text2.Text＝Str(b(1))
For i＝2 To ________③________
Text2.Text＝Text2.Text＋“，”＋Str(b(i))
Next i
End Sub
二、名次計算
3.小王是一位高三的學生，學校剛進行了一次高考全真模擬考試，他的成績不太理想，特別是數學學科，為了更好的對數學成績進行分析，他編寫一個求數學成績在班級排名的VB程序， 學生姓名及數學成績存儲在數據庫文件“score.accdb”的math表中。
程序運行時，在列表框List1中顯示班級同學的姓名及數學成績，在文本框Text1中輸入數學成績，單擊“排名”按鈕(Command1)，在標簽Label4中顯示名次(按數學成績從高到低的名次)，程序運行界面如圖所示。
實現上述功能的VB程序如下，但加框處碼有誤，請改正。
Dim n As Integer　　′n表示學生人數
Dim sx(100) As Single　 ′數組sx存放數學成績
Dim xm(100) As String　 ′數組xm存放學生姓名
Private Sub Form_Load()
　 ′讀入n名學生成績和姓名，分別存儲在數組sx、xm中
　 ′代碼省略
End Sub
Private Sub Command1_Click()
Dim i As Integer, k As Integer, key As Single　　′變量k存放名次
key ＝ Val(Text1.Text)
　　　　　 ′①
For i ＝ 1 To n
If 　Then　　′②
　　　　k ＝ k ＋ 1
End If
Next i
Label4.Caption ＝ Str(k)
End Sub
程序中加框①處應改正為___________________________________________；
加框②處應改正為__________________________________________________。
4.小王編寫了一個依據成績計算名次的VB程序，成績為0到100之間的整數。算法的基本思想：先統計每個分數的個數，然后按照分數從高到低依次計算每個有效分數(該分數的個數不為0)對應的名次，分數相同時名次并列。最高分為第1名，該分數的名次與個數之和為下一個有效分數的名次，以此類推。程序用數組A存放每個分數對應的個數，數組B存放每個分數對應的名次。例如，下表中最高分100有2個，并列第1名，則分數96的名次為分數100的名次加上分數100的個數，即第3名。
分數
100
99
98
97
96
95
94
…
0
個數(A數組)
2
0
0
0
1
0
3
…
0
名次(B數組)
1
3
4
…
程序運行時，學生數據顯示在列表框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 Integer′存放學生人數
Private Sub Form_Load()
　′本過程從數據庫中讀取學生數據，存儲在相應的變量中，并在List1中顯示
　 ′代碼略
End Sub
　 ′整數轉換成長度固定的字符串
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　　′存放每個分數的個數
　Dim 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 recCount ′計算每個分數的個數
______②______
　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
三、綜合類
5.平面上有N(3≤N≤1，00)個房間圍成一圈，按順時針方向分別編號為1～N，相鄰的兩個房間之間均有一扇門，第i個房間居住人數為a(i)。初始時選擇一個房間，將所有人都聚集在該房間，接著每個人都按順時針方向走到相鄰的房間，直到走到居住的房間。一個人每經過一扇門花費 1 的能量，請確定初始房間，使得所有人花費的能量和最小。
例如：N＝5，a(1)＝4，a(2)＝7，a(3)＝8，a(4)＝6，a(5)＝4，最佳方案為：初始時所有人聚集在 2 號房間，花費的能量和：7*0＋8*1＋6*2＋4*3＋4*4＝48。
為了解決這個問題，小明編寫了一個VB程序。在窗體加載時，從數據庫中讀取N的值和編號為1到N的房間的居住人數，人數存儲在數組a中。點擊窗體上的按鈕Command1，程序枚舉每一種方案(不同的初始房間)，計算該方案下的能量和，在文本框Text1中輸出最優方案的初始房間編號，在文本框Text2中輸出最小能量和。
實現上述功能的VB代碼如下，請在程序劃線處填入合適的代碼。
Dim a(1 To 100) As Integer ′依次存儲編號為1到100的房間的最多居住人數
Private Sub Form_Load()
　′本過程從數據庫中讀取N的值和編號為1到N的房間的居住人數，存儲在數組a中
　′代碼略
End Sub
Private Sub Command1_Click()
　Dim i As Integer, j As Integer, w As Integer , k as Integer
　Dim t As Long, ans As Long
　k＝0 : ans ＝ 32767
　For i ＝ 1 To n
t ＝ 0
For j ＝ 0 To n － 1
______①______
　 If w ＝ 0 Then w ＝ n
　 t ＝______②______
Next j
If t < ans Then
　 k＝ i : ans ＝ t
End If
　Next i
　Text1.Text ＝ Str(k)
　Text2.Text ＝ Str(ans)
End Sub
6.設計一個VB程序，實現如下功能：在文本框Text1中輸入一個整數數列(整數間用逗號分隔)，求該數列中連續相同整數最多的數(即相鄰的數相等)，并統計其個數。例如，輸入的整數數列為：1，1，1，2，2，3，3，3，3，4，5，5，5，5，5，5，5，則連續相同整數最多的是5，共有7個。
程序運行時，在文本框Text1中輸入整數序列，單擊“計算”按鈕Command1，在文本框Text2中輸出該數列中連續相同整數最多的數，在文本框Text3輸出個數。程序運行效果如圖所示。
算法說明：
(1)首先將字符串st中的每個整數存儲在數組a中，第k個整數存儲在數組元素a(k)中 。
(2)然后從第一個數開始，依次比較相鄰兩個數，若相等，則連續相同數的個數加1，繼續比較下一對數；若不相等但連續相同整數個數大于maxi，則將結果記錄在maxi，并將當前整數的個數重新計數，然后將當前整數賦給變量t，若不相等且連續相同整數個數不大于maxi，則當前整數的個數重新計數，并將當前整數賦給變量t，繼續比較下一對數。
實現上述功能的VB程序如下，請在劃線處填入合適的代碼。
delete函數說明：delete(st，x，y)為自定義函數，功能為在字符串st中刪除x位置開始的y長度的子串。
Private Sub Command1_Click()
　Dim a(1 To 100) As Integer, st As String
　Dim i As Integer, maxi As Integer, k As Integer，n As Integer, t As Integer
　st ＝ Text1.Text
　k ＝ 0
　i ＝ 1
　Do While i <＝ Len(st)
i ＝ 1
Do While Mid(st, i, 1) < > “，” And i <＝ Len(st)
　　________①______
Loop
k ＝ k ＋ 1
a(k) ＝ Val(Mid(st, 1, i － 1))
x ＝ delete(st, 1, i)
　Loop
　maxi ＝ 0
　t ＝ a(1)
　n ＝ 1
　For i ＝ 2 To k
If ______②______　 Then
　 n ＝ n ＋ 1
ElseIf n > maxi Then
　 maxi ＝ n
　 ______③______
　 n ＝ 1
　 t ＝ a(i)
Else
　 n ＝ 1
　 t ＝ a(i)
End If
　Next i
　If n > maxi Then
maxi ＝ n
ans ＝ t
　End If
　Text2.Text ＝ Str(ans)
　Text3.Text ＝ Str(maxi)
End Sub
Function delete(st As String, x As Integer, y As Integer) As String
　delete ＝ Mid(st, 1, x － 1) ＋ Mid(st, x ＋ y)
End Function
(1)程序運行時，在文本框Text1中輸入“1，2，2，3，3，4，4，4，4，4，4，4，4，4，5，5”，則在文本框Text3中輸出的內容為____________。
(2)為實現上述功能，在程序①、②、③劃線處填入適當的代碼。
四、貪心思想類
7.背包問題。小明編寫了一個求背包最大價值的VB程序，現有n件物品和體積為M的背包，每件物品都有編號、體積和價值，且每件物品都可以任意分割(即可以取走寶貝的一部分)，求裝滿后的背包的最大價值。
程序運行時，在文本框Text1中輸入物品的數量n，單擊“數據讀取”按鈕，則從數據庫讀取前n件物品的編號、價值和體積，分別存儲在數組id、jz、tj中，并顯示在列表框List1中；在文本框Text2中輸入背包的體積，單擊“求解”按鈕Command1后，在列表框List2中顯示依次所取的物品的相關信息，最后，在列表框List2中最后一行顯示背包的總價值。程序運行界面如下圖所示。
求背包最大價值的算法如下：
(1)首先計算出n件物品的單位價值(單位價值＝價值/體積)；
(2)將物品按單位價值降序排序；
(3)然后依次從單位價值最大的物品開始裝入背包，直到裝滿整個背包為止。
(4)輸出裝入背包的物品的相關信息。
實現上述功能的程序如下，請在程序劃線處填入合適的語句或代碼。
Dim conn As New ADODB.Connection
Dim rs As New ADODB.Recordset
Dim id(1 To 20) As String　′存儲物品的id號
Dim jz(1 To 20) As Long，tj(1 To 20) As Long ′數組jz、tj分別存儲物品的價值和體積
Dim dwjz(1 To 20) As Single　′存儲物品的單位價值
Dim n As Integer　　　′表示物品數
Private Sub Command1_Click()
　 ′讀取數據庫表中前n條記錄的信息
End Sub
Private Sub Command2_Click()
　Dim m As Integer, i As Integer，j As Integer, p As Integer, tp1 As String, tp2 As Integer
　Dim tp3 As Single
　m ＝ Val(Text2.Text)
　For i ＝ 1 To n
dwjz(i) ＝ jz(i) / tj(i)
　Next i
　For i ＝ 1 To n － 1
For j ＝ n To i ＋ 1 Step －1
　 If ________①________Then
tp1 ＝ id(j): id(j) ＝ id(j － 1): id(j － 1) ＝ tp1
tp2 ＝ jz(j): jz(j) ＝ jz(j － 1): jz(j － 1) ＝ tp2
tp2 ＝ tj(j): tj(j) ＝ tj(j － 1): tj(j － 1) ＝ tp2
tp3 ＝ dwjz(j): dwjz(j) ＝ dwjz(j － 1): dwjz(j － 1) ＝ tp3
　 End If
Next j
　Next i
　i ＝ 1: p ＝ n
　ans ＝ 0
　List2.AddItem “編號”＋“　價值”＋“　　體積”＋“裝入背包的體積”
　Do While m > 0 And p>＝ 1
If m － tj(i) >＝ 0 Then
　 ans ＝ ans ＋ jz(i)
　 List2.AddItem id(i) & “　” & jz(i) & “　” & tj(i) & “　” & m
Else
　 ________②________
　 List2.AddItem id(i) & “　” & jz(i) & “　” & tj(i) & “　” & m
End If
m ＝ m － tj(i)
i ＝ i ＋ 1
　 ________③________
　Loop
　List2.AddItem “背包總價值為：” ＋Str(ans)
End Sub
8.刪數問題。輸入一個數字串s，刪去其中k個數字(k<數字串中數字的個數)，使剩余數字在保持相對位置不變的情況下構成一個值最小的整數。例如，s＝“19990608”，k＝4，處理結果為：608。
刪數的算法如下：
1)如果k>0，則從前往后檢測相鄰字符，否則，轉3)；
2)①若所有相鄰字符都已非降序，則將串尾k個字符刪去，k值置0，轉1);
②若相鄰兩數存在逆序(即前一個數>后一個數)，則將前一個數刪除，k值變化，然后回到1)；
3)去掉串首的0，輸出結果。
按照上述算法思路，編寫了VB程序，功能如下：在文本框Text1中輸入數字串，在文本框Text2中輸入刪數的個數，單擊“處理”按鈕Command1，在文本框Text3中顯示最小的整數。程序運行界面如圖所示。
(1)如果輸入的數字串為“20160125”，刪除個數為4，則結果是________。
(2)實現上述功能的VB程序如下，請在劃線處填入合適代碼。
Private Sub Command1_Click()
Dim s As String, k As Integer, i As Integer, j As Integer, n As Integer
s ＝ Text1.Text
k ＝ Val(Text2.Text)　　　
n ＝ Len(s)
Do While k > 0
　i ＝ 1
　Do While i < n And ______①______
i ＝ i ＋ 1
　Loop
　If i ＝ n Then
______②______
n ＝ n － k
k ＝ 0
　Else
s ＝ delete(s, i, 1)
n ＝ n － 1
______③______
　End If
Loop
i ＝ 1
Do While n > 1 And Mid(s, 1, 1) ＝ “0”
　 s ＝ delete(s, 1, 1)
　 i ＝ i ＋ 1
　 n ＝ n － 1
Loop
　 Text3.Text ＝ s
End Sub
′自定義函數delete(st，x，y)的功能是在字符串st中刪除x位置開始的y長度的子串。
Function delete(st As String, x As Integer, y As Integer) As String
delete ＝ Mid(st, 1, x － 1) ＋ Mid(st, x ＋ y)
′mid函數第3個參數省略，則截取從開始位置向右到字符串結尾的所有字符
End Function

展開更多......

收起↑