首页 > 试题广场 >

设有矩阵A1(30*35)、A2(35*15)、A3(15*

[单选题]
设有矩阵A1(30*35)、A2(35*15)、A3(15*5)、A4(5*10)，M=A1*A2*A3*A4，下列组合计算M所需数乘次数最少的是？ 
  • (A1(A2(A3A4)))
  • (A1((A2A3)A4))
  • ((A1A2)(A3A4))
  • ((A1(A2A3))A4)
  • (((A1A2)A3)A4)
添加回答
迈杰头像 迈杰
答案：选D

运行结果：
m value is:
0,15750,7875,9375,
0,0,2625,4375,
0,0,0,750,
0,0,0,0,
s value is:
0113
0023
0003
0000
The result is:
((A1(A2A3））A4）

主要代码：

public class Nowcoder20150929 {
//N表示矩阵的个数
public static final int N = 4;

public static void main(String[] args) {
//由于矩阵相乘的特性p的长度为N+1
int[] datas = new int[] { 30, 35, 15, 5, 10 };
//m[i][j]表示的是i~j矩阵对应的最小计算代价
int[][] m = new int[N + 1][N + 1];
//s[i][j]表示的是在m[i][j]情况下的分割点
int[][] s = new int[N + 1][N + 1];
int i, j;
matrix_chain_order(datas, m, s);
//打印最小计算代价
System.out.println("m value is:");
for (i = 1; i <= N; ++i) {
for (j = 1; j <= N; ++j) {
System.out.print(m[i][j] + ",");
}
System.out.println();
}

System.out.println("s value is:");
for (i = 1; i <= N; ++i) {
for (j = 1; j <= N; ++j) {
System.out.print(s[i][j]);
}
System.out.println();
}
System.out.println("The result is:");
print_optimal_parents(s, 1, N);
}

private static void print_optimal_parents(int[][] s, int i, int j) {

if (i == j) {
System.out.print("A" + i);
} else {
System.out.print("(");
print_optimal_parents(s, i, s[i][j]);
print_optimal_parents(s, s[i][j] + 1, j);
System.out.print("）");
}

}

private static void matrix_chain_order(int[] p, int[][] m, int[][] s) {
int i, j, k, t;
for (i = 0; i <= N; ++i){
//i~i上只有一个矩阵，所以计算量为0
m[i][i] = 0;
}
for (t = 2; t <= N; t++) // 当前链乘矩阵的长度
{//t表示的是后一个矩阵
for (i = 1; i <= N - t + 1; i++) // 从第一矩阵开始算起，计算长度为t的最少代价
{//i表示的是前一个矩阵
j = i + t - 1;// 长度为t时候的最后一个元素
m[i][j] = Integer.MAX_VALUE; // 初始化为最大代价
for (k = i; k <= j - 1; k++) // 寻找最优的k值，使得分成两部分k在i与j-1之间
{
int temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (temp < m[i][j]) {
m[i][j] = temp; // 记录下当前的最小代价
s[i][j] = k; // 记录当前的括号位置，即矩阵的编号
}
}
}
}
}
}
发表于 2015-09-29 22:43:11 回复(0)
Aesthetic92头像 Aesthetic92

p0 = 30, p1 = 35, p2 = 15, p3 = 5, p4 = 10；
这题就是要计算m[1][4]

当然再计算一下m[1][3],m[2][4]
计算得出m[1][4] = 9375次，((A1(A2A3))A4)
所以选D


发表于 2015-01-02 18:33:10 回复(0)
提交观点

问题信息

完美世界 动态规划
上传者：飞雨
难度：
2条回答 19004浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号