教科版选修一 对分查找变式 课件+练习(共20张PPT)

(课件网) 对分查找变式 基础知识 key不确定情况 key确定情况 代码选填情况 基础知识 （1）基本理念 （2）基本代码 （3）查找次数 （4）中值情况 m=(i+j)\2 m=Int((i+j))/2 m=Int(i+j+1)\2 m=Fix((i+j)/2) m=Fix((i+j)/2+0.5) m=Fix((i+j+0.5)/2) 左 左 右 左 右 左 1.某对分查找算法的部分代码如下： i=1:j=1000:flag=True:p=0 key=val(Text1.Text) Do While i<=j And flag m=(i+j)\2 p=p+1 if a(m)=key Then flag=False if a(m)>key Then j=m-1 Then i=m+1 Loop 数组元素a(1)到a(1000)中存放着升序排列的数据。下列说法正确的是（ ） A.若key的值小于a(1)，则执行该段程序后，变量j的值等于1 B.若key的值等于a(1)，则执行该段程序后，变量p的值等于10 C.若key的值等于a(1000)，则执行该段程序后，变量i的值等于1001 D.无论key的值是否在数值中a中，执行该段程序后，变量i的值均不可能等于m 基础知识 key确定情况 （1）观察key的值 （2）注意分支语句代码块的变化 （3）通过输出进行推导 key确定情况 1.数组元素a(0)到a(9)的值依次为“15,20,25,30,35,40,45,50,55,60”，文本框Text1中输入的是40，执行该程序段，下列描述正确的是（ ） 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 End if if KeyKey Then i=m+1 Else j=m-1 End if Text2.Text=Text2.Text+Str(m) Loop 则在执行该程序后，Text2中显示的内容是（ ） A.5 2 B.5 7 8 C.55 28 37 D.55 37 28 key不确定情况 （1）观察key的取值 （2）注意分支语句代码块的变化 （3）通过二叉树求解 key不确定情况 1.a(1)=2:a(2)=4:a(3)=5:a(4)=6:a(5)=8:a(6)=10:a(7)=11:a(8)=12 n=0 Key=int(Rnd 7)+2 L=1:R=8 Do While L<=R m=(L+R)\2 if Key=a(m) Then Exit Do Elseif a(m)