online: 1; azi: 491; total: 67803 Manual clasa a xi a - Tehnici de programare - Microproiecte

Manual clasa a Xi a

Tehnici de programare

Microproiecte

Se dau n piese de domino, fiecare piesă i fiind descrisă prin perechi de două numere ( x;y ;). Să se găsească o secvență de lungime maximă de piese în care oricare două piese alăturate au înscrise la capetele cu care se învecinează acelaşi număr.
Pentru această problemă, se pot utiliza mai mulți algoritmi pentru a găsi secvența de lungime maximă. Iată câteva abordări posibile:
Dintre aceste abordări, cea bazată pe programare dinamică este probabil cea mai eficientă în termeni de timp și spațiu. Alte abordări pot fi aplicabile în funcție de restricțiile specifice ale problemei și dimensiunea setului de piese de domino.
# include < iostream >
using namespace std ;
int n;
int pieces [ 100 ][ 2 ];
bool used [ 100 ];
int maxLength = 0 ;
int currentLength = 0 ;
bool canJoin ( int piece1, int piece2) {
return pieces [piece1][ 1 ] == pieces [piece2][ 0 ];
}
void findLongestSequence ( int lastPiece ) {
bool found = false ;
for ( int i = 0 ; i < n; i++) {
if (! used [i] && canJoin ( lastPiece , i)) {
used [i] = true ;
currentLength ++;
findLongestSequence (i);
used [i] = false ;
currentLength --;
found = true ;
}
}
if (! found ) {
maxLength = max ( maxLength , currentLength );
}
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> pieces [i][ 0 ] >> pieces [i][ 1 ];
}
for ( int i = 0 ; i < n; i++) {
used [i] = true ;
currentLength = 1 ;
findLongestSequence (i);
used [i] = false ;
}
cout << "Lungimea maxima a secventei : " << maxLength << endl ;
return 0 ;
}
Acest cod utilizează backtracking pentru a găsi lungimea maximă a secvenței de piese de domino care se pot potrivi. Introduceți numărul de piese și apoi perechile de numere pentru fiecare piesă de domino. Programul va afișa lungimea maximă a secvenței.
Pentru a introduce datele de intrare în acest program, urmați pașii de mai jos:
Iată un exemplu de date de intrare:
6
1 2
2 3
3 4
4 1
1 3
2 4
În acest exemplu, avem 6 piese de domino, iar perechile de numere pentru fiecare piesă sunt (1, 2), (2, 3), (3, 4), (4, 1), (1, 3) și (2, 4).
O implementare în C++ a algoritmului de programare dinamic a:
# include < iostream >
using namespace std ;
int n;
int pieces [ 100 ][ 2 ];
int dp [ 100 ][ 100 ];
int findLongestSequenceDP () {
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
if ( pieces [i][ 1 ] == pieces [j][ 0 ]) {
dp [i][j] = 2 ;
} else {
dp [i][j] = 0 ;
}
}
}
int maxLength = 0 ;
for ( int k = 0 ; k < n; k++) {
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
if ( dp [i][k] > 0 && dp [k][j] > 0 ) {
dp [i][j] = max ( dp [i][j], dp [i][k] + dp [k][j] - 1 );
maxLength = max ( maxLength , dp [i][j]);
}
}
}
}
return maxLength ;
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> pieces [i][ 0 ] >> pieces [i][ 1 ];
}
int maxLength = findLongestSequenceDP ();
cout << "Lungimea maxima a secventei : " << maxLength << endl ;
return 0 ;
}
Acest cod utilizează programarea dinamică pentru a găsi lungimea maximă a secvenței de piese de domino care se pot potrivi. Introduceți numărul de piese și apoi perechile de numere pentru fiecare piesă de domino. Programul va afișa lungimea maximă a secvenței.
I ată o implementare în C ++ a algoritmului bazat pe graf:
# include < iostream >
# include < queue >
using namespace std ;
int n;
int pieces [ 100 ][ 2 ];
bool adjMatrix [ 100 ][ 100 ];
bool visited [ 100 ];
int maxLength = 0 ;
void findLongestSequenceDFS ( int node , int currentLength ) {
visited [ node ] = true ;
maxLength = max ( maxLength , currentLength );
for ( int i = 0 ; i < n; i++) {
if ( adjMatrix [ node ][i] && ! visited [i]) {
findLongestSequenceDFS (i, currentLength + 1 );
}
}
visited [ node ] = false ;
}
int main () {
cin >> n;
for ( int i = 0 ; i < n; i++) {
cin >> pieces [i][ 0 ] >> pieces [i][ 1 ];
}
for ( int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < n; j++) {
adjMatrix [i][j] = ( pieces [i][ 1 ] == pieces [j][ 0 ]);
}
}
for ( int i = 0 ; i < n; i++) {
findLongestSequenceDFS (i, 1 );
}
cout << "Lungimea maxima a secventei : " << maxLength << endl ;
return 0 ;
}

Acest cod utilizează graful și Depth-First Search (DFS) pentru a găsi lungimea maximă a secvenței de piese de domino care se pot potrivi. Introduceți numărul de piese și apoi perechile de numere pentru fiecare piesă de domino. Programul va afișa lungimea maximă a secvenței.
Rețineți că această soluție nu este cea mai eficientă și poate deveni lentă pentru un număr mare de piese de domino. Programarea dinamică este o soluție mai eficientă pentru această problemă.