Reședință - Portal SEI Portalul educațional SEI  Admitere Admitere Bacalaureat Bacalaureat Titularizare Titularizare Euro 200 Euro 200 Bani de Liceu Bani de Liceu
Găzduire WEB pentru școli și licee Găzduire WEB pentru școli, licee și instituții educaționale Dictionare online Dicționare online Subiecte examene naționale "2007-2008" Subiecte examene naționale "2007-2008"
Subiecte examene naționale începând cu 2002 Subiecte examene naționale începând cu 2002 .campion .campion
SIVECO Romania  Ministerul Educației și Cercetării



  Răspunde la acest subiectSubiect nou Sondaj nou

> Problema Codul oji 2002, greseala de implementare ?
userHack
  Trimis: 11 Feb 2011, 03:39 PM


La prima intervenție


Grup: Members
Mesaje: 1
Înscris: 11 Feb 11


Enuntul problemei gasiti aici
Am mici probleme la rezolvarea ei, folosesc programarea dinamica pt a determina lungimea celui mai lung subsir comun, apoi back pt a afisa sirul, programul intra in timp, numai ca nu ofera raspunsul corect pe 3 teste si nu stiu unde gresec, poate ma puteti ajuta
CODE

#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#define N_MAX 211
#define pr pair< int, int >
#define mkpr make_pair< int, int >

using namespace std;
string x, y, r, s;
int C[N_MAX][N_MAX]; //matricea pt dinamica, elementele cu - vor fi elementele in care nu am avut un match
vector< pr > v[N_MAX]; //aici voi retine coordonatele i, j ale locurilor in matrice unde am obtinut un match
vector< pr >::const_iterator it, iend;
inline int _max( int x, int y )
{
return ( x >= y ? x : y );
}
inline int _abs( int x )
{
return ( x >= 0 ? x : -x );
}
inline bool cmp( const pr& i, const pr& j )
{
return x[i.first] > x[j.first];
}
void back( int iMin, int jMin, int k )
{
if( 0 == k ) //am gassit solutie, o afisez si gata
{
 ofstream out( "codul.out" );
 reverse( s.begin(), s.end() );
 out<<s<<'\n';
 out.close();
 exit(0);
 return;
}
vector< pr >::const_iterator it, iend;
for( it=v[k].begin(), iend=v[k].end(); it < iend; ++it )
 if( it->first < iMin && it->second < jMin )
 {
  s.push_back(x[it->first]);
  back( it->first, it->second, k-1 );
  s=s.substr( 0, s.length()-1 ); //sterg ultimul caracter
 }
}
int main( void )
{
int xLength, yLength, i, j, k;
ifstream in( "codul.in" );
in>>x>>y;
xLength=x.size();
yLength=y.size();
for( i=0; i < xLength; ++i ) //dinamica
{
 for( j=0; j < yLength; ++j )
 {
  if( x[i] == y[j] )//daca am gasit un match
  {
   if( 0 == i*j ) //unul dintre indexi este 0
             C[i][j]=1;
   else C[i][j]=_abs(C[i-1][j-1])+1;
   v[C[i][j]].push_back( mkpr( i, j ) );
  }
  else {
    if( 0 == i*j)
       C[i][j]=0;
    else C[i][j]=-_max( _abs(C[i-1][j]), _abs(C[i][j-1]) ); //nefiind un match, il pun cu -
    }
 }
}
for( i=1, k=_abs(C[xLength-1][yLength-1]); i <= k; ++i ) //sortez elementele de pe fiecare nivel, asta imi asigura k prima solutie din back e cea mai mare generata
 sort( v[i].begin(), v[i].end(), cmp );
back( xLength, yLength, k ); //generez solutia
return EXIT_SUCCESS;
}
Mesaj personal
Top
0 utilizator(i) citesc acest subiect (0 vizitatori și 0 utilizatori anonimi)
0 utilizator(i):

Opțiuni Răspunde la acest subiectSubiect nou Sondaj nou

 

 
  © 2002 SIVECO Romania SA. All Rights Reserved