当前位置: 高中信息技术 / 综合题
  • 1. (2019高三上·浙江月考) 求最长升序子序列的长度。一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是升序的。对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些升序的子序列(ai1, ai2, ..., aiK),这里 1 <= i1 < i2 < ...<iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些升序子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)。小王设计VB程序用于求最长升序子序列的长度,在文本框Text1中输入n个各不相同的数据(各数据之间以逗号隔开),单击“求解”按钮Command1后在标签Label1中输出最长升序子序列的长度,运行界面如图所示。

    具体算法描述如下:

    ⑴将文本框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. (1) 若在文本框Text1中输入的序列为(4,7,9,8,6),则数组元素 b(2)的值为
    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(j) Then

      flag = False End If

      j = j - 1 Loop

      IfThen b(1) = a(i)

      End If Next i

      Label1.Caption = "最长升序子序列的长度为:" + Str(maxlen)

      End Sub

微信扫码预览、分享更方便