题型：综合题 题类：常考题 难易度：困难
浙江省东阳中学2016-2017学年高二下学期信息技术入学考试（寒假作业检测）试卷
例如有10个小朋友，5种国籍，从左到右排列，国籍编号依次是2，1,2,4,3,3,5,5,3,5，则最小的一段包含所有5种国籍的区间是从第2个到第7个小朋友，区间长度为6。
算法解析：区间的长度至少为K（国籍的数量），最大为N（小朋友的数量）。我们可以通过二分K到N之间的求得最小区间长度。
实现上述功能的VB代码如下，但加框处代码有错，请改正。
Dim a(1 To 100) As Integer '依次存储为1到100的小朋友的国籍编号
Dim K As Integer
Dim N As Integer
Private Sub Form_Load() '窗体加载，生成数据
'产生N的值，表示人数
'产生K的值，表示国籍种数
'产生编号为1到N的小朋友的国籍编号，并存储在数组a中
'代码略
End Sub
Private Sub Command1_Click() '使用二分的思想计算最小区间
Dim M As Integer
i = K: j = N '答案的范围为K到N，即最少K，最多N个小朋友
Do While i <= j
M = (i + j) \ 2 '二分，求中间值
If pd(M) = True Then '调用Pd函数，判断区间长度为M时，是否包含所有国籍
j = M – 1
ans = M '若以M为区间长度可包含所有国籍，更新答案
Else
i = 
'第①处错误
End If
Loop
Text1.Text = Str(ans)
End Sub
Function pd(M As Integer) As Boolean
Dim f(1 To 20) As Integer 'f(i)表示国籍为i的小朋友是否包含
Dim t As Integer 't用于统计当前区间包含的国籍数量
pd = False
For i = 1 To N - M + 1 '枚举以i为起点的M个小朋友中，各个国籍是否包含
For j = i To i + M - 1
f(a(j)) = 1 '等于1，表示国籍为a(j)的小朋友已包含，0表示不包含
Next j
t = 0
For j = 1 To K '统计已包含的国籍的数量
t = 
'第②处错误
Next j
If t = K Then pd = True: Exit Function '若包含K个国籍，返回True
For j = 1 To K 'f数组元素重新初始化为0
f(j) = 0
Next j
Next i
End Function
|
位置 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
数据 |
64 |
67 |
45 |
145 |
|
269 |
|
|
|
119 |
1275 |
试题篮
