算法是一门让我很头疼的课程，因为平时也不怎么写代码，现在学了算法了，来总结一下一些基本算法。
矩阵连乘
最优值(最少数乘次数)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void matrixchain(int *p,int n,int **m,int **s)
{
for(int i=1;i<=n;i++)m[i][i]=0;
for(int r=2;r<=n;r++)
for(int i=1;i<=n-r+1;i++) //行
{
int j=i+r-1; //列
m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//在i处断开,
//m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j],
//而m[i][i]=0,所以m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]
s[i][j]=i; //i处断开
for(int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; //k=i+1,表示从i以后的点处断开
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
|
输出最优解
1
2
3
4
5
6
7
8
| void trackback(int i,int j,int **s)
{
if(i==j)return;
trackback(i,s[i][j],s);
trackback(s[i][j]+1,j,s);
cout<<"Mulitiply A"<<i<<","<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;
}
|
