资源简介

(共38张PPT)
专题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 keya(2*i＋1)<＝a(2*i)
a(2*i＋1)
a(2*i)
a(2*i＋1)
a(2*i＋2)
5.如区间[8，11]，[9，13]此类区间相交，第i个区间和第i＋1个区间(如区间[8，11]，[9，13]相交)的并集开始、结束位置是__________、__________；如区间[2，7]，[4，6]此类相交，第i个区间和第i＋1个区间的并集开始、结束位置是__________、______。
二、判断某个数key是否在n个区间(已按区间的开始位置进行升序排列)的方法
Key＝Val(Text1.Text): flag＝False
If 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____②____ Else ____③____
Loop
If ____④____ Then
Text1.Text＝key & ”同学的成绩是”＋____⑤____
Else
Text1.Text＝ ”没有找到”&key&”同学的成绩”
End If
答案　①((i＋j)\2)*2－1　②i＝(m＋1)/2＋1 或 i＝(m＋1)\2＋1　③j＝(m＋1)\2－1　④i<＝j　⑤Str(a(m))
解析　变量m表示的是中间学生的姓名，与例题中所填内容相同，那么该学生的序号为(m＋1)\2或(m＋1)/2，i向后移动1个位置，或者j向前移动一个位置。找到时中间退出循环，因此满足条件i<＝j。
考点二　区间的相关计算
【例2】 编写“区间覆盖”程序，实现如下功能：输入数轴上的若干个封闭区间范围(均为正整数且左坐标<右坐标)，单击“统计”按钮，计算覆盖所有区间所需的数据点的个数。例如：依次输入区间：[2，5]，[4，7]，[1，4]，[5，9]，[4，5]，[2，4]。坐标点“4”覆盖了[2，5]，[4，7]，[1，4]，[4，5]，[2，4]共5个区间，坐标点“9”覆盖了[5，9]区间，所以覆盖这6个区间所需的坐标点数为2个。
程序运行界面如图所示。实现上述功能的VB代码如下：
Private Sub Count_Click()
Dim right As Integer, t As Integer, k As Integer
Dim tmp As Integer, i As Integer, ans As Integer
Dim n As Integer, a(1 To 100) As Integer
′把输入的n个正整数区间左右坐标依次存放到数组a(1)到 a(2*n)中，代码略
For i＝1 To n－1
k＝t
For j＝i＋1 To n
If a(2*j－1)Next j
If k <>t Then
tmp＝a(k): a(k)＝a(t): a(t)＝tmp
tmp＝a(k＋1): a(k＋1)＝a(t＋1): a(t＋1)＝tmp
End If
Next i
____①____ ′填空
ans＝1：t＝3
Do While t<2*n
　If ____②____ Then　　′填空
If a(t ＋ 1)　Else
ans＝ans ＋ 1
right＝a(t ＋ 1)
　End If
　____③____　　′填空
Loop
Text2.Text＝Str(ans)
End Sub
(1)加框处代码有误，请修改。
(2)运行以上程序后，区间[4，7]和[4，5]________(填：是/否)会交换位置。
(3)若两个区间具有相同的开始位置，按结束位置升序排列，则划线处代码If a(2*j－1)(4)将程序的空白处填写完整。
答案　(1)k＝2*i－1　(2)是　 (3)a(2*j－1)解析　从比较语句a(2*j－1)【例3】 经过排序的n区间(按每个区间的开始位置升序排列)有些是重叠的，如区间[2，7]和[3，5]可以合并为[2，7]，编写程序实现将可以合并的区间进行合并，实例该功能的主要程序可以由下列两个程序段完成。
(1)在下列两段代码中，变量m分别代表的含义是______①____、____②____。
(2)将空白处填写完整。
i＝a(1): j＝a(2): m＝3: t＝1 Do While m <＝ 2*n－1 If____①____Then 　　　　If a(m＋1)>j Then j＝a(m＋1) Else 　　b(2*t－1)＝i 　　b(2*t)＝j 　　t＝t＋1 　　i＝a(m) 　　j＝a(m＋1) End If ____②____ Loop b(2*t－1)＝i b(2*t)＝j i＝a(1): j＝a(2): m＝2: t＝1
Do While m <＝ n
If____①____ Then
　If a(2*m)>j Then j＝a(2*m)
Else
　　b(2*t－1)＝i
　　b(2*t)＝j
　　t＝t＋1
　　i＝a(2*m－1)
　　j＝a(2*m)
End If
____②____
Loop
b(2*t－1)＝i
b(2*t)＝j
答案　(1)①m表示每个区间的开始位置　②m表示当前第几个区间　(2)左边程序段①a(m) <＝ j　②m＋2　右边程序段①a(2*m－1) <＝ j　②m＋1
解析　左边的程序段中，m从3循环至2*n－1，可知m表示每个区间的开始位置，m＋1表示结束位置。从语句b(2*t－1)＝i来看，变量t表示合并后区间的个数，当两区间不相交时，产生一个新的区间，因此①表示当前区间与前面的区间有交集。当一个区间处理好后，将处理下一个区间，因此下个区间的开始位置在m＋2。右边的程序段中，m从2循环至n，可知m表示当前第几个区间，下一个区间为m＋1。
【变式2】 小王编写“模拟IP过滤器”程序，假设IP地址均采用十进制数表示，程序功能如下： 程序运行时，在列表框List1中显示能通过过滤的IP区间(IP区间按起始端点升序排序)，在文本框Text1中输入需要判断的IP地址，单击“验证”按钮Cmd1，若IP区间有重叠区间则作合并处理，并显示在列表框List2中，然后对输入的IP地址进行判断，判断结果显示在标签Label4中。程序运行界面如图所示：
(1)Cmd1对象属于________类(单选，填字母：A.Form/ B.Label/ C.TextBox/ D.CommandButton)。
(2)实现上述功能的VB程序如下，请在划线处填入合适的代码。
(3)程序中加框处代码有错，请改正。
Dim a(1 To 100) As Integer, n As Integer
Private Sub Form_Load()
′本过程从数据库中读取n个IP地址区间数据，并依次存入数组a(1)、…、a(2*n)中
′对能通过过滤的IP区间按区间起始端点升序排序
′代码略
End Sub
Private Sub Cmd1_Click()
Dim ip As Integer, L As Integer, R As Integer
Dim i As Integer, pos As Integer, f As Boolean
ip＝Val(Text1.Text)
L＝a(1): R＝a(2): i＝3: pos＝1′合并重叠区间
Do While i <＝ 2*n－1
If____①____Then
　　　　If a(i＋1)>R Then R＝a(i＋1)
Else
　　　　a(2*pos－1)＝L
　　　　a(2*pos)＝R
　　　　pos＝pos＋1
　　　　L＝a(i)
　　　　R＝a(i＋1)
End If
　　____②____
Loop
a(2*pos－1)＝L: a(2*pos)＝R
′依次输出排序合并后的区间数据，代码略
Label4.Caption＝”IP需过滤”
Else
　i＝1: f＝False
　Do While i <＝ pos And Not f
　　　　If____③____ Then
　　　　　　i＝i＋1
　　　　Else
　　　　　 Label4.Caption＝”IP不需过滤”
　　　　　 f＝True
　　　　End If
　Loop
　　　　If f＝False Then Label4.Caption＝”IP需过滤”
End If
End Sub
答案　(1)D　(2)①a(i)<＝R　 ②i＝i＋2　③Not(ip>＝a(2*i－1) And ip<＝a(2*i))或a(2*i－1)>ip Or a(2*i)a(2*pos) 或ipR
解析　变量i从3循环 2*n－1，因此i表示第2个区间到第n个区间的开始位置，且下一个区间的开始位置是当前位置加2。pos表示合并以后的区间个数，L和R是合并后每段区间的开始位置和结束位置。判断两个区间是否相交的条件是：该区间的开始位置小于或等于合并后区间的结束位置，若两个区间相交，当前区间的结束位置比相交后的结束位置还要大，将更新合并区间的结束位置。若不相交，则将产生一个新的合并区间，需记录新区间的开始和结束位置。判断某个ip是否在合并的区间内，首先判断他与第1个区间的开始位置值a(1)和最后一个区间的结束位置的值a(2*pos)进行比较，若在这两个值之间，再对pos个区间逐个进行判断，若不在当前区间内，将进行下一区间的查找。
1.数组元素 a(1)～a(2*n)中存储的一批正整数，以两个数一组，每组中第一个数均比前一组中第一个数要大。现用对分查找的思想，设计一个在数组 a 中查找数据 key 的程序 ，如果找到 key，在标签 Label1 上显示“yes”，否则显示“no”。
key＝Val(Text1.Text)
i＝1: j＝n*2 : flag＝False
Do While i＋1 <＝ j And Not flag
m＝(i＋j)\2
If____①____Then m＝m－1
If a(m)＝key Or a(m＋1)＝key Then
flag＝True
ElseIf a(m)>key Then
　　____②____
Else
　　____③____
End If
Loop
If a(i)＝key Or a(j)＝key Then flag＝True
If flag Then Label1.Caption＝”yes” Else Label1.Caption＝”no”
划线处的代码正确的是(　　)
A.①m Mod 2＝1　②j＝m－1　③i＝m＋2
B.①m Mod 2＝0　②j＝m－2　③i＝m＋2
C.①m Mod 2＝1　②j＝m－2　③i＝m＋2
D.①m Mod 2＝0　②j＝m\2－2　③i＝m\2＋2
解析　数组元素每两个数为一组，其中第1个数是有序的，因此当i＋1＝j时，区间只剩下最后一个数据了。从语句a(m)＝key Or a(m＋1)＝key来看，位置m是一对数中前面的个位置，因此根据公式m＝(i＋j)\2计算出m是偶数时，应将m前移一位。如果没有找到，找到每组数中第1个位置，因此往前或往后移2个位置。
B
2.给定n个已经按左边界升序排序的闭区间[a(i)，a(i＋1)](其中 i＝l，3…，2* n－1，将其中两个相邻或相交的闭区间合并为一个闭区间(例如：[1，2]和[2，3]可以合并为[1，3]，[1，3]和[2，4]可以合并为[l，4]，但是[1，2]和[3，4]不可以合并)。实现该功能的VB程序段如下：
k＝1
b(1)＝a(1): b(2)＝a(2)
For i＝3 To 2*n－1 Step 2
b(k*2)＝a(i＋l)
Else If a(i)>b(k*2) Then
k＝k＋l
b(k*2－1)＝a(i)
b(k*2)＝a(i＋1)
End If
Next i
要使程序实现上述算法思想， 则方框中的语句是(　　)
A.a(i)>b(k* 2) And a(i＋1)<＝b(k*2)
B.a(i)<＝b(k*2－1) And a(i＋1)>b(k*2－1)
C.a(i)<＝ b(k*2) And a(i＋1)>b(k*2)
D.a(i)>b(k*2－1) And a(i＋1)<＝b(k*2－i)
解析　k表示合并后区间的个数，变量i值依次为3，5，7，……2*n－1，表示从第2个区间开始的每个区间的开始值。当条件a(i)>b(k*2)成立时，表示当i个区间与前面的区间不相交，将新增一个区间，并记录新增区间的开始值和结束值。数组元素b(k*2)记录了新增区间的结束值，当第i个区间的开始值小于等于上一个区间的结束值b(k*2)，表示两个区间有重叠，若同时满足当第i个区间的结束值a(i＋1)大于上一个区间的结束值，可以更新新增区间的结束值。
C
3.数组a中存储的是两个数列交替排序的n个正整数，下标为奇数的数组元素都是奇数且为升序排列，下标为偶数的数组元素都是偶数且为降序排列。排序示例如下。
依据对分查找思想，设计一个在数组a中查找数据key的程序，实现该功能的VB程序如下，请回答下列问题：
(1)观察程序代码，该事件处理过程名为________。
Private Sub Search_Click()
Const n＝10
Dim a(1 To n) As Integer
Dim i As Integer, j As Integer, m As Integer, f As Boolean, key As Integer
′读取一组正整数，按上述规则存入数组 a 中。代码略
a(1) a(2) a(3) a(4) a(5) a(6) a(7) a(8) a(9) a(10)
1 10 3 8 5 6 7 4 9 2
key＝Val(Text1.Text)
If key Mod 2＝1 Then i＝1 Else i＝2
j＝n: f＝False
Do While i <＝ j And Not f
If key Mod 2＝0 Then
m＝(i＋j)\2－(i＋j)\2 Mod 2
Else
m ＝____①____
End If
If key＝a(m) Then
f＝True
j＝m－2
Else
i ＝____②____
End If
Loop
If f Then Label1.Caption＝Str(m) Else Label1.Caption＝”不存在”
End Sub
(2)程序中加框处代码有错，请改正。
(3)请补充划线处语句。
答案　(1) Search_Click()　(2)key Mod 2＝0 And key>a(m) Or key Mod 2＝1 And key解析　本题考核的是对分查找的基本算法。根据key的奇偶性，在数组的奇数位或偶数位进行查找，关键在于判定中间m处于奇数位还是偶数位。对(i＋j)\2进行讨论，若该数是偶数，那么(i＋j)\2 Mod 2＝0，两者之和为偶数；若该数是奇数，那么(i＋j)\2 Mod 2＝1，两者之和为偶数。反之，若要使得m的值为奇数，应将(i＋j)\2加上或减去((i＋j)\2＋1)Mod 2。由于奇数是升序的，偶数是降序的，因此要分两种情况进行讨论。在条件语句中，分为找到了，移动j在左区间继续查找和在右区间进行查找三种情况，因此左区间i要向后移动2个位置。
4.数组a保存n个(n≤1000区间的端点：数组元素a(1)、a(2)保存第1个区间左、右端点，a(3)、a(4)保存第2 个区间左、右端点，……区间排序方法(以升序为例)：先按区间的左端点进行升序排序，当左端点相同时，再按右端点升序排序。示例：[1，2]，[3，5]，[5，6]，[3，4]升序排序后的结果为： [1，2]，[3，4]，[3，5]，[5，6].小沈基于选择排序思想对n个区间进行升序排序并进行了优化，VB程序如下，将空白处填写完整。
Dim a(1 To 2*1000) As Integer
′读取n个区间的左、右端点值存数组a，代码略
′本函数判断a数组中第i区间是否大于第j区间，如果是则返回True，否则返回False
Function IsLarger(i As Integer, j As Integer) As Boolean
If a(2*i－1)>a(2*j－1) Or____①____Then
IsLarger＝True
Else
IsLarger＝False
End If
End Function
Private Sub Command1_Click()
Dim i As Integer, j As Integer, p As Integer, q As Integer
Dim iMax As Integer, iMin As Integer
p ＝1: q＝n
Do While piMax＝p: iMin＝p
For i＝p＋1 To q
If IsLarger(i, iMax) Then iMax＝i
If____②_____ Then iMin＝i
Next i
t＝a(2*iMin－1): a(2*iMin－1)＝a(2*p－1): a(2*p－1)＝t
t＝a(2*iMin): a(2*iMin)＝a(2*p): a(2*p)＝t
If i Max＝p Then____③____
t＝a(2*iMax－1): a(2*iMax－1)＝a(2*q－1): a(2*q－1)＝t
t＝a(2*iMax): a(2*iMax)＝a(2*q): a(2*q)＝t
p＝p＋1: q＝q－1
Loop
′输出排序结果，代码略
End Sub
答案　①a(2*i－1)＝a(2*j－1) And a(2*i)>a(2*j)　②Not IsLarger(i, iMin)或IsLarger(iMin，i)　③iMax＝iMin
解析　先按区间的左端点进行升序排序，当左端点相同时，再按右端点升序排序。因此在自定义函数中，第i个区间排在第j个区间的后面有两个条件。若要找出最前面的区间，该区间应排在iMin的前面。若最后面(最大的)的区间在交换前在位置p时，当把最前面(最小的)的区间与P位置区间交换，最大的区间已经在原来最小区间的位置。

展开更多......

收起↑