online: 15; azi: 559; total: 67871 Manual clasa a xi a - Tehnici de programare - Microproiecte

Manual clasa a Xi a

Tehnici de programare

Microproiecte

Rezolvaţi problema determinării unui subşir crescător de lungime maximă folosind metoda greedy şi metoda programării dinamice.
# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_SIZE = 1000 ;
int sequence [MAX_SIZE];
int dp [MAX_SIZE];
int n;
int longest_increasing_subsequence_dp ( int idx ) {
if ( dp [ idx ] != -1 ) {
return dp [ idx ];
}
int max_len = 1 ;
for ( int i = idx + 1 ; i < n; i++) {
if ( sequence [i] > sequence [ idx ]) {
max_len = max ( max_len , 1 + longest_increasing_subsequence_dp (i));
}
}
dp [ idx ] = max_len ;
return dp [ idx ];
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> sequence [i];
}
memset ( dp , -1 , sizeof ( dp ));
int max_len_dp = 0 ;
for ( int i = 0 ; i < n; i++) {
max_len_dp = max ( max_len_dp , longest_increasing_subsequence_dp (i));
}
cout << "Lungimea maxima (DP): " << max_len_dp << endl ;
return 0 ;
}
# include < iostream >
# include < climits >
using namespace std ;
const int MAX_SIZE = 1000 ;
int sequence [MAX_SIZE];
int n;
int longest_increasing_subsequence_greedy ( int idx ) {
int current = sequence [ idx ];
int len = 1 ;
for ( int i = idx + 1 ; i < n; i++) {
if ( sequence [i] > current ) {
len ++;
current = sequence [i];
}
}
return len ;
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> sequence [i];
}
int max_len_greedy = 0 ;
for ( int i = 0 ; i < n; i++) {
max_len_greedy = max ( max_len_greedy , longest_increasing_subsequence_greedy (i));
}
cout << "Lungimea maxima ( Greedy ): " << max_len_greedy << endl ;
return 0 ;
}

Ambele programe primesc ca input numărul de elemente din șir și apoi elementele șirului. Programele vor returna lungimea maximă a unui subșir crescător.
Rețineți că metoda greedy poate să nu ofere întotdeauna soluția optimă, deoarece alege cea mai bună opțiune locală la fiecare pas, fără a lua în considerare impactul pe termen lung al deciziei. Metoda programării dinamice garantează găsirea soluției optime, dar poate necesita mai mult timp și memorie pentru a fi executată.