VB专题 贪心算法连续子序列及找最优解 训练-浙江省2022届高三信息技术一轮复习

贪心算法——寻找最优解 1、(2020年精诚联盟15)根据对分查找的思想来查找两个递增序列中最小值所在的位置，其中第一个递增序列中的数据全部大于第二个递增序列中的数据，且两个序列中没有重复数据，如组合序列3、4、5、6、1、2是由两个递增序列“3、4、5、6”和“1、2”组成的，组合序列的最小值是1，在组合序列中的位置是第5位。 为实现上述功能，小王编写如下VB程序，首先在Text1中输入两个满足条件的序列，数字之间用“，”隔开且以“，”结尾，单击按钮“Cod1”，在Text2中输出最小值所在序列中的位置，程序运行界面如下图所示， （1）在界面中，具有Caption属性的对象有 个。 （2）在横线处填入合适的代码。 （3）加框处的表达式有误，请改正。 Private Sub Codl_Click() Dims As String, ch As String Dim i As Integer,j As Integer,n As Integer,c As Integer Dim a(100) As Integer s=Text1. Text:c=0:n=0 For i=1 To Len(s) ch=Mid(s,i,1) If ch>="0"And ch<="9"Then ① Else n=n+1 ② c=0 End If Next i i=1：j=n Do While i<=j m=（i+j）\2 If a（m）>a（i）Then i=m else j=m Loop ③ End Sub 2、（2019年10月浙江五校16）求最长升序子序列的长度。一个数的序列 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 中输出最长升序子序列的长度，运行界面如第 16 题图所示。 具体算法描述如下： 第 16 题图 （1）将文本框 Text1 中的 n 个数据依次读取到数组 a 中； （2）构造一个数组 b(j)，j 表示升序子序列的长度，b(j)的值表示所有 j 长度升序序列中最小的末尾元素值。例：序列(2,6,4,5)，长度为 2 的子序列有(2,6)、(2,4)、(2,5)、(4,5)，则 b(2)=4； （3）从第 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 时所存储的元素值。 以第 16 题图中数据为例： （4）数组b 的最大下标值即为最长升序子序列的长度。实现上述过程的 VB 程序如下，请回答下列问题： ①若在文本框 Text1 中输入的序列为(4,7,9,8,6)，则数组元素 b(2)的值为 。 ②请在划线处填入合适的代码 Private Sub Command1_Click() Dim a(1 To 100) ，b(1 To 100)As Integer '存储原序列 Dim s As String， 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) Th