2020版高考信息技术二轮浙江专用 专题九 其他常用算法课件(46张幻灯片)+学案

文档属性

名称 2020版高考信息技术二轮浙江专用 专题九 其他常用算法课件(46张幻灯片)+学案
格式 zip
文件大小 3.2MB
资源类型 教案
版本资源
科目 信息技术(信息科技)
更新时间 2019-11-30 14:30:50

文档简介

专题九 其他常用算法
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)星期三
同课章节目录