试题

试题 试卷

logo

题型:单选题 题类:常考题 难易度:普通

浙江省高中信息技术 查找算法及程序实现同步练习

有如下程序段:

Dim i As Integer,j As Integer,Key As Integer,m As Integer,s As String

i=1: j=7: s=“”:flag=False

Key=Int(Rnd()* 50)

Do While i <=j And Not Flag

 m=(i+j)\2

 If Key=a(m) Then

  Flag=True

 ElseIf Key < a(m) Then

  j=m-1

 Else

  i=m+1

 End If

 s=s+Str(a(m))

Loop

Text1.Text=s

数组中a(1)到a(7)的值依次为“23,33,45,56,68,77,89”,则Text1 中显示的内容不可能是(  )

A、56 33 B、56 33 45 C、56 33 23 D、56 77 68 11
举一反三
小朋友拍照:有来自K(1<=K<=20)个不同国家的N(1<=N<=100)个小朋友排成一行准备拍照。国籍用数字1,2,3……K表示,每个小朋友的国籍依次存入数组a(1)到a(N)。由于小朋友太多,没有办法全部被拍入。摄像师决定拍摄一段连续区间内的小朋友,这个区间内每种国籍的小朋友至少要有1个,求满足要求的最小区间长度。

例如有10个小朋友,5种国籍,从左到右排列,国籍编号依次是2,1,2,4,3,3,5,5,3,5,则最小的一段包含所有5种国籍的区间是从第2个到第7个小朋友,区间长度为6。

算法解析:区间的长度至少为K(国籍的数量),最大为N(小朋友的数量)。我们可以通过二分K到N之间的求得最小区间长度。

实现上述功能的VB代码如下,但加框处代码有错,请改正。

Dim a(1 To 100) As Integer   '依次存储为1到100的小朋友的国籍编号

Dim K As Integer

Dim 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       '答案的范围为K到N,即最少K,最多N个小朋友

Do While i <= j   

    M = (i + j) \ 2     '二分,求中间值

    If pd(M) = True Then   '调用Pd函数,判断区间长度为M时,是否包含所有国籍

      j = M – 1 

      ans = M        '若以M为区间长度可包含所有国籍,更新答案

    Else

      i =           '第①处错误

    End If

Loop

Text1.Text = Str(ans)

End Sub

Function pd(M As Integer) As Boolean

Dim f(1 To 20) As Integer  'f(i)表示国籍为i的小朋友是否包含

Dim t As Integer           't用于统计当前区间包含的国籍数量

pd = False

For i = 1 To N - M + 1     '枚举以i为起点的M个小朋友中,各个国籍是否包含

    For j = i To i + M - 1

      f(a(j)) = 1            '等于1,表示国籍为a(j)的小朋友已包含,0表示不包含

    Next j

    t = 0

    For j = 1 To K      '统计已包含的国籍的数量

      t =          '第②处错误

    Next j

    If t = K Then pd = True: Exit Function           '若包含K个国籍,返回True

    For j = 1 To K     'f数组元素重新初始化为0

      f(j) = 0

    Next j

Next i

End Function

用VB编写一个模拟在900个观众中产生10个中奖号码的程序,每位观众用三位数字进行编号,要求产生的10个号码不能重复,并且升序排列输出。

①检查产生号码是否重复:把产生的中奖号码放在数组a中,新产生的号码与已经产生的号码进行一一对比,如果找到相等的数,则重新产生新号码。

②找到新产生号码存放的数组下标:从下标为1的数组元素开始,新号码(第i个号码)分别与他们进行一一比较,找到第一个比新号码大的数,该数所在的下标就是新号码应存放的下标。如果在已经产生的数中没有找到比新号码大的数,则新号码应存放在下标为i的数组元素中。下表以产生第5个号码为例,如果产生的号码是150,第一个比他大的数是a(2),下标为2的数组元素应存放新号码;如果产生的号码是300,则新号码应存放在下标为5的数组元素中。

数组元素

a(1)

a(2)

a(3)

a(4)

数组元素的值

120

188

211

278

③移动数组元素到新的位置:如果在已经产生的号码中找到比新号码大的数,从上一个产生的号码开始,到新号码应存放的数组元素,依次把他们向后面移动。以②中产生150为例,从a(4)开始,让a(5)的值等于a(4),a(4)的值等于a(3),依次类推,直到新号码应存放的数组元素a(2)为止。

④将新产生的号码放在相应的数组元素中。

程序运行的界面如图所示,实现上述功能的VB程序代码如下:

Dim a(10) As Single

Private Sub Command1_Click()

Dim i As Integer, j As Integer

Dim temp As Single, k As Integer ‘temp产生随机数,k随机数存放数组元素的下标

    Randomize

    a(1) = Int(Rnd() * 900 + 100)

    For i = 2 To 10

        temp = Int(Rnd() * 900 + 100)

        If  seach(temp, i - 1)= True  Then

            i = i – 1

        Else

k = i                  

For j = 1 To i - 1

    If temp < a(j) Then k = j: Exit For

Next j

            For j = i - 1 To k Step -1

               a(j + 1) = a(j)

            Next j

                     ①        

      End If

    Next i

    List1.Clear

    For i = 1 To 10

       List1.AddItem Str(a(i))

    Next i

End Sub

‘函数实现在数组a中,从下标为1的数组元素到下标为t数组元素,查找有无pp的数值

Function seach(pp As Single, t As Integer) As Boolean

    Dim i As Integer

    seach = False

    For i = 1 To t

        If       ②          Then seach = True : Exit For

    Next i

End Function

返回首页

试题篮