资源简介

专题九　其他常用算法
1．(2019·4月浙江省选考)小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将数组a中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。算法的VB程序段如下，但加框处代码有错，请改正。
′待排序数据存储在数组a中(a(1)～ a(n))，要求升序排列
For i ＝ 1 To (n － 1) 2
　For j ＝ 1 To n － i * 2
If Then′(1)
　 t ＝ a(j): a(j) ＝ a(j ＋ 2): a(j ＋ 2) ＝ t
End If
　Next j
Next i
For i ＝ 1 To n 2
　j ＝ 2 * i － 1
　If a(j) > a(j ＋ 1) Then t ＝ a(j): a(j) ＝ a(j ＋ 1): a(j ＋ 1) ＝ t
Next i
For i ＝ Step 2′(2)
　t ＝ a(i): j ＝ i － 1
　Do While t < a(j)
a(j ＋ 1) ＝ a(j): j ＝ j － 1
　Loop
　a(j ＋ 1) ＝ t
Next i
解析　插入排序也是经常要考到的问题。先是分别对奇数位和偶数位进行排序，排序后再使偶数位大于前面的元素，最后进行插入排序，只需要对奇数位进行插入排序即可。仅奇数位插入排序，i从1时会导致出现a(0)下标越界，所以i从3开始，即第二空答案为3 To n。
答案　(1)a(j)>a(j＋2) 　(2)3 To n
2．(2018·11月浙江选考)某种数据加密方法描述如下(加密前后的数值都是0～255的整数)：
?以m个数据为一段，将n个待加密数据依次分割成若干个数据段。剩余数据(个数小于m)为一个独立数据段。
?数据段加密规则：
数据个数等于m的数据段，先进行值变换，再进行位置变换，得到加密数据段。
数据个数小于m的数据段，只进行值变换，直接得到加密数据段。
?依次合并加密数据段，即为最后的加密数据。
值变换：用值变换密钥数组x(元素个数为m，值为0～255的整数)，将待加密数据段中的数据进行值变换，方法如下：
值变换后第i个元素＝(待加密数据段第i个元素＋x(i))Mod 256，其中i＝1，2，…，m
位置变换：用位置变换密钥数组y(元素个数为m，值为1～m的不重复整数)，将上述值变换后的m个元素进行段内位置变换，方法如下：
加密后数据段第y(i)个元素＝值变换后第i个元素，其中i＝1，2，…，m
例如，n＝5，m＝3的数据加密过程如下：
(1)已知m＝3，数组x与数组y中的数据如下表所示。则待加密数据段“155，1，250”加密后的数据段为________(填数据，用逗号分隔)。
x(1)
x(2)
x(3)
10
20
30
y(1)
y(2)
y(3)
3
1
2
(2)小张根据上述加密算法，设计了一个对应的解密程序，其VB代码如下，请在划线处填入合适的代码(解密与加密使用相同的密钥数据)。
Private Sub Command1_Click( )
Const n＝100
Const m＝6
Dim i As Integer，j As Integer
Dim a(1 To n) As Integer，b(1 To n) As Integer
Dim x(1 To m) As Integer，y(1 To m) As Integer
′读取值变换与位置变换的密钥数据，分别保存在数组x与y中，代码略。
′读取待解密数据，保存在数组a中，代码略。
′下面进行位置变换：位置变换后数据保存到数组b中
For i＝1 To ____①____
For j＝1 To m
　　　　____②____
Next j
Next i
For i＝(n m)*m＋1 To n
b(i)＝a(i)
Next i
′下面进行值变换：值变换后数据仍保存到数组b中
j＝1
For i＝1 To n
b(i)＝____③____
j＝j＋1
If j＞m Then j＝1
Next i
′输出解密后数据，代码略。
End Sub
解析　数据构成环是本题考核的其中一个问题。155，1，250值变换后变成165，21，24，位置变换后变成21，24，165。加密时，先进行值变换，再进行位置变换，解密时应先位置变换，再进行值变换。进行位置变换时，变量i表示共有多少整数段，也可以理解为多少行，易知完整的 m 个数据段的个数为n m个．变量j表示每段中每列的位置。当i＝1 时，完成第 1 段数据变换，即 b(j) ＝ a(y(j))，当i＝2 时，完成第 2 段数据变换，即 b( m＋ j) ＝ a( m＋ y(j))，当i＝3 时，完成第 3 段数据变换，即 b( m* 2＋ j) ＝ a( m* 2＋ y(j))，当i＝4 时，完成第 4 段数据变换 ，即 b( m* 3＋ j) ＝ a( m* 3＋ y(j))……归纳得出第 i 段数据变换为 b((i－ 1)*m＋j) ＝ a((i－ 1)*m＋y(j))。在进行值变换时，加密时值的变换方式为b(i)＝(b(i)＋x(j)) Mod 256。推导出解密时b(i)＝b(i)－x(j)，其中b(i)>＝x(j)或b(i)＝b(i)－x(j)＋256，其中b(i)答案　(1)21，24，165
(2)①n m　或Int(n/m)
②b((i－1)*m＋j)＝a((i－1)*m＋y(j))
③(b(i)＋256－x(j))Mod 256
或 (b(i)＋256－x((i－1)Mod m＋1))Mod 256
1．插入排序也是一种排序的方法，在各地的模拟卷是经常出现。其算法的原理可以理解为在整理一幅扑克牌的过程，当摸到两张及以上牌，将牌放在合适位置，实现整幅牌从小到大排列。
2．数据构成环在数据加密、钟表等问题中经常出现。关键是构成环的原理。
考点1　插入排序
一、排序思想
在将第i个数key插入到数据区间[1，i－1]或[i＋1，n]范围内，使得数据区间[1，i]或[i，n]有序。重复执行n－1遍，使得全部数据有序。
该算法包括两个步骤，一是查找key位置，二是把key放在该位置上。
查找key位置的方法是：把a(i)赋值给key，如果从前往后有序，变量j从i－1位置开始，向前查找，a(j)与key比较，直到找到位置或找到最前面(j＝1)。如果从后往前有序，变量j从i＋1位置开始，向后查找，a(j)与key比较，直到找到位置或找到最后面(j＝n)。
二、算法实现
1．理解变量i、j和key的含义
变量i每次要插入数的位置，key表示第i个数的值。j表示查找和比较位置位置。
2．从前往后有序，进行升序排列
从第2个数(i的初值为2)开始，插入到前面有序的数列中。
某数列已经插入3个数，数列为49，60，71，61，54，3，66，以i＝4为例说明插入排序的过程。
查找位置j：区间为[1，3]，从第3个数开始向前查找。
比较对象：先把当前a(i)的值存在变量key中，再用key分别与前面的数a(j)进行比较。
找到位置的条件：比前面的数大，即key≥a(j)。
当key≥a(j)时，key应所处的位置是j＋1。如果没有找到位置，条件是key＜a(j)，把该数向后移动，即把a(j)赋值给a(j＋1)，a(j)＝a(j＋1)。
三、实现的核心代码
四、也可以从后往前进行插入排序
变量i的初值是n－1，一直插入排序，使得第1个数在序。
【例1】 小明对两个班级的90名同学进行编号，随机产生不同号码，对于其中相同的号码，只保留一个，在号码产生过程中，号码始终是从小号到大号排列，直到找到10个同学号码为止。
1)用b数组表示该号码是否产生，b(x)若为0，表示x未产生；
2)先产生第1个号码，从第2个开始，产生数x，先判断b(x)的值，如果为0，再去插入到合适位置；
3)如果x比前面第一个数大，则直接放入a(i)数组元素中，否则利用对分查找法找到相应位置；
4)从该数x应该存放的位置开始的数据向后移动，并把该数x存放起来。单击“产生”按钮Command1，在列表框List1中输出每次产生的号码。
请在划线处填入合适的代码。
Dim a(10) As Integer, b(100) As Integer
Private Sub Command1_Click()
Dim i　As Integer, x As Integer, s As String
a(1) ＝ Int(Rnd() * 90 ＋ 1): b(a(1)) ＝ 1
①____
Do While i <＝ 10
x ＝ Int(Rnd() * 90 ＋ 1)
If b(x) ＝ 0 Then
　　　　If ____②____Then
　　　　　　a(i) ＝ x
　　　　Else
　　　　　　wz ＝ seach(i, x)
　　　　　　For k ＝ i － 1 To wz Step －1
　　　　　　　　a(k ＋ 1) ＝ a(k)
　　　　　　Next k
　　　　　 ____③____
　　　　End If
　　　　b(x) ＝ 1: s ＝ “产生前” ＋ Str(i) ＋“个号码是：”
　　　　　　 For j ＝ 1 To i
　　　　　　　　 s ＝ s ＋ Str(a(j))
　　　　　　Next j
　　　　　　List1.AddItem s
　　　　　　i ＝ i ＋ 1
End If
Loop
End Sub
Function seach(p As Integer, x As Integer) As Integer
Dim m As Integer, j As Integer
m ＝ Int(p / 2)
If______④____ Then
j ＝ m ＋ 1
Do While a(j) < x
　　　　j ＝ j ＋ 1
Loop
Else
If m ＝ 1 Then j ＝ 1 Else j ＝ m － 1
Do While a(j) > x And j >＝ 1
　　　　j ＝ j － 1
Loop
j ＝ j ＋ 1
End If
seach ＝ j
End Function
解析　变量i表示插入的位置，往往从第2个位置开始。B数组是一个标志，若其值为0，表示该下标的数没有出现过。若他比前一个数大，直接放入第i个位置，否则进行查找，并放入合适位置。
答案　①i＝2　②x>a(i－1)　③a(k ＋ 1) ＝x　④a(m)【变式训练1】 在编号为1－100的观众中随机产生10位不同的幸运观众，并将幸运观众的编号升序排列。
请在划线处填入合适的代码。
n ＝ 10: a(1) ＝ Int(Rnd * 100 ＋ 1)
i ＝ 2
Do While i <＝ n
　t ＝ Int(Rnd * 100 ＋ 1)
　For j ＝ 1 To i － 1
If a(j) ＝ t Then Exit For
　Next j
　If ____①____Then
For j ＝ i － 1 To 1 Step －1
If a(j) > t Then a(j ＋ 1) ＝ a(j) Else Exit For
　 Next j
　 ____②____
　 i ＝ i ＋ 1
　End If
Loop
解析　要求产生10位不同的幸运观众，在已经产生的号码中先进行查找，如果没有重复，会找到i的位置。在利用插入排序的思想，把新产生的数放入合适的位置。
答案　①i＝j　②a(j ＋ 1) ＝t
考点2　约瑟夫环问题
约瑟夫环是一个数学的应用问题：已知n个人(以编号1，2，3……n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。在生活中会碰到类似很多问题，如钟表走向、值日的轮值等。
一、以24小时制式计算(0点－23点)，完成如下表格
t的初值
经历时长(n)
结果时间
统一
表达式
t＝3时
13小时后
16时
(t＋n) Mod 24
23小时后
2时
t＝15时
－3小时后
12时
(t＋n＋24)
Mod 24
－18小时后
21时
二、将字母表的字母A替换为E，B替换为F，C替换为G，…，W替换为A，X替换为B，…
对于环的操作一般用Mod运算符进行计算，某个数Mod n的范围是[0，n－1]，其他下标必须从0开始编号。若要实现从1开始编号，需把编号减去1，进行运算后，再加上1。
对于任意字母表中第t个位置的字母加密后的表达式为(t－1＋4)Mod 26＋1。如字母w在字母表中处于第23，代入以上公式，加密后为第1个位置。
字符ch转换的表达式是Chr((Asc(ch)－1＋4)Mod 26 ＋1)。也可以用以下自定义函数来实现大写字母x向后移动y个位置的功能
Function Run(x As String, y As Integer) As String
Dim ans As Integer
ans＝ Asc(x) －65
ans＝(ans＋y) Mod 26
Run ＝ Chr(ans ＋ 65)
End Function
同理，例如对于一个m行乘以n列的矩阵，第i个位置元素所处的列数为(i－1)Mod n＋1。所处行为(i－1)n+1。
【例2】 字符环上的最长公共字符串。将字符串首尾相接后可以得到一个环，如图1和图2分别是由字符串“ABCUVKLM”和“MADJKLUVKL”首尾相接后得到的环。在图1和图2所示的两个环中，最长的公共字符串为“UVKLMA”(图中带背景圆圈表示)。
编写VB程序，实现如下功能：在文本框Text1和Text2中分别输入一个字符串(仅由大写字母构成，每个字符串长度不超过100)，单击命令按钮Command1后，在标签Label3中输出两个字符串构成的环的最长公共字符串长度(字符串在环中必须连续)。程序运行效果如图所示。
实现上述功能的 VB 程序如下，请回答下列问题：
(1)根据题意描述，字符串“BCEFGK”和“GKBLMCKEF”的最长公共字符串长度为________。
(2)请在划线处填入合适的代码。
Function getmin(a As Integer, b As Integer) ′获取两个整数的较小者
If a < b Then getmin ＝ a Else getmin ＝ b
End Function
Private Sub Command1_Click()
Dim s1 As String, s2 As String, i As Integer, j As Integer, x As Integer, y As Integer
Dim cnt As Integer, ans As Integer, len1 As Integer, len2 As Integer
s1 ＝ Text1.Text
s2 ＝ Text2.Text
len1 ＝ Len(s1)
len2 ＝ Len(s2)
minlen ＝ ____①____　′minlen 中保存s1和s2中较短字符串的长度
ans ＝ 0
For i ＝ 1 To len1
For j ＝ 1 To len2
cnt ＝ 0: x ＝ i: y ＝ j
Do While　____②____And cnt < minlen
　　　　 cnt ＝ cnt ＋ 1
　　　　x ＝ x Mod len1 ＋ 1
　　　　y ＝ y Mod len2 ＋ 1
Loop
If　____③____ Then ans ＝ cnt
Next j
Next i
Label3.Caption ＝ Str(ans)
End Sub
解析　用x和y分别记录s1和s2中正在比较的字符的位置，通过对字符串长度求余，巧妙地回到第一个字符的位置，实现了字符环的功能。注意：因为字符串的下标从1开始，故不能写作x＝(x＋1) Mod len1。
答案　(1)5　(2)① getmin(len1, len2)　②Mid(s1，x，1) ＝ Mid(s2，y，1)　③cnt > ans
【变式训练2】 编写VB程序，实现如下功能：在文本框Text1中输入当天对应的星期，文本框Text2中输入天数，单击“推算”按钮Command1，推算出相应天数后的星期情况，并在标签Label1中输出结果。界面如图所示。
(1)为实现上述功能，请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim x As String, xq As String, num As Integer
Dim i As Integer, h As Integer
x ＝ “日一二三四五六”
xq ＝ Text1.Text
i ＝ 1
num ＝ Val(Text2.Text)
For i ＝ 1 To Len(x)
If xq ＝ Mid(x, i, 1) Then h ＝ i: Exit For
Next i　　
_____①____
Label1.Caption ＝ “星期” ＋ Mid(x, r, 1)
End Sub
(2)若当天是“星期五”，在文本框Text2中输入“166”，单击“推算”按钮后，标签Label1中显示的内容是________。
解析　先找出今天在星期中的位置，但构成环，需用0－(n－1)来表示，因此输入五，获得位置6，但用5来表示，加上166＝171，171 Mod 7＝3，表达成字符串还加1，应用星期三。
答案　(1)①r ＝(h＋num－1) Mod 7 ＋ 1 　(2)星期三
一、选择题
1．有如下 VB 程序段：
For i ＝ 4 To 3 Step －1
If a(i) < a(i － 1) Then
　 tmp ＝ a(i)
　For j ＝ i － 1 To 1 Step －1
　　　If tmp > a(j) Then Exit For
　　　a(j ＋ 1) ＝ a(j)
　Next j
　a(j ＋ 1) ＝ tmp
End If
Next i
数组元素 a(1)到 a(6)的值依次为“19，8，96，92，85，88”，经过该程序段“加工”后，数组元素 a(1)到 a(6)的值依次为(　　)
A．8，19，92，96，85，88 B．8，19，85，88，92，96
C．19，8，92，96，85，88 D．19，8，85，92，96，88
解析　变量i从第4个位置开始，如果小于他前面的数，时行插入排序，结果为19，8，92，96，85，88，当i＝3时，条件不满足。
答案　C
2．小张编写程序，实现把数据temp插入到升序序列中，得到一个新的升序序列，原升序序列各元素已依次存放在数组元素a(1)、a(2)、a(3)、……、a(n)中。他编写的VB程序段如下：
If temp >＝ a(n) Then
a(n ＋ 1) ＝ temp
Else
j ＝ n
Do While j >＝ 1 And temp < a(j)
　____①____
　j ＝ j －1
Loop
　 ____②____
End If
要使程序实现上述功能，则方框①②中的语句分别是(　　)
A．①a(j ＋ 1) ＝ a(j)　②a(j ＋ 1) ＝ temp
B．①a(j) ＝ a(j－1)　②a(j ＋ 1) ＝ temp
C．①a(j ＋ 1) ＝ a(j)　②a(j) ＝ temp
D．①a(j) ＝ a(j－1)　②a(j) ＝ temp
解析　如果满足条件temp < a(j)，应该把当前位置的数往后移动，即a(j ＋ 1) ＝ a(j)，当条件不满足时，temp已经大于或等于a(j)，应放入j＋1的位置。
答案　A
3．某VB程序段如下：
s ＝ ”Abc”
i ＝ Len(s)
Do While i >＝ 1
ch ＝ Mid(s, i, 1)
t ＝ (Asc(ch) Mod 32 ＋ 4) Mod 26
s1 ＝ s1 ＋ Chr(t ＋ 65)
i ＝ i － 1
Loop
Text1.Text ＝ s1
该程序段执行后，在文本框Text1中显示的内容是(　　)
A．HGF B．Hgf C．FGH D．Fgh
解析　Asc(ch) Mod 32是取出他在字母表中位置，且位置是从1－26，若要构成环，可以理解为Asc(ch) Mod 32 －1＋ 5) Mod 26，即后移5位。从s的最后一个位置开始进行转换，转换后只有大写字母。
答案　C
二、非选择题
4．对一段字符(仅包含大小写字母和数字)加密，加密规则为：①字母和数字都往后循环顺移 3 位，如“a”变为“d”，“y”变为“b”；“0”变为“3”，“7”变为“0”，②加密后字母在前，数字在后，③字母按逆序排列，数字按顺序排列，如输入明文“a1b7Z8x3”，密文为“aCed4016”。
(1)根据程序代码分析，“加密”按钮的名称是__________。
(2)根据加密规则，明文“9G78fbY5”，则密文为________。
(3)请在划线处填入合适的代码：
Private Sub Com_jm_Click()
Dim x As String, ch As String, c1 As String
Dim s1 As String, s2 As String, s As String
Dim i As Integer, n As Integer, y As Integer
x ＝ Text1.Text
n ＝ Len(x)
For i ＝ 1 To n
　ch ＝ Mid(x, i, 1)
　If ch >＝ ”0” And ch <＝ ”9” Then
　 ____①____
　 s2 ＝ s2 & Str(y)
　ElseIf ch >＝ ”a” And ch <＝ ”z” Then
　 y ＝ (Asc(ch) － Asc(”a”) ＋ 3) Mod 26
　 ____②____
　 s1 ＝ c1 ＋ s1
　Else
　 y ＝ (Asc(ch) － Asc(”A”) ＋ 3) Mod 26
c2 ＝ Chr(Asc(”A”) ＋ y)
s1 ＝ c2 ＋ s1
　End If
Next i
____③____
Text2.Text ＝ s
End Sub
解析　s2连接的是数字串，0－6依次加3后的值为3－9，7－9加3后的值为10－12。将10－12转换成0－2，可以用该数Mod 10的方法。
答案　(1)Com_jm　(2)Beij2018　(3)①y＝(Val(ch)＋3) Mod 10　②c1 ＝ Chr(Asc(”a”) ＋ y)　③s＝s1＋s2
5．小王编写了一个VB程序，该程序的功能是：有15个数形成环状，现要分别找出3个相邻的数，使其相加之和最大或最小。如15个数依次为：18，14，42，61，13，19，14，13，28，52，61，58，30，则相邻三数之和最大为62(30＋18＋14)，相邻三数之和最小为31(4 ＋26＋1)。
程序运行时，先随机生成15个[1，30]区间内的整数，存储在数组a(0)至a(14)中，并在文本框Text1中显示；单击“计算”按钮Command1，则在标签Label4中显示连续三数最大和，在标签Label5 中显示连续三数最小和，程序运行界面如图所示。
实现上述功能的VB程序如下，请在划线处填入合适的代码。
Const n ＝ 14
Dim a(n) As Integer
Private Sub Form Load()
′随机生成15个数，存储在数组元素a(0)～a(14)中，并显示在文本框Text1中
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer
Dim imax As Integer, imin As Integer
Dim smax As Integer, sum As Integer, smin As Integer
smax ＝ 0: smin ＝ 100
For i ＝ 0 To 14
j ＝ ____①____
k ＝ ____②____
sum ＝ a(i) ＋ a(j) ＋ a(k)
If sum > smax Then
smax ＝ sum
imax ＝ i
End If
If sum < smin Then
smin ＝ sum
imin ＝ i
End If
Next i
Label4.Caption ＝ Str(smax)
Label5.Caption ＝ Str(smin)
End Sub
解析　sum是连续三个数之和，当i<＝12时，可以表示为i＋1，i＋2，但当i>12时，i＋1，i＋2的值要超出14，要构成一个环，可以用相加的值Mod 15。若数据存储在a(1)至a(15)，循环应修改为For i＝1 To 15，变量j＝(i－1＋1) Mod 15 ＋1 。
答案　①(i ＋ 1) Mod 15　②(i ＋ 2) Mod 15
6．小李同学碰到了一个数学问题：400个同学按顺序进行编号后围成一个大圈，按1至2报数(从1号位置开始)，报到2的同学出列，以此一直循环报数下去，问最后剩下的那位同学他的编号是几号？
例如以6个同学编号为例，按1至2报数(从1号位置开始)依次出列的编号次序为2－4－6－3－1－5，那么最后剩下的就是编号为5的同学。为了解决这个问题，小李用VB编写了如下程序尝试解决，其中列表List1显示出列的顺序编号，文本框Text1中显示最后留下的编号，程序代码如下：
请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim s, f, t As Integer
Dim a(1 To 400) As Boolean
For i ＝ 1 To 400
a(i) ＝ False
Next i
s ＝ 0：f ＝ 0：i ＝ 0
Do While f < 399
i ＝ i ＋ 1
If i ＝ 401 Then i ＝ ____①____
If a(i) ＝ False Then s ＝ s ＋ 1
If s ＝ 2 Then
　 ____②____
List1.AddItem Str(i)
a(i) ＝ True
f ＝____③____
End If
Loop
For i ＝ 1 To 400
If a(i)＝False　Then Text1.Text＝Str(i)
Next i
End Sub
解析　语句If i ＝ 401 Then i ＝1，很巧妙地构成环的另外一种方法，数组a中存放是否在列的标志，f表示出列人数，s表示1和2报数。
答案　①1　②s＝0　③ f＋1
7．平面上有N(3≤N≤100)个房间围成一圈，按顺时针方向分别编号为1…N，相邻的两个房间之间均有一扇门，第i个房间居住人数为a(i)。初始时选择一个房间，将所有人都聚集在该房间，接着每个人都按顺时针方向走到相邻的房间，直到走到居住的房间。一个人每经过一扇门花费1能量，请确定初始房间，使得所有人花费的能量和最小。例如：N＝5，a(1)＝4，a(2)＝7，a(3)＝8，a(4)＝6，a(5)＝4
最佳方案：初始时所有人聚集在2号房间，花费的能量和：7*0＋8*1＋6*2＋4*3＋4*4＝48。为了解决这个问题，小明编写了一个VB程序。在窗体加载时，从数据库中读取N的值和编号为1到N的房间的居住人数，人数存储在数组a中。点击窗体上的按钮Command1，程序枚举每一种方案(不同的初始房间)，计算该方案的能量和，在文本框Text1中输出最优方案的初始房间编号，在文本框Text2中输出最小能量和。
实现上述功能的VB代码如下，请在划线处填入合适的代码。
Dim a(1 To 100) As Integer　′依次存储编号为1到100的房间的居住人数
Private Sub Form_Load()
′本过程从数据库中读取N 的值和每个房间居住人数，存储在数组a中
′代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, w As Integer, k as Integer
Dim t As Long, ans As Long
k＝0 ：ans ＝ 32767′ans初始化为最大的Integer数据
For i ＝ 1 To n
　t ＝ 0
　For j ＝ 0 To n －1
w ＝ ____①____
If w ＝ 0 Then w ＝ n
t ＝ ____②____
　Next j
　If tNext i
Text1.Text ＝ Str(k)　　 ′起始房间编号
Text2.Text ＝ Str(ans)
End Sub
解析　算法实现从宏观上来讲类似选择排序，但又不是排序，通过这种算法找到能量和最小的那个初始聚集房间。一个人从初始聚集房间起步花费 j 个能量后到达房号为w的房间，那么该房间的几个人所花费的能量即为a(w)*j，当w＝0时，即为n号房间。
答案　①(i＋j) Mod n　②t＋a(w)*j
8．数组a中存储n个2位正整数，从倒数第2个数开始，利用对分查找的思想，找到他所在位置，并插入到位置中，实现整个数组有序。实现该功能的VB程序如下：
Const n ＝ 100
Dim a(n) As Integer
Private Sub Form_Load()
′产生n个2位正整数，并显示在文本框Text1中，代码略
End Sub
Private Sub Command1_Click()
　Dim i As Integer, j As Integer, left As Integer
　Dim right As Integer, m As Integer, t As Integer
　i ＝ n － 1
　Do While i >＝ 1
right ＝ n
t ＝ a(i)
Do While left <＝ right
m ＝ Int((left ＋ right) / 2)
If a(m) ＝ t Then right ＝ m: Exit Do
If a(m) < t Then
　　 　　left ＝ m ＋ 1
Else
　　　 　right ＝ m － 1
End If
Loop
For j ＝ i To right － 1
a(j) ＝ a(j ＋ 1)
Next j
____①____
i ＝ i – 1
s ＝ ”　”
For j ＝ 1 To n
　 s ＝ s ＋ Str(a(j))
Next j
List1.AddItem s
　Loop
End Sub
(1)语句“List1.AddItem s”中的AddItem是________。(单选，填字母：A.对象名/B.属性名/C.事件名/D.方法名)
(2)程序代码中，加框处有错，请改正。
(3)程序代码中，将①处语句补充完整。
(4)若删除语句“If a(m) ＝ t Then right ＝ m: Exit Do”，则下列说法正确的是__________(单选，选填字母：A.程序进入死循环，无法正常运行/B.输出排序的结果不变/C.输出排序的结果将改变)。
解析　本题考核的知识点是对分查找算法及排序算法的综合运用。语句“List1.AddItems”的功能是将变量s加入到列表框List1中，List1称为对象名，在语句中没有出现赋值语句，因此属于方法名。Left和right指查找的开始、结束位置，结束位置是最后，因此开始位置在i的后面1位。对分查找的可能性有两种，找到或没有找到，如果没有找到，最后一次查找时，变量left、right和m是相等的，如果a(m) < t，将移动left到m＋1的位置，该数比a(m)大，但比a(m＋1)小，因此该数在m即right的位置。如果a(m) > t，将移动right到m－1的位置，该数比a(m－1)大，但比a(m)小，因此该数将插入到m－1，即right的位置。综合所述，right就是a(i)要插入的位置，具体操作是，先把[i＋1，right]区间的数向前移一位，再把a(i)即t的值放入right的位置。如果删除If a(m) ＝ t Then right ＝ m: Exit Do，表示该数在后面的区间中找到了，即存在重复的数。没有该条语句，条件a(m) < t不满足，执行right ＝ m － 1，直到right向前移动到比该数小的位置，此时left已经大于right，不再进行查找。因此两次的输出结果是不变的。
答案　(1)D 　(2)left ＝ i ＋ 1　(3)①a(right) ＝ t
(4)B
9．某8位日期加密授权码生成方法描述如下：
①授权码由9位字符组成，前8位为日期的密文，最后1位为验证码；
②日期的最后1位数字k(若k的值为0，令k＝10)，加密成26个大字英语字母表中该位置对应的字母。
③将26个大写英文字母向左移k(日期的最后1位数字)个位置，并将移出的k个字母依次连接到最后。例如当k＝3时，形成如下表所示新的字母排列顺序：
位置
1
2
3
4
……
23
24
25
26
字母
D
E
F
G
……
Z
A
B
C
④日期的第1个数字至第7个数字的加密方法是：计算第i个位置上的数字与第i＋1个位置的数字及位置i三者相加的和，在新的字母表中取出该数字和对应的字母，作为第i个位置上数字加密字符。
⑤计算日期的各个位置上数字之和sum，若和sum的值大于26，在新的英文字母表中，sum Mod 26对应字母转换成小写字母，作为验证码，否则验证码为新的英文字母表中对应字母。
(1)根据上述加密算法，若输入日期为“20000101”，则生成的注册码为________________。
(2)小张根据上述加密算法，设计了一个对应的解密程序，其 VB 代码如下，请在划线处填入合适的代码。
Private Sub Command1_Click()
Dim i As Integer, j As Integer, s As String, k As Integer
Dim mw As String, sum As Integer, t As Integer, t1 As Integer
str1 ＝ ”0123456789”
s ＝ Text1.Text
___①____
t ＝ k: sum ＝ t
s1 ＝ Mid(str1, t ＋ 1, 1)
For i ＝ 7 To 1 Step －1
t1 ＝ Asc(Mid(s, i, 1)) － 64
j ＝ ____②____
t ＝ j － t － i
s1 ＝ Mid(str1, t ＋ 1, 1) ＋ s1
sum ＝ sum ＋ t
Next i
mw ＝ jm(k)
If sum > 26 Then
sum ＝ sum Mod 26
ch ＝ Chr(Asc(Mid(mw, sum, 1)) ＋ 32)
Else
ch ＝ Mid(mw, sum, 1)
End If
If ch ＝ Mid(s, 9, 1) Then　Text2.Text ＝ s1　Else　Text2.Text ＝ ”该系列号未能通过验证！”
End Sub
Function jm(t As Integer) As String
Dim i As Integer, p As Integer
If t ＝ 0 Then t ＝ 10
For i ＝ 1 To 26
p ＝ (t ＋ i － 1) Mod 26
　 　____③____
Next i
End Function
解析　若输入日期为“20000101”，最后一位数字为1，表示字母表向左移动1位，该位数字加密为字母“A”。第1、2个数字及位数之和为3，加密为新字母表第3个位置的字母D，依此类推，完成其他数字加密。由于已知最后一位数字，解密时应从第7位向第1位解密，sum表示各位数字之和，t表示i＋1位置上的数字，其初值为第8位数字k。根据第i个位置上的数字与第i＋1个位置的数字及位置i三者相加的和为j，因此可以计算当前第i个位置的数字。t1表示加密字母在新英文字母表中位置，j表示该字母在A～Z的26个字母表中位置，当t1＝k时，表示该字母向左移动，但还在开始部分，新的位置为t1 － k，综合两种情况表达式为：(t1 － k ＋ 26) Mod 26。
在自定义函数中，字母向左移t个位置后，该字母新的位置距离字母A的距离为p，函数返回相应值。
答案　(1)DCDEGHIAE　(2)①k＝Asc(Mid(s, 8，1))－64或k＝Asc(Mid(s, 8, 1))－Asc(“A”)＋1
②(t1－k＋26)Mod 26　③jm＝jm＋Chr(65＋p)
课件46张PPT。专题九　其他常用算法1．(2019·4月浙江省选考)小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将数组a中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。算法的VB程序段如下，但加框处代码有错，请改正。
′待排序数据存储在数组a中(a(1)～ a(n))，要求升序排列
For i ＝ 1 To (n － 1) 2
　For j ＝ 1 To n － i * 2　t ＝ a(i): j ＝ i － 1
　Do While t < a(j)
a(j ＋ 1) ＝ a(j): j ＝ j － 1
　Loop
　a(j ＋ 1) ＝ t
Next i
解析　插入排序也是经常要考到的问题。先是分别对奇数位和偶数位进行排序，排序后再使偶数位大于前面的元素，最后进行插入排序，只需要对奇数位进行插入排序即可。仅奇数位插入排序，i从1时会导致出现a(0)下标越界，所以i从3开始，即第二空答案为3 To n。
答案　(1)a(j)>a(j＋2) 　(2)3 To n2．(2018·11月浙江选考)某种数据加密方法描述如下(加密前后的数值都是0～255的整数)：
?以m个数据为一段，将n个待加密数据依次分割成若干个数据段。剩余数据(个数小于m)为一个独立数据段。
?数据段加密规则：
数据个数等于m的数据段，先进行值变换，再进行位置变换，得到加密数据段。
数据个数小于m的数据段，只进行值变换，直接得到加密数据段。
?依次合并加密数据段，即为最后的加密数据。(1)已知m＝3，数组x与数组y中的数据如下表所示。则待加密数据段“155，1，250”加密后的数据段为________(填数据，用逗号分隔)。(2)小张根据上述加密算法，设计了一个对应的解密程序，其VB代码如下，请在划线处填入合适的代码(解密与加密使用相同的密钥数据)。Private Sub Command1_Click( )
Const n＝100
Const m＝6
Dim i As Integer，j As Integer
Dim a(1 To n) As Integer，b(1 To n) As Integer
Dim x(1 To m) As Integer，y(1 To m) As Integer′读取值变换与位置变换的密钥数据，分别保存在数组x与y中，代码略。
′读取待解密数据，保存在数组a中，代码略。
′下面进行位置变换：位置变换后数据保存到数组b中
For i＝1 To ____①____
For j＝1 To m
　　　　____②____
Next j
Next i
For i＝(n m)*m＋1 To n
b(i)＝a(i)Next i
′下面进行值变换：值变换后数据仍保存到数组b中
j＝1
For i＝1 To n
b(i)＝____③____
j＝j＋1
If j＞m Then j＝1
Next i
′输出解密后数据，代码略。
End Sub解析　数据构成环是本题考核的其中一个问题。155，1，250值变换后变成165，21，24，位置变换后变成21，24，165。加密时，先进行值变换，再进行位置变换，解密时应先位置变换，再进行值变换。进行位置变换时，变量i表示共有多少整数段，也可以理解为多少行，易知完整的 m 个数据段的个数为n m个．变量j表示每段中每列的位置。当i＝1 时，完成第 1 段数据变换，即 b(j) ＝ a(y(j))，当i＝2 时，完成第 2 段数据变换，即 b( m＋ j) ＝ a( m＋ y(j))，当i＝3 时，完成第 3 段数据变换，即 b( m* 2＋ j) ＝ a( m* 2＋ y(j))，当i＝4 时，完成第 4 段数据变换 ，即 b( m* 3＋ j) ＝ a( m* 3＋ y(j))……归纳得出第 i 段数据变换为 b((i－ 1)*m＋j) ＝ a((i－ 1)*m＋y(j))。在进行值变换时，加密时值的变换方式为b(i)＝(b(i)＋x(j)) Mod 256。推导出解密时b(i)＝b(i)－x(j)，其中b(i)>＝x(j)或b(i)＝b(i)－x(j)＋256，其中b(i)(2)① n m 　或Int(n/m)
②b((i－1)*m＋j)＝a((i－1)*m＋y(j))
③(b(i)＋256－x(j))Mod 256
或 (b(i)＋256－x((i－1)Mod m＋1))Mod 2561．插入排序也是一种排序的方法，在各地的模拟卷是经常出现。其算法的原理可以理解为在整理一幅扑克牌的过程，当摸到两张及以上牌，将牌放在合适位置，实现整幅牌从小到大排列。
2．数据构成环在数据加密、钟表等问题中经常出现。关键是构成环的原理。考点1　插入排序
一、排序思想
在将第i个数key插入到数据区间[1，i－1]或[i＋1，n]范围内，使得数据区间[1，i]或[i，n]有序。重复执行n－1遍，使得全部数据有序。
该算法包括两个步骤，一是查找key位置，二是把key放在该位置上。查找key位置的方法是：把a(i)赋值给key，如果从前往后有序，变量j从i－1位置开始，向前查找，a(j)与key比较，直到找到位置或找到最前面(j＝1)。如果从后往前有序，变量j从i＋1位置开始，向后查找，a(j)与key比较，直到找到位置或找到最后面(j＝n)。二、算法实现
1．理解变量i、j和key的含义
变量i每次要插入数的位置，key表示第i个数的值。j表示查找和比较位置位置。
2．从前往后有序，进行升序排列
从第2个数(i的初值为2)开始，插入到前面有序的数列中。
某数列已经插入3个数，数列为49，60，71，61，54，3，66，以i＝4为例说明插入排序的过程。
查找位置j：区间为[1，3]，从第3个数开始向前查找。比较对象：先把当前a(i)的值存在变量key中，再用key分别与前面的数a(j)进行比较。
找到位置的条件：比前面的数大，即key≥a(j)。
当key≥a(j)时，key应所处的位置是j＋1。如果没有找到位置，条件是key＜a(j)，把该数向后移动，即把a(j)赋值给a(j＋1)，a(j)＝a(j＋1)。三、实现的核心代码四、也可以从后往前进行插入排序变量i的初值是n－1，一直插入排序，使得第1个数在序。
【例1】 小明对两个班级的90名同学进行编号，随机产生不同号码，对于其中相同的号码，只保留一个，在号码产生过程中，号码始终是从小号到大号排列，直到找到10个同学号码为止。1)用b数组表示该号码是否产生，b(x)若为0，表示x未产生；
2)先产生第1个号码，从第2个开始，产生数x，先判断b(x)的值，如果为0，再去插入到合适位置；
3)如果x比前面第一个数大，则直接放入a(i)数组元素中，否则利用对分查找法找到相应位置；
4)从该数x应该存放的位置开始的数据向后移动，并把该数x存放起来。单击“产生”按钮Command1，在列表框List1中输出每次产生的号码。
请在划线处填入合适的代码。Dim a(10) As Integer, b(100) As Integer
Private Sub Command1_Click()
Dim i　As Integer, x As Integer, s As String
a(1) ＝ Int(Rnd() * 90 ＋ 1): b(a(1)) ＝ 1
____①____
Do While i <＝ 10
x ＝ Int(Rnd() * 90 ＋ 1)
If b(x) ＝ 0 Then
　　　　If ____②____Then
　　　　　　a(i) ＝ x　　　　Else
　　　　　　wz ＝ seach(i, x)
　　　　　　For k ＝ i － 1 To wz Step －1
　　　　　　　　a(k ＋ 1) ＝ a(k)
　　　　　　Next k
　　　　　 ____③____
　　　　End If
　　　　b(x) ＝ 1: s ＝ “产生前” ＋ Str(i) ＋ “个号码是：”
　　　　　　 For j ＝ 1 To i
　　　　　　　　 s ＝ s ＋ Str(a(j))　　　　　　Next j
　　　　　　List1.AddItem s
　　　　　　i ＝ i ＋ 1
End If
Loop
End Sub Function seach(p As Integer, x As Integer) As Integer
Dim m As Integer, j As Integer
m ＝ Int(p / 2)
If______④____ Then
j ＝ m ＋ 1
Do While a(j) < x
　　　　j ＝ j ＋ 1
Loop
ElseIf m ＝ 1 Then j ＝ 1 Else j ＝ m － 1
Do While a(j) > x And j >＝ 1
　　　　j ＝ j － 1
Loop
j ＝ j ＋ 1
End If
seach ＝ j
End Function解析　变量i表示插入的位置，往往从第2个位置开始。B数组是一个标志，若其值为0，表示该下标的数没有出现过。若他比前一个数大，直接放入第i个位置，否则进行查找，并放入合适位置。
答案　①i＝2　②x>a(i－1)　③a(k ＋ 1) ＝x　④a(m)n ＝ 10: a(1) ＝ Int(Rnd * 100 ＋ 1)
i ＝ 2
Do While i <＝ n
　t ＝ Int(Rnd * 100 ＋ 1)
　For j ＝ 1 To i － 1
If a(j) ＝ t Then Exit For
　Next j　If ____①____Then
For j ＝ i － 1 To 1 Step －1
If a(j) > t Then a(j ＋ 1) ＝ a(j) Else Exit For
　 Next j
　 ____②____
　 i ＝ i ＋ 1
　End If
Loop解析　要求产生10位不同的幸运观众，在已经产生的号码中先进行查找，如果没有重复，会找到i的位置。在利用插入排序的思想，把新产生的数放入合适的位置。
答案　①i＝j　②a(j ＋ 1) ＝t考点2　约瑟夫环问题约瑟夫环是一个数学的应用问题：已知n个人(以编号1，2，3……n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。在生活中会碰到类似很多问题，如钟表走向、值日的轮值等。一、以24小时制式计算(0点－23点)，完成如下表格二、将字母表的字母A替换为E，B替换为F，C替换为G，…，W替换为A，X替换为B，…对于环的操作一般用Mod运算符进行计算，某个数Mod n的范围是[0，n－1]，其他下标必须从0开始编号。若要实现从1开始编号，需把编号减去1，进行运算后，再加上1。对于任意字母表中第t个位置的字母加密后的表达式为(t－1＋4)Mod 26＋1。如字母w在字母表中处于第23，代入以上公式，加密后为第1个位置。
字符ch转换的表达式是Chr((Asc(ch)－1＋4)Mod 26 ＋1)。也可以用以下自定义函数来实现大写字母x向后移动y个位置的功能
Function Run(x As String, y As Integer) As String
Dim ans As Integer
ans＝ Asc(x) －65
ans＝(ans＋y) Mod 26
Run ＝ Chr(ans ＋ 65)
End Function 同理，例如对于一个m行乘以n列的矩阵，第i个位置元素所处的列数为(i－1)Mod n＋1。所处行为(i－1)n+1。
【例2】 字符环上的最长公共字符串。将字符串首尾相接后可以得到一个环，如图1和图2分别是由字符串“ABCUVKLM”和“MADJKLUVKL”首尾相接后得到的环。在图1和图2所示的两个环中，最长的公共字符串为“UVKLMA”(图中带背景圆圈表示)。编写VB程序，实现如下功能：在文本框Text1和Text2中分别输入一个字符串(仅由大写字母构成，每个字符串长度不超过100)，单击命令按钮Command1后，在标签Label3中输出两个字符串构成的环的最长公共字符串长度(字符串在环中必须连续)。程序运行效果如图所示。实现上述功能的 VB 程序如下，请回答下列问题：
(1)根据题意描述，字符串“BCEFGK”和“GKBLMCKEF”的最长公共字符串长度为________。
(2)请在划线处填入合适的代码。
Function getmin(a As Integer, b As Integer) ′获取两个整数的较小者
If a < b Then getmin ＝ a Else getmin ＝ b
End FunctionPrivate Sub Command1_Click()
Dim s1 As String, s2 As String, i As Integer, j As Integer, x As Integer, y As Integer
Dim cnt As Integer, ans As Integer, len1 As Integer, len2 As Integer
s1 ＝ Text1.Text
s2 ＝ Text2.Text
len1 ＝ Len(s1)
len2 ＝ Len(s2)minlen ＝ ____①____　′minlen 中保存s1和s2中较短字符串的长度
ans ＝ 0
For i ＝ 1 To len1
For j ＝ 1 To len2
cnt ＝ 0: x ＝ i: y ＝ j
Do While　____②____And cnt < minlen
　　　　 cnt ＝ cnt ＋ 1
　　　　x ＝ x Mod len1 ＋ 1
　　　　y ＝ y Mod len2 ＋ 1
LoopIf　____③____ Then ans ＝ cnt
Next j
Next i
Label3.Caption ＝ Str(ans)
End Sub解析　用x和y分别记录s1和s2中正在比较的字符的位置，通过对字符串长度求余，巧妙地回到第一个字符的位置，实现了字符环的功能。注意：因为字符串的下标从1开始，故不能写作x＝(x＋1) Mod len1。
答案　(1)5　(2)① getmin(len1, len2)　②Mid(s1，x，1) ＝ Mid(s2，y，1)　③cnt > ans【变式训练2】 编写VB程序，实现如下功能：在文本框Text1中输入当天对应的星期，文本框Text2中输入天数，单击“推算”按钮Command1，推算出相应天数后的星期情况，并在标签Label1中输出结果。界面如图所示。(1)为实现上述功能，请在划线处填入合适的代码。
Private Sub Command1_Click()Dim x As String, xq As String, num As Integer
Dim i As Integer, h As Integer
x ＝ “日一二三四五六”
xq ＝ Text1.Text
i ＝ 1
num ＝ Val(Text2.Text)For i ＝ 1 To Len(x)
If xq ＝ Mid(x, i, 1) Then h ＝ i: Exit For
Next i　　
_____①____
Label1.Caption ＝ “星期” ＋ Mid(x, r, 1)
End Sub
(2)若当天是“星期五”，在文本框Text2中输入“166”，单击“推算”按钮后，标签Label1中显示的内容是________。解析　先找出今天在星期中的位置，但构成环，需用0－(n－1)来表示，因此输入五，获得位置6，但用5来表示，加上166＝171，171 Mod 7＝3，表达成字符串还加1，应用星期三。
答案　(1)①r ＝(h＋num－1) Mod 7 ＋ 1 　(2)星期三

展开更多......

收起↑