(课件网) 专题27 区间交集和并集问题 n 个区间的开始和结束位置分别按顺序存储在数组a(1)至 a(2*n)，如第 1、2、3、4、5 个区间分别为[2，7]，[4，6]，[8，11]，[9，13]，[15，18]；在数组中的存储如下表所示。 第1个区间 第2个区间 第3个区间 第4个区间 第5个区间 a(1) a(2) a(3) a(4) a(5) a(6) a(7) a(8) a(9) a(10) 2 7 4 6 8 11 9 13 15 18 一、区间位置的表示方法 1.第i个区间的开始位置和结束位置分别是_____、_____。 2.输入一个数key，判断该数不在第i个区间的条件(两种方法表示)_____ _____ 或 _____。 3.第i个区间和第i＋1个区间(已升序排列，下同)是否有交集的条件是_____。 4.如区间[8，11]，[9，13]此类区间相交，第i个区间和第i＋1个区间的交集开始、结束位置是_____、_____；区间[2，7]，[4，6]此类区间相交第i个区间和第i＋1个区间的交集开始、结束位置是_____、_____。 2*i－1 2*i Not (key>＝ a(2*i－1) And key<＝a(2*i)) key>a(2*i) Or key＝a(1) And key<＝a(2*n) Then i＝1 Do While i <＝ n And Not flag a(2*i－1) a(2*i＋2) a(2*i－1) a(2*i) If _____Then flag＝True: Exit Do i＝i＋1 Loop End If If flag Then s＝”该数在第”＋Str(i)＋”个区间中” Else s＝”该数不在这些区间中” End If key>＝a(2*i－1) And key<＝a(2*i) 考点一 区间位置的表示方法 用两个值来表示每个对象，n个对象存储在2*n个数组元素中，则第i个对象的两个值的在数组元素中下标的表示方法是：2*i－1，2*i。 【例1】 把n个学生成绩由高到低排序后，按姓名在前、成绩在后的顺序依次存储在2*n个元素的数组a中。例如(“张三”，“97”，“李四”，“92”，“王五”，“87”，……)。设计一个VB程序，利用对分查找思想实现在数组a中查找成绩为Key的学生姓名。VB程序段如下： i＝1：j＝n ———n代表学生的数量 Key＝Val(Text1.Text) Do While i <＝ j If Val(a(m))>Key Then i＝m\2 ＋ 1 Else j＝m\2－1 Loop j＝j ＋ 1 Do While j <＝ n If _____ Then List1.AddItem a(2*j－1) ＋ ”” ＋ a(2*j) Else Exit Do End If j＝j ＋ 1 Loop (1)上述程序中方框处可能的语句是( ) A.(i＋ j)\2 B.(i＋j)/2 C.((i＋j)\2)*2 D.((i＋j)\2)/2 (2)划线处的语句补充完整。 答案 (1)C (2)Val(a(2*j))＝Key 解析 每个学生有2个信息，那么第i个学生的姓名存储在a(2*i－1)中，成绩存储在a(2*i)中，从程序的比较语句Val(a(m))>Key中来看，变量m表示的是中间学生的成绩，因此先找出中间的学生(i＋j)\2序号，再将该序号乘以2。在对分查找中，若找到相应成绩并没有退出(无Exit Do语句)，而是向前继续查找，因此查找结束后，i＝j＋1，此时i或者j－1就是第1个与key相等的学生，那么第i个学生后面还有可能有学生成绩等于key，并要求把这些学生也输出来。 【变式1】 把学生按姓名升序排列，按姓名在前、成绩在后的顺序依次存储在数组a中。设计一个VB程序，利用对分查找思想实现在数组a中查找姓名为Key的学生成绩。 i＝1：j＝n———n代表学生的数量 Key＝Text1.Text Do While i <＝ j ____①____ If a(m)＝Key Then Exit Do If a(m)>Key Then____②____ ... ...
