第8节 数组问题
模拟演练
1.有以下VB程序段:
a(1)=68: a(2)=88: a(3)=76: a(4)=60: a(5)=98: a(6)=100: a(7)=64: a(8)=85: a(9)=99:a(10)=59
For i = 1 To 9
b(i) = Abs(a(i + 1) - a(i))
c(b(i) 10) = c(b(i) 10) + 1
Next i
For i = 0 To 10
If c(i) > 0 Then Label1.Caption = Label1.Caption + “” + Str(c(i))
Next i
数组c各元素初值为0,执行该程序段,标签Label1上显示的内容是( )
A.23211 B.13221 C.23221 D.13
答案 B 本程序主要由两个For循环组成,第一个循环里完成的任务为给b(i)赋值,它的值为a(i+1)与a(i)之差的绝对值,给c数组做累加用,例如b(1)的值是20,那么c(2)的值加1,由于b(1)到b(9)的值分别为20,12,16,38,2,36,21,14,40,则c数组的2,1,1,3,0,3,2,1,4这些位置的值在循环中依次被加1,可知c(0)=1,c(1)=3,c(2)=2,c(3)=2,c(4)=1。第二个循环把c数组中,大于0的值依次输出在label1,所以输出13221,所以答案选B。
2.有VB编写的程序如下:
Dim a(0 To 9) As Integer, t as Long
t=Val(Text1.Text)
Do While t<>0
a(t Mod 10) = 1
t = t 10
Loop
For i = 0 To 9
x = x + a(i)
Next i
Text1中输入10242048,则程序执行后x的值为( )
A.1 B.2 C.5 D.10
答案 C 本题先执行一个Do While循环,然后执行一个For循环,Do While循环的作用是把t从个位开始逐个取出来,作为数组a的位置,并且令这个位置的值为1,例如个位数是8,则a(8)=1,这里注意到如果这个位置出现多次,那么数组a中这个位置的值还是1,例如2出现了两次,那么a(2)=1被执行了两次。For循环就是把数组a中的值加起来存储到x,由于数组a中只有0,1,2,4,8这几个位置的值是1,所以x=5,所以答案选C。
3.某VB程序段如下:
For i = 1 To 5
b(a(i)) = b(a(i)) + 1
Next i
pa = 0
For j = 1 To 10
For k = 1 To b(j)
pa= pa + 1 : a(pa) = j
Next k
Next j
a(1)到a(5)的初值依次是7、5、9、4、3,程序段运行后,数组a值依次是( )
A.7, 9, 5,4, 3 B.3, 4, 5, 7, 9
C.4,5,7,9, 3 D.9, 7, 5, 4, 3
答案 B 由于数组a初始值是7、5、9、4、3,因此第一个For循环后,数组b中b(3)、b(4)、b(5)、b(7)、b(9)的值分别1,那么接下来的双重For循环里,只在j等于3、4、5、7、9的时候内部的For k=1 to b(j)循环里的语句才会执行,例如循环到j=3时,由于b(3)=1,for k=1 to b(3)循环里的语句就会执行一遍,pa变成了1,那么a(1)=3,当循环到j=5的时候,pa就变成了2,a(2)=5,依次类推,每次pa加1,并且a(pa)=j,相当于给数组a的1到5的位置重新赋值,巧妙地实现了排序的功能,所以答案选B。
4.有如下VB程序段:
n = Len(Text1.Text)
For i = 1 To n
a(i) = Mid(Text1.Text, i, 1)
Next i
Do While n > 1
If Asc(a(n)) >= Asc(a(n - 1)) Then
m = 1
Else
m = 2
End If
b(m) = b(m) + 1
n = n-1
Loop
数组b各元素的初始值都为0,文本框Text1的内容为“2018Python”。执行程序后,变量b(1)的值为( )
A.10 B.6 C.5 D.4
答案 C 本题中先用数组a把输入的字符串分开来逐个存储,然后用Do While循环从后向前,逐个两两比较,如果后面的字符ASCII编码大于等于前面一个字符的编码,那么m=1,否则m=2,并且每次比较后都执行一遍b(m)=b(m)+1,即b(1)统计出了后面字符比前1个字符编码大于等于的次数,b(2)统计出了后面字符比前1个字符编码小的次数。这里要注意A~Z的编码位65~90,a~z的编码是97~122,0~9的编码是48~57,根据输入的字符串“2018Python”,可知从后面开始往前逐个两两比较,后面字符编码大于等于前1个字符编码的次数是5,所以答案选C。
5.小吴编写了一个查找数组中不重复数据的VB程序,功能如下:程序运行时在列表框List1中显示原始数据(存储在数组a中),单击“查找”按钮Command1后,在列表框List1中显示数组中元素值只出现一次的数据。程序运行界面如图所示。
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Const n = 10 ’数组元素的总数
Dim a(1 To n) As Integer
Private Sub Form_Load()
’该过程对数组a进行赋值,并在列表框List1中显示,代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer,flag(1 To n) As Boolean
’ flag(i)记录第 i 个元素是否重复出现
For i = 1 To n ’flag(i)=true开始假设都只出现1次
flag(i) = True
Next i
For i = 1 To n
If flag(i) Then
For j = i + 1 To n
Ifa(i) = a(i+1) Then flag(i) = False: flag(j) = False ’①
Next j
End If
Next i
For i = 1 To n
Ifflag Then List2.AddItem Str(a(i)) ’②
Next i
End Sub
答案 ①a(i) =a(j) ②flag(i) 或 flag(i)=True
解析 本程序用数组flag记录数组a的每个位置的值是否只出现一次。利用双重循环对数组a中的每个位置的值进行统计,对每个a(i)只要用循环去找一遍i位置后面(用j表示i后面的位置)是不是有跟a(i)相同的值,如果有,则令flag(i)为false,并且flag(j)为false,说明这两个位置的值重复出现过。①根据程序的意思,第1个改错的地方应该是把a(i)跟它后面位置的值都进行比较,所以答案是a(i)=a(j)。②第2个位置所在的For循环为了输出没有重复出现的数据,所以这里要对每个i位置的flag(i)进行判断,答案是flag(i)=true或者flag(i)。
6.某游戏规则如下:将2*n位队员按2人一组分成n个队(n<10),地面上有一排格子,共2*n个,每个格子都对应一个小于10的随机正整数。游戏开始后,所有队员都选择站到一个空的格子里,等他们站满格子后,开始为每位队员进行记分。记分规则:每组甲乙两个队员,甲队员的分数是从自己所站的格子开始,按照格子序号递减,将这些格子中的数字一直累加到第1个格子。乙队员的分数是从自己所站的格子开始,按照格子序号递增,一直将格子中的数字累加到第2*n个格子。如果同一队的两名队员得到的分数相同,则该组参赛队获胜。
例如:如图所示,有4个队8位队员,地上一排格子的数字依次为2、1、1、7、9、2、5、6。若某队甲队员站在第4个格子,则其分数为2+1+1+7=11;乙队员站在第7个格子,则其分数为5+6=11。两者相等,则该队获胜。
gz(1)
gz(2)
gz(3)
gz(4)
gz(5)
gz(6)
gz(7)
gz(8)
2
1
1
7
9
2
5
6
甲 乙
(1)假设有3队队员,地上一排格子的数字依次为6、7、3、4、3、9。若某队甲队员站在第3个格子上,那么该队乙队员站在第 个格子上才能获胜。?
(2)实现上述功能的VB程序如下。请在划线处填入合适代码。
Dim n As Integer
Dim gz(1 To 20) As Integer
Private Sub Command1_Click()
Dim dfa As Integer, dfb As Integer
Dim ta As Integer, tb As Integer
① ?
Randomize
For i = 1 To 2 * n
gz(i) = Int(Rnd* 9 + 1)
List1.AddItem “gz(“ & i & ”)” & gz(i)
Next i
num = 1
For j = 1 To 2 * n
ta = j
dfa = zwdf(ta, True)
For k = 1 To 2 * n
tb = k
② ?
If dfa = dfb Then
List2.AddItem num & “甲队员(“ & j &”)得分=” & dfa & “乙队员(“ & k & ”)得分=” & dfb
num = num + 1
End If
Next k
Next j
List2.AddItem “获胜的站法共有:”+ ③ + “种”?
End Sub
Function zwdf(p As Integer, r As Boolean) As Integer
Dim fs As Integer
If r = True Then
④ ?
fs = fs + gz(i)
Next i
Else
For i = p To 2 * n
fs = fs + gz (i)
Next i
End If
zwdf = fs
End Function
答案 (1)4 (2)①n=Val(Text1.Text) ②dfb=zwdf(tb, False) 或 dfb=zwdf(k,False) ③Str(num-1) ④For i = p To 1 Step -1 或 For i = 1 To p
解析 (1)甲站在第3格上,往左累加,结果是16。从最后一格往左累加,能得到16的是第4格。
(2)① 结合窗体,通读程序,发现缺少输入语句,故填n=Val(Text1.Text)。② 需要结合理解自定义函数zwdf来填,zwdf有2个参数,第一个表示位置,第二个表示方向(True表示向左累加,False表示向右累加),由此,可先填第④空:For i=p To 1 Step-1或者For i=1 To p。回到主程序,第②空的下一个If语句的条件为dfa=dfb,dfa已在外层循环中赋值,其含义是从ta开始往左累加,则dfb应该为从tb开始往右累加,故填dfb=zwdf(tb,False)。③ 用于输出所有能获胜的站法总数num,但要注意num的初值为1,故输出时应该为Str(num-1)。
7.问题描述:有n个互不重复的数字,值的范围是[1,n],分别保存在数组元素a(1)到a(n)中,若数字i保存在a(i),则认为数字i在正确的位置上。若干个相互占用了位置的数字称为一组,一个在正确位置上的数字单独为一组,比如6个数字2,3,1,4,6,5分别保存在数组元素a(l)到a(6)中,则2、3、1为一组,4为一组,6、5为一组。该程序的功能为输出每组的情况。运行界面如图:
(1)数组元素a(l)到a(5)的值分别为2、5、3、1、4,这5个元素总共有 组。?
(2)请补充代码。
Const n = 10
Dim a(1 To n) As Integer ’保存原始数据
Dim b(1 To n) As Boolean ’数组b用来标记相应的位置有没有找过
Private Sub Command1_Click()
Dim i As Integer, sum As Integer, total As Integer
sum = 0: total = 1 ’total表示第几组
i = 1
List2.AddItem“第” + Str (total) + “组”
Do While sum < n
Do While Not b(i)
List2.AddItem a(i)
b(i) = True
① ?
sum = sum + 1
Loop
If sum < n Then
② ?
List2.AddItem “第”+ Str(total)+“组”
i = 1
Do While b(i) ’该循环用来查找下一组的开始位置
i = i+ 1
Loop
End If
Loop
End Sub
Private Sub Form_Load()
Dim i As Integer
Randomize
For i = 1 To n ’产生n个不一样的整数,范围为[1,n]
a(i) = Int(Rnd * n)+1
Do While ③ ?
a(i)= Int(Rnd * n) + 1
Loop
Next i
For i = 1 To n
List1.AddItem a(i)
b(i) = False
Next i
End Sub
Function f(x As Integer, y As Integer) As Boolean
’该函数的功能:判断x和数组a中前y个数有没有重复
Dim j As Integer
f = False
For j = 1 To y
If a(j) = x Then f = True:Exit For
Next j
End Function
答案 (1)2 (2)①i=a(i) ②total=total+1 ③f(a(i),i-1) 或 f(a(i),i-1)=True
解析 (1)第 1 组: 2,5,4,1;第 2 组: 3。
(2)当程序的逻辑结构复杂,函数较多时,我们最好按照程序的运行顺序去阅读代码,在本题中,我们可以先阅读Form_Load()和Function f(),生成原始数据后,再去阅读Command1_Click(),才能理顺程序的逻辑结构。生成原始数据时,要求产生n个不一样的整数存储在数组a中,所以每生成一个随机整数a(i),需要先判断它是否和数组a前(i-1)个元素重复,只有不重复,才能存储到数组a中。如何理解“相互占用了位置的数字”呢?当处理数组a的第i个元素时,若a(i)=j,表示数字j占用了位置i,则a(i)和a(j)是同一组元素,我们接下来去处理第j个元素,即令i=a(i)。就这样从一个元素“跳”到同一组的下一个元素,直到跳回该组的第一个元素,由于该组的第一个元素对应的b(i)=True,退出循环。以第1题提供的数据为例:数组元素a(1)到a(5)的值分别为2、5、3、1、4。刚开始i=1,a(1)=2,则执行i=2,a(2)=5,则执行i=5,a(5)=4,则执行i=4,a(4)=1,则执行i=1,因为b(1)=true,退出循环,由此得到第1组元素,输出顺序为2,5,4,1。上述循环结束后sum=4,满足sum8.有N堆纸牌,编号分别为①,②,…。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。
移牌规则:在编号为①的堆上取的纸牌,只能移到编号为②的堆上;在编号为N(N≥2)的堆上取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。
例如N=4,4堆纸牌数分别为:
①
②
③
④
9
8
17
6
移动3次可达到目的:从③取4张牌放到④(9 8 13 10)→从③取3张牌放到②(9 11 10 10)→从②取1张牌放到①(10 10 10 10)。
现编写如下代码解决4堆任意张数牌的移动问题,请按提示补充划线句的代码:
Private Sub Command1_Click()
Dim aver As Single
Dim st As Integer ’统计移动的步数
Dim ssum,i, j As Integer
Dim a( 1 To 100) As Integer
a(1) = Val(Text1.Text) ’读取各堆牌张数,求总张数aver
a(2) = Val(Text2.Text)
a(3) = Val(Text3.Text)
a(4) = Val(Text4.Text)
ssum =a(1) + a(2) + a(3) + a(4)
aver=ssum 4 ’求牌的平均张数aver
For i=1 To 4
① ?
Next i
i=1 ’过滤初端和末端的0
j = 4
Do While a(i) = 0 And i < 4
i=i+1
Loop
Do While a(j) = 0 And j > 1
j = j-1
Loop
st = 0
Do While i < j ’开始移动牌使数组a元素值均为0并过滤掉
② ?
a(i) = 0
st = st + 1
i=i+1
Do While a(i) = 0 And i ③ ?
Loop
Loop
Print st ’输出移动次数
End Sub
(1)划线①处 。?
(2)划线②处 。?
(3)划线③处 。?
(4)若现有6堆牌,分别编号①②③④⑤⑥,各堆张数分别为15、2、4、7、8、6,按上述算法的思路,要使用最少的移动次数使每堆上纸牌数都一样多,则最少次数为 。?
答案 (1)a(i) =a(i)–aver
(2)a(i + 1) = a(i + 1) + a(i)
(3)i = i + 1 (4)3
解析 如果能想到把每堆牌的张数减去平均张数,题目就变成移动正数,加到负数中,使大家都变成0,那就意味着成功了一半!拿本题来说,平均张数为10,每堆牌的张数减去平均张数,原张数9,8,17,6变为-1,-2,7,-4,其中没有为0的数,我们从左边出发:要使第1堆的牌数-1变为0,只需将-1张牌移到它的右边(第2堆)-2中,结果是-1变为0,-2变为-3,各堆牌张数变为0,-3,7,-4;同理,要使第2堆变为0,只需将-3张牌移到它的右边(第3堆)中去,各堆牌张数变为0,0,4,-4;要使第3堆变为0,只需将第3堆中的4张牌移到它的右边(第4堆)中去,结果为0,0,0,0,完成任务。每移动1次牌,步数加1。其中出现的负数张牌的移动并不违反题意,其实从第i堆移动-m张牌到第(i+1)堆,等价于从第(i+1)堆移动m张牌到第i堆,步数是一样的。如果张数中本来就有为0的怎么办呢?如0,-1,-5,6,还是从左算起(从右算起也完全一样),第1堆是0,无需移牌,余下与上相同;再比如-1,-2,3,10,-4,-6,从左算起,第1次移动的结果为0,-3,3,10,-4,-6;第2次移动的结果为0,0,0,10,-4,-6,现在第3堆已经变为0了,可节省1步,余下继续。
课件11张PPT。
第8节 数组问题 排序算法及其变形、查找算法等相对复杂的问题,本质上是基于数组的 应用。
1.求数组中的最小值、最大值。
k=a(1)
For i=2 to n If a(i)Next
代码运行完后,k中存储的是数组a中的最小值;将a(i)k,则k中 是最大值。2.求数组中最小值(最大值)所在的位置。
k=1
For i=2 to n
If a(i)Next3.判断一个10位数n中数字刚好是0123456789的不同组合,不重复,不缺 失(即每个数字均只出现一次)。
Dim a(0 To 9) As Integer
Do While n > 0
a(n Mod 10) = 1
n = n 10
Loop
s = 0For i = 0 To 9
s = s + a(i)
Next
If s = 10 Then Print “yes”4.统计字符串s中出现次数最多的小写字母。
Dim a(1 To 26) As Integer
For i = 1 To Len(s)
c = Mid(s, i, 1)
If c >= “a” And c <= “z” Then n = Asc(c) - Asc(“a”) + 1
a(n) = a(n) + 1
End IfNext
Max = 1
For i = 2 To 26
If a(i) > a(Max) Then Max = i
Next
Print Chr(Asc(“a”) + Max - 1)5.产生10个1至100的不重复的数(利用数组做标记)。
Dim f(1 To 100) As Boolean
For i = 1 To 10
a(i) = Int(Rnd * 100) + 1
Do While f(a(i)) = True
a(i) = Int(Rnd * 100) + 1
Loop
f(a(i)) = TrueNext
利用数组f做标记,如果数值i已经产生,则f(i)=true。6.产生10个1至100的不重复的数(通过查找的方法)。
For i = 1 To 10
a(i) = Int(Rnd * 100) + 1
For j = 1 To i - 1
If a(j) = a(i) Then i = i - 1: Exit For
Next
Next 利用顺序查找,查找第i次产生的随机数是否与前i-1个数有相同,如果有相同,则重新产生,此处i=i-1是一个巧妙的运用。7.产生10个1至100不重复的数(利用自定义函数)。
Dim a(1 To 10) As Integer
Private Sub Command1_Click()
Dim i As Integer
For i = 1 To 10
a(i) = Int(Rnd * 100) + 1
Do While f(i) a(i) = Int(Rnd * 100) + 1 Loop
Next
End Sub
Public Function f(n As Integer) As Boolean
f = False
For i = 1 To n - 1
If a(i) = a(n) Then f = True: Exit For
NextEnd Function
自定义函数f的作用是判断第n个数是否已经产生,在函数中利用顺序查 找第n个数是否与前n-1个数有相同,如果相同则返回函数值true。因为 有两个过程要使用数组,因此数组定义为通用变量。8.在数组a的第i个位置插入一个数key,并让第i至第n个数依次往后移。
For j = n + 1 To i + 1 Step -1
a(j) = a(j - 1)
Next
a(i)=key
