第5节 子序列问题
模拟演练
1.编写VB程序,实现如下功能:在文本框Text1中输入一个整数,单击“查找”按钮,找出该整数的全部的连续整数固定和,并将它们显示在列表框List1中。所谓一个数n的连续整数固定和,就是指存在a1,a2,…, an,其中ai+1比ai大1,使得a1+a2+…+an。这样a1,a2,…,an称为n的一个连续整数固定和。例如27的全部的连续整数固定和有3组,运行界面如图所示,实现上述功能的程序如下,请在划线处填写合适代码。
Private Sub Command1_Click()
Dim i As Integer, j As Integer, sum As Integer
Dim n As Integer, k As Integer, tmp As String
n = Val (Text1.Text)
sum = 0:List1.Clear
For i = 1 To n-1
j=i
Do While sum < n
① ?
j = j + 1
Loop
If sum = n Then
② ?
For k=i+1 To j-1
tmp = tmp + “+” + Str(k)
Next k
List1.AddItem tmp +“=”+ Str(n)
End If
③ ?
Next i
End Sub
答案 ①sum=sum+j ②tmp=Str(i) ③ sum = 0
解析 循环变量i表示每个连续整数序列的首元素,j依次指向该序列中的每个整数,sum记录该序列的和,若sum=n,则表示找到了满足条件的序列,把该序列拼接成字符串tmp。注意:循环变量k的初始值是i+1,故tmp的初始值为str(i)。若把代码改为For k= i To j-1,则tmp的初始值为空串。把第3空sum=0放在循环体的最后是出题者故意挖坑,事实上把该语句放在Do While sum2.要求从某一字符串中删除指定的字符(假设所含的英文字母均为小写字母),并将处理后的字符串重新输出。
程序界面如图所示,在文本框Text_1中输入原始字符串,在文本框Text_2中输入需要删除的字符,单击“删除此字符”按钮(Command1)后,在文本框Text_3中输出处理后的结果。
解决此问题的算法流程图如图所示,相应的Visual Basic程序如下:
Dim p As String,k As String
Private Sub Command1_Click()
Dim s As Integer,result As String,flag As Boolean
result=“”
p=Text_1.Text
k=Text_2.Text
For s=1 To Len(p)
flag=f(s)
If Not flag Then
result=result+① ?
End If
Next s
② ?
End Sub
Function f(s As Integer)As Boolean
If Mid(p,s,1)=k Then f=True
End Function
(1)解决此问题的算法是 。(选填:顺序查找或对分查找)?
(2)在程序①和②划线处,填入适当的语句或表达式,把程序补充完整。
程序中①划线处应填入 。?
程序中②划线处应填入 。?
答案 (1)顺序查找 (2)①Mid(p,s,1) ②Text_3.text=result
解析 本题主要考查顺序查找的思想方法和程序实现。顺序查找的基本思想是从第一个数据开始,按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定值相等,则查找成功;否则,查找不成功。
(1)本题中的查找范围是字符串p中的所有字符,查找关键字是字符k,通过顺序查找的方法(For s=1 To Len(p)),逐个比较字符k和字符串p中的字符。
(2)函数f(s)是判断字符串p中第s个字符是不是要找的字符k,如果是则返回true,不是则返回false,如果not flag=true,即当前查到的第s个字符不等于k,则将该字符加入字符串变量result中。因此程序中①划线处应填当前查到的第s个字符,即Mid(p,s,1)。
根据题中流程图可知,循环结束时应该输出result,在文本框Text_3中输出,因此②划线处填Text_3.text=result。
连续子序列定义如下:在序列{a1,a2,…,an}中取出一段{ai,ai+1,…,aj},这一段就称为连续子序列。给定长度为n(l < n < 100)的整数序列{a1,a2,…,an}以及整数s(s < 100)。求出总和不小于s的连续子序列中长度最小者。
例如:给定长度为5的整数序列和s=9。
2
3
2
7
1
其中总和不小于9的连续子序列{2,3,2,7}、{2,3,2,7,1}、{3,2,7}、{3,2,7,1}、{2,7}、{2,7,1},长度最小的子序列为{2,7}。
3.小杜编写VB解决上述问题的程序,其功能如下:程序运行时在文本框Text1中输入整数序列(输入的数据保证存在符合条件的子序列),在Text2中输入整数s。单击按钮Command1后在标签Label1上输出总和不小于s的连续子序列,程序运行如图所示。
(1)给定整数序列为{5,1,3,5,10,7,4,9,2,8},整数s=15,符合条件的长度最小的子序列为 。?
(2)实现上述功能的VB程序如下,请在划线处填入合适代码。Dim a(1 To 100) As Integer
Dim sum(0 To 100) As Integer ’sum(i)存储 a(1)+a(2)+…+a(i)的值
Dim n As Integer, s As Integer
Private Sub Form_Load()
’读取整数序列依次存储在数组a中
’读取整数序列长度存储在变量n中
’本过程代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, ans As String
Dim Min As Integer ’存储符合条件的最小长度
Dim iMin As Integer ’存储符合条件子序列的起始位置
s=val(Text2.text)
For i = 0 To n
sum(i) = 0
Next i
① ?
For i = 2 To n
sum(i) = a(i) + sum(i-1)
Next i
Min = n
iMin = 1
For i = 1 To n
j=i
Do While ② And j<= n?
j = j + 1
Loop
If j <= n And j - i + 1 < Min Then
Min = j - i + 1
iMin = i
End If
Next i
ans =“”
For i = iMin To ③ ?
ans = ans + Str(a(i))
Next i
Label1.Caption = “符合条件的子序列为” + ans
End Sub
解析 (1){5,10} (2)①sum(1) =a(1) ②sum(j)-sum(i-1) < s ③iMin+Min-1
(2)需要注意的是数组sum的下标从0开始,且sum(0)=0。因为sum(i)存储a(1)+a(2)+……+a(i)的值,所以我们可以用sum(j)-sum(i-1)表示a(i)+……+a(j)。因为Min和iMin分别存储符合条件子序列的最小长度和起始位置,故我们可以用For i=i Min To iMin+Min-1来遍历长度最小的子序列。
4.“奔跑吧,兄弟”栏目组要在全国各地挑选节目录制的地点。有来自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
答案 (1)7 (2)① M = (i + j) 2 ② i To i + M-1 ③t = t + f(j)
解析 (1)满足要求的最小区间为4,6,3,1,2,3,5,区间长度为 7。
(2)程序用M表示区间的长度,最小为K,最大为N,通过二分K到N之间的数求得最小区间长度ans。自定义函数bh(M As Integer)用来判断长度为M的区间是否能包含所有省份,循环变量i指向长度为M的区间的左边界,代码For j = i To i + M - 1表示遍历该区间内的各个地区,每次遍历该区间前先设置数组f的所有元素值均为0(题目中把该段代码放在了内层循环后面,实际上放在前面更好理解),若某个省份编号a(j)出现过,则令f(a(j))=1,然后用t来统计出现过的省份数量,最后判断t是否等于K,若相等则表示包含所有省份,返回 True。注意:第③空答案也可以是If f(j) = 1 Then t = t + 1。
课件9张PPT。
第5节 子序列问题 一个字符串的子串是指该串的一个连续的局部。如果不要求连续, 则可称为它的子序列。比如对“abc”而言, “ab”“ac”“bc”都是 它的子序列。子序列包括子串。同样数组的局部也称为数组的子序列。
1.求数组最大连续子序列和
例如a(l),a(2),a(3),a(4),a(5),a(6)的值分别为-2,11, -4, 13,-5, -2时,最大连续 子序列和为20,即a(2)+a(3)+a(4)。
s = 0 : ans = 0 ’ans存储最大子序列和
For i = 1 To n
s = s + a(i)
If s > ans Then ans = s
If s < 0 Then s = 0
Next i2.求数组最长连续上升子序列个数
例如a(l),a(2),a(3),a(4),a(5),a(6)的值分别为2, 1, 3, 7, 5, 8时,最长连续上 升子序列1、3、7,即a(2)、a(3)、a(4)。tmp = 1 : ans = 0 ’ans存储最长连续上升子序列个数
For i = 2 To n
If a(i) > a(i-1) Then tmp = tmp + 1 Else tmp = 1
If tmp > ans Then ans = tmp
Next i3.数组最长上升子序列的个数
序列:2 7 1 5 6 4 3 8 9,最长上升子序列个数为5,该序列为2 5 6 8 9。下面代码中:a(i)存储原始序列,d(i)是以a(i)结尾的最长子序列个数。
max = 0 ’max存储最长上升子序列个数
For i = 1 To n
d(i) = 1
For j = 1 To i – 1
If a(j)< a(i) And d(j) + 1 > d(i) Then d(i) = d(i) + 1 Next j
If d(i) > max Then max = d(i)Next i4.求字符串的所有子串
For i=1 to len(s)
For j=1 to len(s)-i+1
Print Mid(s,j,i)
Next j
Next i
说明:要求是连续字符组成的子串。i是长度,j是起始位置。5.统计递增段个数
k=1
For i=2 to len(s)
If Mid(s,i,1)>Mid(s,i-1,1) Then
k=k+1
If k=2 Then m=m+1
Else
k=1 End IfNext
说明:m是递增段个数,如:s=“abcddecaab”,递增段有“abcd”“de” “ab”,因此m=3。6.最长相同子串
k=1:max=1
For i=2 to len(s)
If Mid(s,i,1)=Mid(s,i-1,1) Then
k=k+1
Else If k>max Then
max=k:pos=i End If
k=1
End If
Next
s1=Mid(s,pos-max+1,max)
说明:如s=“ABCCDDDDDFFG”,最长相同子串s1=“DDDDD”。
