Subsir Comun Maximal

16/11/2010 § Leave a comment

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

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 Subsir Comun Maximal at crengux.

meta

%d bloggers like this: