Parantezare optima de matrici

Se dă un produs matricial M = M₁M₂…M_n. 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 (d_i-1, d_i) reprezintă dimensiunile matricii M_i.

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 ≤ d_i ≤ 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;
}

Domino

Enunt:Se dau n piese de domino.Fiecare piesa poate fi rotita cu 180 de grade.Sa se determine subsiruri de piese de lungime maxima astfel incat oricare doua piese alaturate sa aiba un numar in comun.

Exemplu:

domino.in                                                          cout:

5 6                                                                      6 5
1 1                                                                       5 2
2 5                                                                      2 3
3 2                                                                     3 5
1 5                                                                      5 5
6 4                                                                     5 2
5 1
5 3
2 1
1 4
5 5
5 2
3 3

Algoritm:

#include<iostream.h>
#include<fstream.h>
typedef struct{int first,sec;}PIESA;
PIESA v[100];
int d[2][100],poz[2][100],n;
void citire()
{
n=0;
ifstream f(“domino.in”);
while(!f.eof())f>>v[++n].first>>v[n].sec;
f.close();
}
void dinamica()
{
int i,j,max1,max0,p0,p1;
d[0][n]=d[1][n]=0;
poz[0][n]=poz[1][n]=0;
for(i=n-1;i>=1;i–)
{max0=max1=0;
p0=p1=0;
for(j=i+1;j<=n;j++)
{if(v[i].sec==v[j].first && d[0][j]>max0){max0=d[0][j];
p0=j;}
if(v[i].sec==v[j].sec && d[1][j]>max0){max0=d[1][j];
p0=j;}
if(v[i].first==v[j].sec && d[1][j]>max1){max1=d[1][j];
p1=j;
if(v[i].first==v[j].first && d[0][j]>max1){max1=d[0][j];
p1=j;}
}
d[0][i]=max0+1;
d[1][i]=m
poz[0][i]=p0;
poz[1][i]=p1;}
}
void afisare()
{
int k,p,aux,i,max=0;
for(i=1;i<=n;i++){if(d[0][i]>max){max=d[0][i];k=0;p=i;}
if(d[1][i]>max){max=d[1][i];k=1;p=i;}
}
if(k==0){cout<<v[p].first<<” “<<v[p].sec<<”\n”;aux=v[p].sec;}
else {cout<<v[p].sec<<” “<<v[p].first<<”\n”;aux=v[p].first;}
p=poz[k][p];
while(p>0){if(aux==v[p].first){cout<<v[p].first<<” “<<v[p].sec<<”\n”;
k=0;aux=v[p].sec;}
else {cout<<v[p].sec<<” “<<v[p].first<<”\n”;
k=1;aux=v[p].first;}
p=poz[k][p];}
}
int main()
{
int k,p,i,max=0;
citire();
dinamica();
for(i=1;i<=n;i++){if(d[0][i]>max){max=d[0][i];k=0;p=i;}
if(d[1][i]>max)max=d[1][i];k=1;p=i;}
cout<<max<<”\n”;
afisare();
return 0;
}

Subsir Comun Maximal

Enunt: Se dau x, y doua siruri cu m , n numere. Se cere sa se determine cel mai lung subsir comun celor doua siruri.

Exemplu:

nr.in                                                               cout:

8                                                                      4
10 4 20 10 40 2 0 60                                4   10    2    0
9
4 90 7 10 70 2 71 81 0

Algoritm:

#include<iostream.h>
#include<fstream.h>
int a[100][100],x[100],y[100],m,n;
void citire()
{
int i;
ifstream f(“subsir.in”);
f>>m>>m;
for(i=1;i<=m;i++)f>>x[i];
for(i=1;i<=n;i++)f>>y[i];
f.close();
}

int maxim(int x,int y)
{
if(x>y)return x;
return y;
}
void dinamita()
{
int i,j;
for(i=0;i<=m;i++)
a[0][i]=0;
for(i=1;i<=n;i++)
a[i][0]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(x[i]==y[j])
a[i][j]=a[i-1][j-1]+1;
else
a[i][j]=maxim(a[i-1][j],a[i][j-1]);
cout<<”lungimea maxima este”<<a[m][n]<<”\n”;
}
void afis()
{
int v[100],k,i,j;
i=m;
j=n;
k=0;
while(i>0 && j>0)
if(x[i]==y[j])
{
v[++k]=x[i];
i–;
j–;
}
else
{
if(a[i][j]==a[i-1][j])
i–;
else j–;
}
for(i=k;i>=1;i–)cout<<v[i]<<” “;
}
int main()
{
citire();
dinamita();
afis();
return 0;
}

Subsir Crescator Maximal

-enunt:

Se citeste de la tastatura n, un numar natural si un vector v cu n elemente naturale. Afisati cel mai lung subsir de numere din vectorul v ordonat crescator si lungimea acestuia.

D.I. :  Fisierul “subsir.in” contine pe prima linie n iar pe urmatoarea linie n numere naturale.

D.O.:  Fisierul “subsir.out” va contine pe prima linie lungimea maxima a sirului si pe urmatoarea linie elementele sirului.

-exemplu:

subsir.in

7
3 6 9 2 5 11 45

subsir.out

Lungimea maxima este 5

3 6 9 11 45

-program:

#include<iostream.h>
#include<fstream.h>
int n,v[100],d[100],p[100];
ofstream g(“subsir.out”);
void citire()
{
int i;
ifstream f(“subsir.in”);
f>>n;
for(i=1;i<=n;i++)
f>>v[i];
f.close();
}
void afisare(int k)
{
while(k!=0)
{
g<<v[k]<<” “;
k=p[k];
}
}
void dinamita()
{
int i,j,poz,pozm,maxp,max;
d[n]=1;
p[n]=0;
pozm=n;
maxp=1;
for(i=n-1;i>=1;i–)
{
max=0;
poz=-1;
for(j=i+1;j<=n;j++)
if(v[j]>v[i] && d[j]>max)
{
max=d[j];
poz=j;
}
if(poz==-1)
{
d[i]=1;
p[i]=0;
}
else
{
d[i]=1+d[poz];
p[i]=poz;
if(d[i]>maxp)
{
maxp=d[i];
pozm=i;
}
}
}
g<<maxp<<”\n”;
afisare(pozm);
}
int main()
{
citire();
dinamita();
return 0;
}