Parantezare optima de matrici

21/11/2010 § Leave a comment

Parantezare optima de matrici

Se dă un produs matricial M = M1M2…Mn. Cum înmulţirea matricelor este asociativă, toate parantezările conduc la acelaşi rezultat. Însă, numărul total de înmulţiri scalare al produsului matricial poate să difere substanţial în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor n matrici se dau sub forma unui şir d astfel încât perechea (di-1, di) reprezintă dimensiunile matricii Mi.

Cerinţă

Se cere să se minimizeze numărul total de înmulţiri scalare al produsului matricial M, valoare ce corespunde unei parantezări optime.

Date de intrare

Fişierul de intrare podm.in conţine pe prima linie un număr natural n, reprezentând numărul matricelor. Pe următoarea linie se găsesc n + 1 numere naturale, reprezentând valorile şirului d.

Date de ieşire

În fişierul de ieşire podm.out se va găsi un singur număr natural egal cu valoarea minimă a numărului total de înmulţiri scalare a produsului matricial M.

Restricţii

  • 1 ≤ n ≤ 500
  • 1 ≤ di ≤ 10 000, unde 0 ≤ i ≤ n

Exemplu

podm.in podm.out
4
13 5 89 3 34
2856

Rezolvare:

#include <iostream.h>
#include <fstream.h>
int d[100], c[100][100], n, op[100], cl[100];
ifstream f(“podm.in”);
ofstream g(“podm.out”);
void citire ()
{
int i;
f>>n;
for (i=0;i<=n;i++) f>>d[i];
f.close();
}
int min (int a, int b)
{
if(a<b)return a;
return b;
}
void matrice ()
{
int i,p,aux,k,j;
for (i=1;i<=n;i++)
c[i][i]=0;
for (i=1;i<=n-1;i++)
c[i][i+1]=d[i-1]*d[i]*d[i+1];
for (p=2;p<=n-1;p++)
for (i=1;i<=n-p;i++)
{
j=i+p;
c[i][j]=c[i][i]+c[i+1][j]+d[i-1]*d[i]*d[j];
c[j][i]=i;
for (k=i+1;k<=j-1;k++)
{
aux=c[i][k]+c[k+1][j]+d[i-1]*d[k]*d[j];
if(c[i][j]>aux)
{
c[i][j]=aux;
c[j][i]=k;
}
}
}
g<<c[1][n];
}
int main()
{
citire ();
matrice ();
return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Parantezare optima de matrici at crengux.

meta

%d bloggers like this: