[单选题]
答案：选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)
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)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
