试题

试题 试卷

logo

题型:综合题 题类:常考题 难易度:困难

浙江省高中信息技术 子序列问题练习

“奔跑吧,兄弟”栏目组要在全国各地挑选节目录制的地点。有来自K(1<=K<=25)个不同省份的N(K<=N<=100)个地区送来了各自的竞选材料。由于参选地区太多,没有办法同时呈现所有材料供评委进行选择。栏目组决定选择一段连续区间内的参选地区,这个区间内每个省份的参选地区至少要有1个,求满足要求的最小区间长度。

参选地区用数字1,2,3……N表示,每个地区所属的省份依次存入数组a(1)到a(N),若1号地区的省份编号是3,即a(1)=3。分析可知,所求区间的长度至少为K(省份的数量),最大为N(地区的数量)。我们可以通过二分K到N之间的数求得最小区间长度。例如有10个参选地区,分别来自于5个不同的省份,从左到右排列,地区编号依次为2,1,2,4,3,3,5,5,3,5,则最小的一段包含所有5个地区的区间是从第2个到第7个地区,区间长度为6。

(1)、若有12个参选地区,分别来自于6个不同的省份,从左到右排列,地区编号依次为2,1,6,4,6,3,1,2,3,5,5,4,则最小的区间长度为
(2)、请在划线处填入合适的代码。

Dim a(1 To 100) As Integer, K As Integer, 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

Do While i <= j

 

 If bh(M) = True Then

  j = M -1

  ans = M

 Else

  i = M+1

 End If

Loop

Text1.Text = Str(ans)

End Sub

Function bh(M As Integer) As Boolean

Dim f(1 To 25) As Integer     ‘f(i)表示是否包含省份为i的地区

Dim t As Integer

bh= False

For i = 1 To N-M + 1     ‘枚举以i为起点的M个地区中各个省份是否都包含

 For j =

  f(a(j)) = 1

Next j

t= 0

For j = 1 To K

 

Next j

If t = K Then bh= True: Exit Function

For j = 1 To K

 f(j) =0

 Next j

Next i

End Function

举一反三
返回首页

试题篮