题库 高中信息

题干

求最长升序子序列的长度。一个数的序列bi,当b1<b2<…<bS的时候,我们称这个序列是升序的。对于给定的一个序列(al,a2,…,aN),我们可以得到一些升序的子序列(ail,ai2,…,aiK),这里1<=il<i2<……<iK<=N。比如,对于序列(1,7,3,5,9,4,8),有它的一些升序子序列,如(1,7),(3,4,8)等等。这些子序列中最长的长度是4,比如子序列(1,3,5,8),小王设计VB程序用于求最长升序子序列的长度,在文本框Text1中输入n个各不相同的数据(各数据之间以逗号隔开),单击“求解”按钮Command1后在标签Labell中输出最长升序子序列的长度,运行界面如图所示。

具体算法描述如下:
①将文本框Text1中的n个数据依次读取到数组a中;
②构造一个数组b(j),j表示升序子序列的长度,b(j)的值表示所有j长度升序序列中最小的末尾元素值。例:序列(2,6,4,5),长度为2的子序列有(2,6),(2,4),(2,5),(4,5),则b(2)=4;
③从第1个元素开始,依次处理到第i(1≤i≤n)个元素为止,b数组所能达到的最大下标值maxlen,处理过程分两种情况:
a)a(i)>b(maxlen),则最长升序子序列的长度增加;
b)a(i)<b(maxlen),则在数组b中逆序查找到第一个b(j)>a(i)(maxlen-1≤j<1),更新数组b中升序子序列长度为j+1时所存储的元素值。
以图中数据为例:

④数组b的最大下标值即为最长升序子序列的长度。
实现上述过程的VB程序如下,请回答下列问题:
(1)若在文本框Text1中输入的序列为(4,7,9,8,6),则数组元素b(2)的值为_____________。
(2)请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim a(1 To 100)As Integer存储原序列
Dim b(1 To 100)As Integer存储各长度序列的最小末尾元素
Dim s As String
Dim n As Integer,i As Integer,j As Integer,maxlen As Integer
S=Text1.Text
n=1:j=1
For i=1 To Len(s)

c=Mid(s,i,1)

If c=","Then

a(n)=Mid(s,j,i-j)
n=n+1
j=i+1
End If
Next i
______
maxlen=1:b(1)=a(1)
For i=2 To n
If a(i)>b(maxlen) Then
maxlen=maxlen+1
b(maxlen) =a(i)
Else
j=maxlen-1:flag=True
Do While j>=1 And flag
If a(i)>b(i)Then
______
flag = False
End If
j=j-1
Loop
If______Then b(1)=a(i)
End If
Next i
Label1.Caption="最长升序子序列的长度为:"+Str(maxlen)
End Sub
上一题 下一题 0.99难度 None 更新时间:2020-03-30 09:43:46

答案(点此获取答案解析)

同类题3

用VB设计一个模拟选手得分程序,在文本框Text1中输入裁判人数(人数大于2),然后点击Command1按钮,在List1中产生70到100的随机数为裁判的打分,去除一个最高分,去除一个最低分,取其他裁判打分的平均分作为最终得分显示在文本框Text2中,运行效果如图所示。

(1)若要在程序运行时,修改窗体显示的标题为“得分计算”,则下面语句可行的是__________。
(单选,填字母:A.Command1.Caption=“得分计算”/B.Form1.Name=“得分计算”/C.Form1.Text=“得分计算”/
A.Form1.Caption=“得分计算”)
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim n As Integer   '裁判人数
Dim max As Integer, min As Integer, sum As Integer
Dim AveScore As Single  '存储最终得分
n = Val(Text1.Text): sum = 0
If n <= 2 Then MsgBox ("输入数据要大于2,请重新输入!")
If n > 2 Then
List1.Clear
Randomize
score = Int(Rnd() * 31) + 70
List1.AddItem Str(score)
_______________________ ' ①
max = score
min = score
For i = 2 To n
score = Int(Rnd() * 31) + 70
List1.AddItem Str(score)
If score > max Then max = score
If score < min Then min = score
sum = sum + score
Next i
AveScore = ______________________ '②
Text2.Text = Str(AveScore)
End If
End Sub
(3)若要将最终得分保留一位小数(四舍五入),下列代码可行的是______________________。
A.AveScore=int(AveScore+0.5)
B.AveScore=int(AveScore*10+0.5)/10
C.AveScore=int(AveScore*100+0.5)/100

同类题4

在数组a中按顺序找出一组升序子序列,可以不连续,但要求长度最长。例如:数组a的值分别为2,11,4,13,5,7。升序子序列分别有2,11、2,4、2,11,13、2,4,13、2,4,5、
2,4,5,7、11,13、4,13、4,5、4,5,7、5,7,其中最长升序子序列的数据是2,4,5,7。

算法思路如下:

(1)求以a(i)为结尾元素的最长升序子序列时,找到所有序号j(j=1,2……i-1),且a(j)<a(i)。

如果这样的元素存在,且d(j)>=d(i)(d(i)记录i位置的最长升序子序列长度),那么就增加i位置的最长升序子序列长度,并记录该升序子序列倒数第二个位置。

(2)在d数组中找出最大值,即最长升序子序列长度。

(3)例如,2、11、4、13、5、7,d(1)=1,d(2)=2,d(3)=2,d(4)=3,d(5)=3,d(6)=4,所以最长升序子序列长度为4,是以a(6)为结尾元素。

现设计了如下VB程序,界面如图所示,请回答下列问题:


(1)观察上图,最长升序子序列的数据是____________________________。
(2)请在划线处填入合适的代码。
Const n = 9
Dim a(1 To n) As Integer
Private Sub Form_Load()

‘生成n个1,10范围的随机数,存储在a数组,并显示在列表框List1。代码略

End Sub
Private Sub Command1_Click()
Dim d(1 To n) As Integer ‘记录i位置的最长升序子序列长度
Dim pre(1 To n) As Integer ‘记录i结尾的最长升序子序列前一数据的位置
Dim st As String,i As Integer,k As Integer,maxlen As Integer
For i = 1 To n

d(i) = 1

Next i
For i = 2 To n

For j = 1 To i-1

If a(j) < a(i) And d(j) >= d(i) Then
d(i) = ___________ 
pre(i) = j
End If

Next j

Next i
maxlen = 0:k = 0
For i = 1 To n

If ___________ Then maxlen = d(i):k = i

Next i
Do While k <> 0

st = a(k) & "," & st

_____________

Loop
Text1. Text = Mid(st,1,Len(st)-1)
End Sub