5.4 对分查找程序应用 导学案 -2021-2022学年高中信息技术浙教版选修1

| 7页
| 367人阅读
| 78人下载
普通

高二信息技术导学案    VB模块   班级            姓名               

《 对分查找程序应用》导学案

[考试要求]

1.对分查找程序实现       (c)

 [学习目标]

1. 对比顺序查找,掌握对分查找的算法思想。

2. 分解对分查找的算法思想,构建对分查找的代码

3. 充分解读和理解对分查找的程序代码     

 [自主学习]

一、 知识梳理

1、 对分查找继续重复进行查找的条件是              

2、 对分查找最多的查找次数(n个数据)               

3、 key与d(mid)的大小比较影响i,j在后续查找中的取值变化:①若d(mid)<key,则i=        ,j不变;②若d(mid)>key,则j=mid-1,i            

二、自我检测

1.完善下方对分查找基本代码,并在空白处对横线所填代码进行注释。

i=1:j=n

x=0

Do While__________

  m=______________

  If d(m)=key Then

      x=m

      Exit Do

  End If

  If d(m)>key Then

      _________

  Else

      _________

  End If

Loop

If x<>0 Then

    list1.additem “查找成功下标为”+str(x)

Else

    list1.additem  “查找失败”

End If

2.某算法程序段如下:

Key=Val (Textl. Text)

Text2. Text=""

i=1:j=9:f= False

Do While i<=j And Not f

   m=(i+j)\2

   If a(m) Mod 10=Key Then

      search=m

      f= True

   Elself a(m) Mod 10>Key Then

       i=m+1

  Else

       j=m-1

  End Ifpage number 0


高二信息技术导学案    VB模块   班级            姓名               

  Text2. Text=Text2. Text+Str(m)

Loop

现数组元素a(1)至a(9)的值依次为19, 28, 37,46, 55, 64, 73, 82, 91,若在文本框Text1中输入29,执行以上程序段后,文本框Text2中显示的内容是(   )

A. 5 7 8             B. 55 73 82           C. 55 28 37            D. 5 21

[课堂练习]

1.某对分查找算法的VB程序段如下:

i=1:j=9:n=0

key=Val(Text1.Text)

Do While i<=j

 n=n+1

 m=Fix((i+j)/2)

 If key=d(m) Then Exit do   'Exit Do 表示退出循环

 If key<d(m) Then j=m-1 Else i=m+1

Loop

数组元素d(1)到d(9)的值依次为“7,12,18,25,39,58,61,72,86”,若该程序段运行结果后,n的值为2,则key的值是(        )

A.39     B.18或61         C.18或72     D.12或61

2.数组元素a(0)到a(9)的值依次为“13,20,22,25,30,33,40,52,65,100”,文本框Text1中输入的值是33,执行该程序段,下列描述正确的是( )  

key = Val(Text1.Text)

i = 0: j = 9:  s = 0

Do While i <= j

  m = Fix((i + j) \ 2 + 0.5)

  s = s + 1

  If key = a(m) Then

     Label1.Caption = Label1.Caption + "→" + Str(m)

     Exit Do  'Exit Do表示退出循环

  End If

  If key < a(m) Then j = m - 1 Else i = m + 1

  Label1.Caption = Label1.Caption + "→" + Str(m)

Loop

Label2.Caption = "历经" + CStr(s) + "步"

A.标签Label1显示内容为“→4→7→5”

B.标签Label2显示内容为“历经1步”

C.该程序为顺序查找,查找次数为3

D.该程序为对分查找,查找次数为4

3.数组a中依次存放6个有序数据“23 33 44 55 66 77”

Dim a(1 To 10) As Integer

Dim s As String ,n ,key As Integer

a(1)=23:a(2)=33:a(3)=44:a(4)=55:a(5)=66:a(6)=77

i=1:j=6:c=0:key=35

Do While i<=j

    c=c+1

    m=(i+j)\2

    If (j-i+1) mod 2=0 Then m=m+1

    If a(m)=key Then Exit Do

    If key<a(m) Then j=m-1 Else i=m+1

Looppage number 1


高二信息技术导学案    VB模块   班级            姓名               

该程序运行后,下列各变量的值不正确的是(     )

A.i=3                   B.j=2                    C.c=3                      D.m=2

4.某查找算法的VB程序段如下:

Key=VaI(Text1. Text)

i=1

j= 10

Do While i<=j

   mid1=i+(j-i)\3

   mid2=j- (j-i)\3

   If a(mid1)=Key Or a(mid2)=Key Then

      Exit Do

   Elself Key<a(mid1) Then

      j= mid1 -1

   Elself Key>a(mid1) And Key<a(mid2) Then

      i= mid1+1

      j= mid2 -1

   Else

     i= mid2+1

   End If

   Text2. Text=Text2. Text+Str(a(mid1))+Str(a (mid2))

Loop

数组元素a(1)到a(10)的值依次为“15, 19, 23, 25, 27,32, 33, 38, 43, 48",若在文本框Text1中输入38,执行垓程序段,文本框Text2中显示的是(  )

A.25 33                B.23 32               C.38 48              D.25 32

[课后练习]

1.已知一无序数组a(下标1到n),通过引入数组b(下标1到n),使得a(b(1))≤a(b(2)) ≤a(b(3))……≤a(b(n))(示例如图所示),对这些有序数据可进行对分查找。则第一次查找时,中点位置m与中点值分别是(      )

A. m的值是Fix((1+n)/2),中点值是 a(m)

B. m的值是Fix((1+n)/2),中点值是 a(b(m))

C. m的值是Fix((b(1))+b(n))/2),中点值是 a(m)

D. m的值是Fix((b(1))+b(n))/2),中点值是 a(b(m))

2.采用如下对分查找算法对数组a中7个有序数据“15,38,51,66,77,81,99”进行查找,查找数据为“55”

i = 1: j = 7: x = 55

Do While i <= j

     m = (i + j) \ 2

     If a(m) = x Then Exit Do

     If a(m) > x Then j = m - 1 Else i = m + 1

Looppage number 2


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。