算法设计与分析（二）

1	/****************** 递归算法求解 ******************/
2	int MatrixChain_Recursive(int i, int j, int p, int *s)
3	{
4	if (i == j)
5	return 0;
6	int u = MatrixChain_Recursive(i, i, p, s) + MatrixChain_Recursive(i + 1, j, p, s) + p[i - 1] * p[i] * p[j];
7	s[i][j]=i;
8	for (int k = i+1; k < j; k++)
9	{
10	int tmp = MatrixChain_Recursive(i, k, p, s) + MatrixChain_Recursive(k + 1, j, p, s) + p[i - 1] * p[k] * p[j];
11	if (tmp < u)
12	{
13	u = tmp;
14	s[i][j] = k;
15	}
16	}
17	return u;
18	}

1	/****************** 动态规划算法 ******************/
2	void MatrixChain_Dynamic(int n, int p, int m, int *s)
3	{
4	for (int i = 1; i <= n; i++)
5	m[i][i] = 0; // l = 1
6	for (int r = 2; r <= n; r++) // l is the chain length, 自底向上！
7	for (int i = 1; i <= n -r + 1; i++)
8	{
9	int j = r + i - 1;
10	m[i][j] = m[i + 1][j] +p[i-1]p[i]p[j]; //i,j分别对应矩阵链的首尾
11	s[i][j] = i; // k = i
12	for (int k = i + 1; k < j; k++)
13	{
14	int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
15	if (t < m[i][j])
16	{
17	m[i][j] = t;
18	s[i][j] = k;
19	}
20	}
21	}
22	}

1	/****************** 备忘录法 ******************/
2	int LookupChain(int i,int j,int p,int m,int *s)
3	{
4	if (m[i][j] > 0)
5	return m[i][j];
6	if (i == j)
7	return 0;
8	int u = LookupChain(i, i, p, m, s) + LookupChain(i + 1, j, p, m, s) + p[i - 1] * p[i] * p[j];
9	s[i][j]=i;
10	for (int k = i+1; k < j; k++)
11	{
12	int tmp = LookupChain(i, k, p, m, s) + LookupChain(k + 1, j, p, m, s) + p[i - 1] * p[k] * p[j];
13	if (tmp < u)
14	{
15	u = tmp;
16	s[i][j] = k;
17	}
18	}
19	m[i][j] = u;
20	return u;
21	}
22
23	int MatrixChain_LookUp(int i, int j, int n, int p, int m, int *s)
24	{
25	for (int p = 1; p <= n; p++)
26	for (int q = 1; q <= n; q++)
27	m[p][q] = 0;
28	return LookupChain(i, j, p, m, s);
29	}

1	/***************************************构造最优解*********************************************************/
2	void Traceback(int i, int j, int **s)
3	{
4	if (i == j)
5	cout << "A"<<i;
6	else
7	{
8
9	cout << "(";
10	Traceback(i, s[i][j], s);
11	Traceback(s[i][j] + 1, j, s);
12	cout << ")";
13	}
14	}

1	int main()
2	{
3	int select;
4	int p[] = {30,35,15,5,10,20,25};
5	int n = sizeof(p) / sizeof(*p) - 1;
6	int *m = new int [n + 1];
7	int *s = new int [n + 1];
8	for (int i = 1; i <= n; i++)
9	{
10	m[i] = new int[n + 1];
11	s[i] = new int[n + 1];
12	}
13	printf("*******动态规划算法***\n");
14	printf("****1.动态规划算法****\n");
15	printf("****2.递归算法*******\n");
16	printf("****3.备忘录算法*****\n");
17	printf("*****0.退出**********\n");
18	printf("*************************\n");
19	printf("请选择：");
20	scanf("%d",&select);
21	if(select=1) { /****************** 动态规划算法******************/
22	cout<<"动态规划算法"<<endl;
23	cout << "最优值为：";
24	MatrixChain_Dynamic(n, p, m, s);
25	cout << m[1][n] << endl;
26	cout << m[2][5] << endl;
27	}
28	else if(select=2) {
29	/****************** 递归算法求解 ******************/
30	cout<<"递归算法求解"<<endl;
31	cout << "最优值为：";
32	cout << MatrixChain_Recursive(1, n, p, s) << endl;
33	cout << MatrixChain_Recursive(2, 5, p, s) << endl;
34	} else
35	if (select=3) {
36	/****************** 备忘录算法 ******************/
37	cout<<"备忘录算法"<<endl;
38	cout << "最优值为：";
39	cout << MatrixChain_LookUp(1, n, n, p, m, s) << endl;
40	cout << MatrixChain_LookUp(2, 5, n, p, m, s) << endl;
41	}
42	else if(select=0){
43	exit(0);
44	}
45	cout<<"最优解为：";
46	Traceback(1, n, s);
47	cout << endl;
48	for (int i = 1; i <= n; i++)
49	{
50	delete[] m[i];
51	delete[] s[i];
52	}
53	delete[] m;
54	delete[] s;
55
56	return 0;
57	}

递归算法求解矩阵连乘