Probleme Rezolvate

Rezolvai problema acoperirii tablei de sah de dimensiunea nxn cu un cal care porneste din patratul de c

Rezolvai problema determinarii sumei maxime intr

Pe o tabla de sah de dimensiunea nxn un cal porneste din patratul de coordonate

Rezolvai problema gasirii unui traseu pentru a iesi din labirintul de dimensiunea nxm

Rezolvai problema plaii unei sume cu bancnote cu valori date

Rezolvai problema turistului care trebuie sa gaseasca un traseu de munte in care sa urce cat mai puin

Rezolvai problema determinarii unui subsir crescator de lungime maxima folosind metoda greedy si metoda programarii dinamice

Se dau n piese de domino

Rezolvai problema costruirii tevii de lungime l din bucai de teava de lungimi a

Se dau n paralelipipede avand fiecare dimensiunile ai

Pe o tabla de sah de dimensiunea nxn un cal porneste din patratul de coordonate

Manual clasa a Xi a

Tehnici de programare

Microproiecte

Pe o tablă de şah de dimensiunea nxn un cal porneşte din pătratul de coordonate (x4,y4) şi trebuie să ajungă în pătratul de coordonate (x2,y2). Să se găsească traseul de lungime minimă.
În această problemă, trebuie să găsești traseul de lungime minimă pentru un cal care se deplasează pe o tablă de șah de dimensiunea nxn . Am creat două soluții pentru această problemă, una care folosește backtracking și alta care folosește algoritmul Breadth-First Search (BFS), deoarece programarea dinamică și algoritmul greedy nu sunt potrivite pentru această problemă specifică.
Algoritmul de backtracking nu este optim pentru a rezolva această problemă, deoarece poate duce la o complexitate exponențială. În cazul dat, este recomandat să folosiți algoritmul de căutare în lățime ( Breadth-First Search - BFS) pentru a găsi traseul de lungime minimă.

# include < iostream >
# include < queue >
using namespace std ;
struct Position {
int x, y, step;
};
int dx[] = { -2 , -1 , 1 , 2 , 2 , 1 , -1 , -2 };
int dy [] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 };
bool valid ( int x, int y, int n) {
return x >= 0 && x < n && y >= 0 && y < n;
}
int minPathLengthBFS ( int n, int x1, int y1, int x2, int y2) {
queue < Position > q;
q. push ({x1, y1, 0 });
while (! q. empty ()) {
Position current = q. front ();
q. pop ();
if ( current.x == x2 && current.y == y2) {
return current.step ;
}
for ( int i = 0 ; i < 8 ; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy [i];
if ( valid ( newX , newY , n)) {
q. push ({ newX , newY , current.step + 1 });
}
}
}
return -1 ;
}
int main () {
int n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
int result = minPathLengthBFS (n, x1, y1, x2, y2);
cout << "Minimul folosind BFS: " << result << endl ;
return 0 ;
}
Exemplu de date de intrare:
8
1 3
6 2
Prezint si metoda backtraking , metoda care in functie de mediu de dezvoltare si datele introduse, poate sa intre in bucla infinita :
# include < iostream >
using namespace std ;
int dx[] = { -2 , -1 , 1 , 2 , 2 , 1 , -1 , -2 };
int dy [] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 };
bool valid ( int x, int y, int n) {
return x >= 0 && x < n && y >= 0 && y < n;
}
int minPathLengthBacktracking ( int n, int x1, int y1, int x2, int y2, int step) {
if (x1 == x2 && y1 == y2) {
return step;
}
int minLength = INT_MAX;
for ( int i = 0 ; i < 8 ; i++) {
int newX = x1 + dx[i];
int newY = y1 + dy [i];
if ( valid ( newX , newY , n)) {
minLength = min ( minLength , minPathLengthBacktracking (n, newX , newY , x2, y2, step + 1 ));
}
}
return minLength ;
}
int main () {
int n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
int result = minPathLengthBacktracking (n, x1, y1, x2, y2, 0 );
cout << "Minimul folosind backtracking : " << result << endl ;
return 0 ;
}