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