matrixchainmult
#include <bits/stdc++.h>
using namespace std;
int **create2Darr(int x, int y)
{
int **p, *q, i;
q = new int[x * y];
p = new int*[x];
for (i = 0; i < x; i++)
{
p[i] = q + i * y;
}
return p;
}
int **findk(int d[], int n)
{
int m[n + 1][n + 1], **s, z, i, j, k, l;
s = create2Darr(n + 1, n + 1);
for (i = 1; i <= n; i++)
{
for(j = 1; j<=n; ++j)
m[i][i] = s[i][j] = 0;
}
for (l = 2; l <= n; l++)
{
for (i = 1; i <= n - l + 1; i++)
{
j = i + l - 1;
m[i][j] = 65535;
for (k = i; k < j; k++)
{
z = m[i][k] + m[k + 1][j] + d[i - 1] * d[k] * d[j];
if (z < m[i][j])
{
m[i][j] = z;
s[i][j] = k;
}
}
}
}
return s;
}
int **matmul(int **a, int **b, int p, int q, int r)
{
int **c = create2Darr(p, r);
int i, j, k, sum;
for (i = 1; i <= p; i++)
{
for (j = 1; j <= q; j++)
{
sum = 0;
for (k = 1; k <= r; k++)
{
sum = sum + a[i][k] * b[k][j];
}
c[i][j] = sum;
}
}
return c;
}
int **matrixchain(int **A[], int i, int j, int **s, int d[])
{
int **m1, **m2, **res;
if (i < j)
{
m1 = matrixchain(A, i, s[i][j], s, d);
m2 = matrixchain(A, s[i][j] + 1, j, s, d);
res = matmul(m1, m2, d[i - 1], d[s[i][j]], d[j]);
return res;
}
}
void ip(int **m, int x, int y)
{
int i, j;
cout<<endl<<"Enter the matrix"<<endl;
for (i = 1; i <= x; i++)
{
for (j = 1; j <= y; j++)
{
cin >> m[i][j];
}
}
}
int main()
{
int n, i, j;
cout << "Enter the number of matrices: ";
cin >> n;
int d[n + 1], **s;
cout << "Enter the dimensions:\n";
for (i = 0; i <= n; i++)
{
cin >> d[i];
}
s = findk(d, n);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (i > j)
{
cout << "0 ";
}
else
{
cout << s[i][j] << " ";
}
}
cout << "\n";
}
int **A[n + 1];
for (i = 1; i <= n; i++)
{
A[i] = create2Darr(d[i - 1]+1, d[i]+1);
ip(A[i], d[i - 1], d[i]);
}
int **res = matrixchain(A, i, j, s, d);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
cout << res[i][j] << " ";
}
cout << "\n";
}
return 0;
}
Comments
Post a Comment