专项测试十一 综合算法类
一、加密与解密类
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
