编写矩阵乘法的Neon程序,若矩阵元素为双精度浮点数,则应对矩阵乘加计算的循环进行()路循环展开。
A.2
B.4
C.8
D.16
A.2
B.4
C.8
D.16
A.O(N2)
B.O(N2Lgn)
C.O(N3)
D.O(n3lgn)
请编制程序,其功能是:求I×J矩阵的转置矩阵(矩阵中元素为字节型),并计算转置矩阵的每一行元素之和,然后存放在每一行最后一个字单元中。
例如:
内存中有04H,05H,06H,(第一行)01H,02H,03H(第二行)
结果为 04H,01H,05H,00H,05H,02H,07H,00H,06H,03H,09H,00H
部分程序已给出,其中原始数据由过程LOAD从文件1NPUT1.DAT中读入SOURCE开始的内存单元中。运算结果要求从RESULT开始存放,由过程SAVE保存到文件OUTPUT1.DAT中。
请填空BEGIN和END之间已经给出的一段源程序使其完整,需填空处已经用横线标出,每个空白一般只需要填一条指令或指令的一部分(指令助记符或操作数),也可以填入功能相当的多条指令,或删去BEGIN和END之间原有的代码并自行编程来完成所要求的功能。对程序必须进行汇编,并与IO.OBJ链接产生可执行文件,最终运行程序产生结果。调试中若发现整个程序中存在错误之处,请加以修改。
试题程序:
阅读以下说明及Visual Basic程序代码,将应填入(n)处的字句写在对应栏内。
[说明]
本程序提供了三阶矩阵加、减及乘运算的功能。用户单击“生成操作数”按钮将随机生成两个矩阵(即操作数1和操作数2),再单击某一矩阵运算按钮后,程序将输出相应运算的结果。程序运行界面如下:
开发过程中,界面上从左至右三个文本框分别取名为Text1至Text3,“生成操作数”按钮名为 CmdNew,“+”、“-”和“*”构成按钮控件组,分别名为CmdOperate(0)、CmdOperate(1)和CmdOperate(2)。
已知n阶矩阵加、减法运算法则是对应位置的元素相加、减;n阶矩阵的乘法C=AB有公式:Cij=AilBij+AilBij+…+An1Bnj其中记号Xij表示矩阵X第i行第j列上的元素。程序使用的主要变量是三维数组matrix(3,3,3),其元素matrix(i,j,k)代表第i个矩阵j行k列上的元素,这里i,j,k均从0开始计数,第0、1、2个矩阵分别表示操作数1、操作数2和结果矩阵。
代码中用到的子过程及其功能说明如下:
(1) Sub newMatrices():随机产生矩阵运算的两个操作数;
(2) Sub printOut(txt As TextBox, i As Integcr):定义矩阵i向文本框txt的输出格式;
(3) Sub operate(operation As String):计算并输出矩阵运算结果。
[Visual Basic代码]
Dim matrix(3, 3, 3) As Integer
Sub newMatrices()
……… End Sub
Sub printOut(txt As TextBox, i As Integer)
……… End Sub
Sub operate(operation As String)
Dim i, j, k As Integer
For i = 0 To 2
For j = 0 To 2
(1)
Case"+": matrix(2, i, j) = matrix(0, i, j) + matrix(1, i, j)
Case"-": matrix(2, i, j) = matrix(0, i, j) - matrix(1, i, j)
Case"*"
matrix(2, i, j) = 0
For k = 0 To 2
matrix(2, i, j) = matrix(2, i, j) +(2)
Next
End Select
Next
Next
printOut (3)
End Sub
Private Sub CmdNew_Cliek() ’“生成操作数”按钮的单击事件响应代码
(4)
printout Text1,0
printout Text2,1
End Sub
Private Sub CmdOperale_Click(Index As Integer) ’矩阵运算按钮组的单击事件响应代码
operate CmdOperate(Index).(5)
End Sub
试题四(15分)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
某工程计算中要完成多个矩阵相乘(链乘)的计算任务。
两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数,计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法,计算Am*n*Bn*p,需要m*n*p次乘法运算。
矩阵相乘满足结合律,多个矩阵相乘,不同的计算顺序会产生不同的计算量。以矩阵A110*100,A2100*5,A35*50三个矩阵相乘为例,若按(A1*A2)*A3计算,则需要进行10*100*5+10*5*50=7500次乘法运算;若按A1*(A2*A3)计算,则需要进行100*5*50+10*100*50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。
矩阵链乘问题可描述为:给定n个矩阵<A1,A2,….An>,矩阵Ai的维数为pi-1*Pi,其中i = 1,2,….n。确定一种乘法顺序,使得这n个矩阵相乘时进行乘法的运算次数最少。
由于可能的计算顺序数量非常庞大,对较大的n,用蛮力法确定计算顺序是不实际的。经过对问题进行分析,发现矩阵链乘问题具有最优子结构,即若A1*A2*…*An的一个最优计算顺序从第k个矩阵处断开,即分为A1*A2*….Ak和Ak+1*Ak+2*…*An两个子问题,则该最优解应该包含A1*A2*…*Ak的一个最优计算顺序和Ak+1*Ak+2*…An的一个最优计算顺序。据此构造递归式,
其中,cost[i][j]表示Ai+1*Ai+2*...Aj+1的最优计算的计算代价。最终需要求解cost[0][n-1]。
【C代码】
算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量,然后依次计算3个矩阵、4个矩阵、…、n个矩阵相乘的最小计算量及最优计算顺序。下面是算法的C语言实现。
(1)主要变量说明
n:矩阵数
seq[]:矩阵维数序列
cost[][]:二维数组,长度为n*n,其中元素cost[i][j]表示Ai+1*Ai+2*…Aj+1的最优计算的计算代价
trace[][]:二维数组,长度为n*n,其中元素trace[i][j]表示Ai+1*Ai+2*Aj+1的最优计算对应的划分位置,即k
(2)函数cmm
define N 100
intcost[N][N];
inttrace[N][N];
int cmm(int n,int seq[]){
int tempCost;
int tempTrace;
int i,j,k,p;
int temp;
for(i=0;i<n;i++){ cost[i][i] =0;}
for(p=1;p<n;p++){
for(i=0; (1) ;i++){
(2);
tempCost = -1;
for(k = i;k<j;k++){
temp = (3) ;
if(tempCost==-1||tempCost>temp){
tempCost = temp;
(4) ;
}
}
cost[i][j] = tempCost;
trace[i][j] = tempTrace;
}
}
return cost[0][n-1];
}
【问题1】(8分)
根据以上说明和C代码,填充C代码中的空(1)~(4)。
【问题2】(4分)
根据以上说明和C代码,该问题采用了 (5) 算法设计策略,时间复杂度 (6) 。(用O符号表示)
【问题3】(3分)
考虑实例n=6,各个矩阵的维数:A1为5*10,A2为10*3,A3为3*12,A4为12*5,A5为5*50,A6为50*6,即维数序列为5,10,3,12,5,50,6。则根据上述C代码得到的一个最优计算顺序为 (7) (用加括号方式表示计算顺序),所需要的乘法运算次数为 (8) 。
A.n(n-1)
B.n2/2
C.n(n-1)/2
D.n(n+1)/2
若采用邻接矩阵来存储简单有向图,则其某一个顶点i的入度等于该矩阵(20) 。
A.第i行中值为1的元素个数
B.所有值为1的元素总数
C.第i行及第i列中值为l的元素总个数
D.第i列中值为1的元素个数
若采用邻接矩阵来存储简单有向图,则其某一个顶点i的入度等于该矩阵(37)。
A.第i行中值为1的元素个数
B.所有值为1的元素总数
C.第i行及第i列中值为1的元素总个数
D.第i列中值为1的元素个数
A.第i行中值为1的元素个数
B.所有值为1的元素总数
C.第i行及第i列中值为1的元素总个数
D.第i列中值为1的元素个数
例如,输入下面的矩阵: 其转置矩阵为:
1 2 3 1 4 7
4 5 6 2 5 8
7 8 9 3 6 9
程序输出:
2 6 10
6 10 14
10 14 18
注意:部分源程序在文件PROGl.C中。
请勿改动主函数main和其他函数中的任何内容,仅在函数fun的花括号中填入你编写的若干语句。