其他典型算法之矩阵应用
【例1】 把矩阵A的行和列互相交换所产生的矩阵称为A的转置矩阵,这一过程称为矩阵的转置,如 。以下VB6程序实现矩阵的转置,请在划线处填入正确的语句实现功能。
Const m = 4
Const n = 5
Dim a(1 To m * n) As Integer
Dim b(1 To m * n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer
List1.Clear
List2.Clear
Randomize
For i = 1 To m * n '生成源矩阵
a(i) = Int(Rnd() * 89 + 10)
Next
For i = 1 To m '显示源矩阵
s = ″ ″
For j = 1 To n
s =①
Next
List1.AddItem s
Next
For i = 1 To n '生成并显示转置矩阵
s = ″″
For j = 1 To m
b((i - 1) * m + j) =②
s = s + Str(b((i - 1) * m + j))
Next
List2.AddItem s
Next
End Sub
答案:①s+Str(a((i-1)*n+j)) ②a((j-1)*n+i)
解析:本程序用一维数组a保存矩阵数据Amn。转置后的矩阵为Anm,对于矩阵中的元素aij,对应一维数组元素为a((i-1)*n+j),转置后对应的元素是aji,对应一维数组元素为a((j-1)*m+i)。因此,①处应填入的语句是s + Str(a((i - 1) * n + j)),②处应填入的语句是a((j - 1) * n + i)。
【例2】.(2017·11浙江选考)由数组a生成数组b的方法描述如下:
(1)将数组a中的n个元素依次分割出若干个数据块,每个数据块有m×m个元素,m最大值为8,最小值为2。分割时,按尽可能大的数据块进行分割。
(2)对每个分割出的数据块用“方阵转换法”进行转换,每次转换后得到的数据块依次存储在数据b中。
(3)数组a分割后的剩余元素(个数小于4),直接依序存储到数组b中。
例如n=140时,可依次分割出3个数据块,元素的个数分别为64(8×8)、64(8×8)、9(3×3),剩余元素为3个。
“方阵转换法”过程如下:将数据块中m×m个元素按行序排列成一个数字方阵,从该数字方阵中按列序得到转换后元素的次序。以3×3数据块为例,转换过程如下图所示:
小明依据上述描述设计了如下VB程序。请回答下列问题:
(1)当n=120时,分割出的第3个数据块元素个数为 。
(2)请在划线处填入合适的代码。
Const n = 120
Dim a(1 To n) As Integer
Dim b(1 To n) As Integer
Private Sub Command1_Click()
Dim m As Integer, i As Integer
Dim Start As Integer '当前未分割数据的第1个元素下标
Dim Left As Integer '当前未分割数据的个数
Dim pa As Integer '数组a的下标
Dim pb As Integer '数组b的下标
'读取n个转换前的数据,依次存储到a(1)、a(2)、…、a(n)中,代码略
m = 8
Start = 1
Left = n
Do While Left > 3
If Left < m * m Then
m =①
Else
pa = Start
pb = Start
For i = 1 To m * m
b(pb) = a(pa)
pb = pb + 1
If i Mod m = 0 Then
②
Else
pa = pa + m
End If
Next i
③
Start = Start + m * m
End If
Loop
For i = Start To n
b(i) = a(i)
Next i
'依次输出转换后数据b(1)、b(2)、…、b(n)中,代码略
End Sub
答案: (1)4 (2)①m-1或int[sqr(left)] ② pa=pa-m* (m-1)+1或pa=Start+i\m ③left=left-m* m
解析: (1)n=120时,可依次分割出 3 个数据块,元素的个数分别为 64(8×8)、49(7×7)、4(2×2),剩余元素为 3 个。所以第 3 个数据块为 4 个元素。
(2)①剩余数量 Left < m * m,意味着当前剩余数量不够分割成m×m。下一次尝试 m-1 方块。例如Left=50,m=8,不够分割成 8×8,下依次尝试 7×7。
②当 m=3 时为例:
当 i=1 时,执行 b(1)=a(1),计算 a 的下一次下标 pa=4;
当 i=2 时,执行 b(2)=a(4),计算 a 的下一次下标 pa=7;
当 i=3 时,执行 b(3)=a(7),计算 a 的下一次下标 pa=2;
当 i=4 时,执行 b(4)=a(2),计算 a 的下一次下标 pa=5;
……
通过变量i,找出变量i和下一次数组a下标之间的关系。通过观察发现每一段pa的值公差都为3,只需要计算出每一段的首项,该段后面的依次pa+3即可。分析得出,每一段首项下标 pa=i\3+1,后面的依次为 pa=pa+3。推广到n个数据,m×m 方阵中。每一段首项下标pa=i\m+start,后面的依次为 pa=pa+m。
③执行Else部分,意味着m×m分割成功。分割之后剩余数量为left减去m*m。例如Left=50,m=7,7×7分割后,剩余50-7*7=1个。
课后作业
1.某程序功能如下:数组a中存放了n n个10到99之间的随机整数,按n行n列的形式在列表框List1中显示(即第一行依次显示a(1)~a(n),第二行依次显示a(n+1)~a(2 n),依次类推)。在文本框Text1中输入某矩形区域的左上角位置(x1,y1)(注:x1表示列号,y1表示行号),在文本框Text2中输入右下角位置(x2,y2),单击“垂直翻转”按钮Command1,对以(x1,y1)和(x2,y2)为对角顶点的矩形区域中的数据进行垂直翻转,并在列表框List2中显示。程序运行界面如图所示。
(1)依据上述描述设计如下VB程序。请在划线处填入合适的代码。
Const n=5
Dim a(1 To n^2) As Integer,b(1 To n^2) As Integer
Private Sub Form_Load()
'产生n n个10到99之间的随机整数存数组a,并在List1中显示。代码略。
End Sub
Private Sub Command1_Click()
Dim i As Integer,j As Integer,value As String,c As String,xy(1 To 4) As Integer
s=Text1.Text+″,″+Text2.Text
value=″ ″:j=0
For i=1 To Len(s)
c=Mid(s,i,1)
If c>=″0″ And c<=″9″ Then
value=value+c
Else
①
xy(j)=Val(value):value=″ ″
End If
Next i
xy(4)=Val(value)
For i=1 To n
For j=1 To n
If j>=xy(1) And j<=xy(3) And i>=xy(2) And i<=xy(4) Then
b((i-1) n+j)= ②
Else
b((i-1) n+j)=a((i-1) n+j)
End If
Next j
Next i
List2.Clear:c=″ ″
For i=1 To n n
c=c+Str(b(i))
if ③ then
List2.AddItem c
c=″ ″
end if
Next i
End Sub
(2)对于有10 10个元素构成的数组a,如果输入左上角位置是(2,3),右下角位置是(6,7),垂直翻转后,则元素a(23)在新数组中的位置是 。
答案 (1)①j=j+1 ②a((xy(2)+xy(4)-i-1)*n+j) ③i mod n=0 (2)63
解析 ①处循环是要把存放在s中的4个位置数据分离出来,依次存入数组元素xy(1)、xy(2)、xy(3)、xy(4)中。具体方法是每次从s中取一字符c,如果是数字,存入value,如果不是,表明已得到一个完整位置,所以①处填j=j+1,然后把value存入xy(j),value清空,为提取下一个位置准备。
②处双重循环完成垂直翻转功能。其中数组a存放变换前矩阵数据,数组b存放变换后矩阵数据,变量i代表翻转后矩阵的行号,j代表列号,如果(j,i)在变换区外,b((i-1) n+j)=a((i-1) n+j),如果在变换区内,换算方法为:根据对称原理,变换前后列号不变,变换前也是j列,而行号是xy(2)+xy(4)-i,其中xy(2)是变换区的左上角行号,xy(4)是右下角行号。所以变换前元素号是(xy(2)+xy(4)-i-1) n+j,②处填a((xy(2)+xy(4)-i-1) n+j)。
③处所在循环输出变换后矩阵数据,每行要求显示n个数据,循环每次存放一个数据到c中,如果存满n个数据,则输出,所以③处填i mod n=0。
2.某人编写一个VB程序,功能如下:程序启动时产生n n个1到50之间的随机整数存数组a,如n=8时,产生64个随机整数,以行优先方式,按8行8列的形式在列表框List1中显示(即第一行依次显示a(1)~a(8),第二行依次显示a(9)~a(16),依次类推)。在文本框Text1中输入某矩形区域的左上角位置(x1,y1)(注:x1表示行号,y1表示列号),在文本框Text2中输入右下角位置(x2,y2),单击“水平翻转”按钮Command1,对以(x1,y1)和(x2,y2)为对角顶点的矩形区域中的数据进行水平翻转,并在列表框List2中显示。程序运行界面如图1所示,变换前的数据区域的值如图2所示,变换后的值如图3所示。
图1
10 44 8 2 6
28 13 9 2 30
22 25 14 40 26
46 46 47 24 1
18 45 29 15 41
6 2 8 44 10
30 2 9 13 28
26 40 14 25 22
1 24 47 46 46
41 15 29 45 18
实现上述功能的VB程序如下,请回答下列问题:
(1)根据题意可知,此次程序运行时数组元素a(12)的值为 (填写数值)。
(2)请在划线处填入合适的代码。
Const n=8
Dim a(1 To n^2) As Integer,b(1 To n^2) As Integer
Function adj(s As String,n As Integer)As String
'该函数功能:在字符串s前添加若干空格,实现右对齐。代码略。
End Function
Private Sub Form_Load()
'产生n n个1到50之间的随机整数存数组a,并List1中显示。代码略。
End Sub
Private Sub Command1_Click()
Dim x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer
Dim i As Integer,j As Integer,value As Integer,line As String
value=0
s=Text1.Text
For i=1 To Len(s)
If Mid(s,i,1)>=″0″And Mid(s,i,1)<=″9″ Then
①
Else
x1=value:value=0
End If
Next i
y1=value
'读取Text2中输入矩形区域的右下角位置,处理后把行号存x2,列号存y2。代码略。
For i=1 To n
For j=1 To n
If i>=x1 And i<=x2 And j>=y1 And j<=y2 Then
b((i-1) n+j)= ②
Else
b((i-1) n+j)=a((i-1) n+j)
End If
Next j
Next i
For i=1 To n^2
line=line+adj(Str(b(i)),3)
If ③ Then
List2.AddItem line
line=″ ″
End If
Next i
End Sub
答案 (1)8 (2)①value=value 10+Val(Mid(s,i,1))
②a((i-1) n+y1+y2-j) ③i Mod n=0
解析 (1)a(12)即为第2行第4列的数组元素,故a(12)的值为8。
(2)第①空考查遍历过程中,把数字字串转换成十进制数值,代码形式“变量名=变量名*R+当前分离得到的数字”,R表示不同的进制,此处R为10。故①处代码应为“value=value 10+Val(Mid(s,i,1))”。
②通过两层循环控制数组元素赋值,变量i控制行,j控制列,第(i,j)位置元素对应一维数组中的元素下标为(i-1) n+j,第②题主要考察二维方阵行列位置到一维数组下标之间的转换,方阵第(i,j)位置元素应赋值为方阵第(i,y1+y2-j)位置元素,故②处代码应为“a((i-1) n+y1+y2-j)”。
③一维数组以二维方阵形式输出,每行输出n个元素,第③空主要考查输出时的控制条件,当循环变量i值是n的倍数时需输出一行值,并清空line;否则,把a(i)拼接到line中,故③处代码应为“i Mod n=0”。
3.小王设计了一个顺时针旋转矩阵的程序,其功能为:运行程序时,在文本框Text1中输入矩阵规模n,点击“产生矩阵”按钮Command1,在列表框List1中显示一个n×n的矩阵,该矩阵数据由从1开始的连续自然数组成。点击“旋转矩阵”按钮Command2,该矩阵顺时针旋转90度并显示在列表框List2中。此后,每点一次“旋转矩阵”按钮Command2,列表框List2中显示的矩阵顺时针旋转90度。程序运行界面如图所示。
(1)运行程序,在文本框Text1中输入5,点击“产生矩阵”按钮Command1,再连续点击三次Command2按钮,则列表框List2中第一行显示的内容是 。
(2)实现此程序的代码如下,请在划线处填入合适的代码。
Dim n As Integer,st As String
Dim a(1 To 100) As Integer
Dim b(1 To 100) As Integer
Private Sub Command1_Click()
n=Val(Text1.Text)
For i=1 To n n
a(i)=i
Next i
For i=1 To n
st=″ ″
For j=1 To n
st=st+adj(Str(a((i-1) n+j)),3)
Next j
List1.AddItem st
Next i
End Sub
Private Sub Command2_Click()
List2.Clear
For i=1 To n
st=″ ″
For j=1 To n
b((i-1) n+j)= ①
st=st+adj(Str(b((i-1) n+j)),3)
Next j
List2.AddItem st
Next i
For i=1 To n n
a(i)= ②
Next i
End Sub
'adj函数的功能:在字符串a前加入适当的空格,使a的长度为n位
Function adj(a As String,n As Integer) As String
Dim sa As String
na=Len(a):sa=a
For i=1 To n-na
sa=″ ″+sa
Next i
adj= ③
End Function
答案 (1)5 10 15 20 25 (2)①a((n-j) n+i)
②b(i) ③sa
解析 (1)略 (2)①处双重循环功能是对矩阵顺时针旋转90度。数组a存放旋转前数据,数组b存放旋转后数据,变量i表示旋转后数据的行号,j表示列号。通过下表可以找出旋转前后行列变化的规律(以n=3为例):i=n-j+1,j=i
旋转后行列号(i,j) 旋转前行列号
(1,1) (1,3)
(1,2) (2,3)
(1,3) (3,3)
(2,1) (1,2)
(2,2) (2,2)
(2,3) (3,2)
……
所以①处填a((n-j) n+i)。②处循环把数组b中的数据存入a,为下一次旋转作准备,所以②处填b(i)。③处给自定义函数返回结果。
4.皇后的势力范围。在国际象棋,皇后的攻击范围是经过所在位置的任何直线和对角线,如图所示:
用VB设计一自定义函数,给定皇后所在位置p1和对方所在棋子位置p2(位置编号如上图所示,编号从左到右,从上到下,左上起第1格为①),判断皇后是否可以攻击对方棋子,如果可以返回true,不行则返回false。程序如下,请在划线处填入正确的语句。
Function judge(p1 As Integer,p2 As Integer) As Boolean
Dim f As Boolean,x1 As Integer,y1 As Integer
Dim x2 As Integer,y2 As Integer
x1=p1 Mod 8
y1=p1\8
x2=p2 Mod 8
y2=p2\8
If x1=x2 Or y1=y2 Or Then
f=True
Else
f=False
End If
judge=f
End Function
答案: abs(x1-x2)=abs(y1-y2)
解析: 由皇后的攻击范围可知,如果皇后所在横坐标x1和对方棋子的横坐标x2相同,或者是皇后所在纵坐标y1和对方棋子的纵坐标y2相同,或者是皇后与对方棋子所在的横坐标之差的绝对值等于纵坐标差的绝对值,则皇后可以攻击对方棋子,所以划线处应填abs(x1-x2)=abs(y1-y2)。其他典型算法之矩阵应用
【例1】 把矩阵A的行和列互相交换所产生的矩阵称为A的转置矩阵,这一过程称为矩阵的转置,如 。以下VB6程序实现矩阵的转置,请在划线处填入正确的语句实现功能。
Const m = 4
Const n = 5
Dim a(1 To m * n) As Integer
Dim b(1 To m * n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer
List1.Clear
List2.Clear
Randomize
For i = 1 To m * n '生成源矩阵
a(i) = Int(Rnd() * 89 + 10)
Next
For i = 1 To m '显示源矩阵
s = ″ ″
For j = 1 To n
s =①
Next
List1.AddItem s
Next
For i = 1 To n '生成并显示转置矩阵
s = ″″
For j = 1 To m
b((i - 1) * m + j) =②
s = s + Str(b((i - 1) * m + j))
Next
List2.AddItem s
Next
End Sub
【例2】.(2017·11浙江选考)由数组a生成数组b的方法描述如下:
(1)将数组a中的n个元素依次分割出若干个数据块,每个数据块有m×m个元素,m最大值为8,最小值为2。分割时,按尽可能大的数据块进行分割。
(2)对每个分割出的数据块用“方阵转换法”进行转换,每次转换后得到的数据块依次存储在数据b中。
(3)数组a分割后的剩余元素(个数小于4),直接依序存储到数组b中。
例如n=140时,可依次分割出3个数据块,元素的个数分别为64(8×8)、64(8×8)、9(3×3),剩余元素为3个。
“方阵转换法”过程如下:将数据块中m×m个元素按行序排列成一个数字方阵,从该数字方阵中按列序得到转换后元素的次序。以3×3数据块为例,转换过程如下图所示:
小明依据上述描述设计了如下VB程序。请回答下列问题:
(1)当n=120时,分割出的第3个数据块元素个数为 。
(2)请在划线处填入合适的代码。
Const n = 120
Dim a(1 To n) As Integer
Dim b(1 To n) As Integer
Private Sub Command1_Click()
Dim m As Integer, i As Integer
Dim Start As Integer '当前未分割数据的第1个元素下标
Dim Left As Integer '当前未分割数据的个数
Dim pa As Integer '数组a的下标
Dim pb As Integer '数组b的下标
'读取n个转换前的数据,依次存储到a(1)、a(2)、…、a(n)中,代码略
m = 8
Start = 1
Left = n
Do While Left > 3
If Left < m * m Then
m =①
Else
pa = Start
pb = Start
For i = 1 To m * m
b(pb) = a(pa)
pb = pb + 1
If i Mod m = 0 Then
②
Else
pa = pa + m
End If
Next i
③
Start = Start + m * m
End If
Loop
For i = Start To n
b(i) = a(i)
Next i
'依次输出转换后数据b(1)、b(2)、…、b(n)中,代码略
End Sub
课后作业
1.某程序功能如下:数组a中存放了n n个10到99之间的随机整数,按n行n列的形式在列表框List1中显示(即第一行依次显示a(1)~a(n),第二行依次显示a(n+1)~a(2 n),依次类推)。在文本框Text1中输入某矩形区域的左上角位置(x1,y1)(注:x1表示列号,y1表示行号),在文本框Text2中输入右下角位置(x2,y2),单击“垂直翻转”按钮Command1,对以(x1,y1)和(x2,y2)为对角顶点的矩形区域中的数据进行垂直翻转,并在列表框List2中显示。程序运行界面如图所示。
(1)依据上述描述设计如下VB程序。请在划线处填入合适的代码。
Const n=5
Dim a(1 To n^2) As Integer,b(1 To n^2) As Integer
Private Sub Form_Load()
'产生n n个10到99之间的随机整数存数组a,并在List1中显示。代码略。
End Sub
Private Sub Command1_Click()
Dim i As Integer,j As Integer,value As String,c As String,xy(1 To 4) As Integer
s=Text1.Text+″,″+Text2.Text
value=″ ″:j=0
For i=1 To Len(s)
c=Mid(s,i,1)
If c>=″0″ And c<=″9″ Then
value=value+c
Else
①
xy(j)=Val(value):value=″ ″
End If
Next i
xy(4)=Val(value)
For i=1 To n
For j=1 To n
If j>=xy(1) And j<=xy(3) And i>=xy(2) And i<=xy(4) Then
b((i-1) n+j)= ②
Else
b((i-1) n+j)=a((i-1) n+j)
End If
Next j
Next i
List2.Clear:c=″ ″
For i=1 To n n
c=c+Str(b(i))
if ③ then
List2.AddItem c
c=″ ″
end if
Next i
End Sub
(2)对于有10 10个元素构成的数组a,如果输入左上角位置是(2,3),右下角位置是(6,7),垂直翻转后,则元素a(23)在新数组中的位置是 。
2.某人编写一个VB程序,功能如下:程序启动时产生n n个1到50之间的随机整数存数组a,如n=8时,产生64个随机整数,以行优先方式,按8行8列的形式在列表框List1中显示(即第一行依次显示a(1)~a(8),第二行依次显示a(9)~a(16),依次类推)。在文本框Text1中输入某矩形区域的左上角位置(x1,y1)(注:x1表示行号,y1表示列号),在文本框Text2中输入右下角位置(x2,y2),单击“水平翻转”按钮Command1,对以(x1,y1)和(x2,y2)为对角顶点的矩形区域中的数据进行水平翻转,并在列表框List2中显示。程序运行界面如图1所示,变换前的数据区域的值如图2所示,变换后的值如图3所示。
图1
10 44 8 2 6
28 13 9 2 30
22 25 14 40 26
46 46 47 24 1
18 45 29 15 41
6 2 8 44 10
30 2 9 13 28
26 40 14 25 22
1 24 47 46 46
41 15 29 45 18
实现上述功能的VB程序如下,请回答下列问题:
(1)根据题意可知,此次程序运行时数组元素a(12)的值为 (填写数值)。
(2)请在划线处填入合适的代码。
Const n=8
Dim a(1 To n^2) As Integer,b(1 To n^2) As Integer
Function adj(s As String,n As Integer)As String
'该函数功能:在字符串s前添加若干空格,实现右对齐。代码略。
End Function
Private Sub Form_Load()
'产生n n个1到50之间的随机整数存数组a,并List1中显示。代码略。
End Sub
Private Sub Command1_Click()
Dim x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer
Dim i As Integer,j As Integer,value As Integer,line As String
value=0
s=Text1.Text
For i=1 To Len(s)
If Mid(s,i,1)>=″0″And Mid(s,i,1)<=″9″ Then
①
Else
x1=value:value=0
End If
Next i
y1=value
'读取Text2中输入矩形区域的右下角位置,处理后把行号存x2,列号存y2。代码略。
For i=1 To n
For j=1 To n
If i>=x1 And i<=x2 And j>=y1 And j<=y2 Then
b((i-1) n+j)= ②
Else
b((i-1) n+j)=a((i-1) n+j)
End If
Next j
Next i
For i=1 To n^2
line=line+adj(Str(b(i)),3)
If ③ Then
List2.AddItem line
line=″ ″
End If
Next i
End Sub
3.小王设计了一个顺时针旋转矩阵的程序,其功能为:运行程序时,在文本框Text1中输入矩阵规模n,点击“产生矩阵”按钮Command1,在列表框List1中显示一个n×n的矩阵,该矩阵数据由从1开始的连续自然数组成。点击“旋转矩阵”按钮Command2,该矩阵顺时针旋转90度并显示在列表框List2中。此后,每点一次“旋转矩阵”按钮Command2,列表框List2中显示的矩阵顺时针旋转90度。程序运行界面如图所示。
(1)运行程序,在文本框Text1中输入5,点击“产生矩阵”按钮Command1,再连续点击三次Command2按钮,则列表框List2中第一行显示的内容是 。
(2)实现此程序的代码如下,请在划线处填入合适的代码。
Dim n As Integer,st As String
Dim a(1 To 100) As Integer
Dim b(1 To 100) As Integer
Private Sub Command1_Click()
n=Val(Text1.Text)
For i=1 To n n
a(i)=i
Next i
For i=1 To n
st=″ ″
For j=1 To n
st=st+adj(Str(a((i-1) n+j)),3)
Next j
List1.AddItem st
Next i
End Sub
Private Sub Command2_Click()
List2.Clear
For i=1 To n
st=″ ″
For j=1 To n
b((i-1) n+j)= ①
st=st+adj(Str(b((i-1) n+j)),3)
Next j
List2.AddItem st
Next i
For i=1 To n n
a(i)= ②
Next i
End Sub
'adj函数的功能:在字符串a前加入适当的空格,使a的长度为n位
Function adj(a As String,n As Integer) As String
Dim sa As String
na=Len(a):sa=a
For i=1 To n-na
sa=″ ″+sa
Next i
adj= ③
End Function
4.皇后的势力范围。在国际象棋,皇后的攻击范围是经过所在位置的任何直线和对角线,如图所示:
用VB设计一自定义函数,给定皇后所在位置p1和对方所在棋子位置p2(位置编号如上图所示,编号从左到右,从上到下,左上起第1格为①),判断皇后是否可以攻击对方棋子,如果可以返回true,不行则返回false。程序如下,请在划线处填入正确的语句。
Function judge(p1 As Integer,p2 As Integer) As Boolean
Dim f As Boolean,x1 As Integer,y1 As Integer
Dim x2 As Integer,y2 As Integer
x1=p1 Mod 8
y1=p1\8
x2=p2 Mod 8
y2=p2\8
If x1=x2 Or y1=y2 Or Then
f=True
Else
f=False
End If
judge=f
End Function
