Enunt:

Se dau n matrici A1,A2,…,An,matricea A1 are dimensiunile d0*d1,matricea A2 are dimensiunile d1*d2…matricea Ai are dimensiunile di-1*di.

Se cere:

Sa se gaseasca o ordine de inmultire a matricelor astfel incat numarul de inmultiri sa fie minim.

Exemplu:

A[mxn]xB[nxp]=C[mxp]=numarul de inmultiri este mxnxp

c[i][j]=0,i=j sau c[i][j]=min(c[i][j],c[i][k]+c[k+1][j]+d[i-1]xd[k]xd[j]),k=i,j-1;

c[i][j]-reprezinta numarul minim de inmultiri necesare produsului AixAi+1x…xAj

Rezultatul va fi in c[1][n]

Rezolvare:

#include<iostream.h>
#include<fstream.h>
#define INF 10000000
int c[100][100],d[101],n;
void citire()
{
ifstream f(„inmultire.in”);
f>>n;
for(int i=0;i<=n;i++)f>>d[i];
f.close();
}
void dinamica()
{
int i,j,p,k,min,kmin;
for(i=1;i<=n;i++)c[i][i]=0;
for(p=1;p<=n-1;p++)
for(i=1;i<=n-p;i++)
{
j=i+p;
min=INF;
kmin=-1;
for(k=i;k<=j-1;k++)
if(min>c[i][k]+c[k+1][j]+d[i-1]*d[k]*d[j])
{
min=c[i][k]+c[k+1][j]+d[i-1]*d[k]*d[j];
kmin=k;
}
c[i][j]=min;
c[j][i]=kmin;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<c[i][j]<<” „;
cout<<„\n”;
}
}
void afisare(int i,int j)
{
if(i==c[j][i])cout<<„A”<<i;
else
{
cout<<„(„;
afisare(i,c[j][i]);
cout<<„)”;
}
cout<<„*”;
if(j==c[j][i]+1)cout<<„A”<<j;
else {
cout<<„(„;
afisare(c[j][i]+1,j);
cout<<„)”;
}
}
int main()
{
citire();
dinamica();
afisare(1,n);
return 0;
}