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

Rezolvaţi problema turistului care trebuie să găsească un traseu de munte în care să urce cat mai puţin , folosind metoda programării dinamice şi metoda greedy .

# include < iostream >
# include < climits >
# include < cstring >
using namespace std ;
const int MAX_ROWS = 100 ;
const int MAX_COLS = 100 ;
int matrix [MAX_ROWS][MAX_COLS];
int dp [MAX_ROWS][MAX_COLS];
int rows , cols ;
int dx[] = { -1 , -1 , 0 , 1 , 1 }; // Nord-Vest, Nord, Est, Nord-Est, Nord
int dy [] = { -1 , 0 , 1 , 0 , 1 };
bool is_valid ( int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols ;
}
int min_climb ( int x, int y) {
if (x == 0 ) {
return 0 ;
}
if ( dp [x][y] != -1 ) {
return dp [x][y];
}
int min_height = INT_MAX;
for ( int i = 0 ; i < 5 ; i++) {
int nx = x + dx[i];
int ny = y + dy [i];
if ( is_valid ( nx , ny )) {
min_height = min ( min_height , min_climb ( nx , ny ));
}
}
dp [x][y] = min_height + matrix [x][y];
return dp [x][y];
}
int main () {
cin >> rows >> cols ;
for ( int i = 0 ; i < rows ; i++) {
for ( int j = 0 ; j < cols ; j++) {
cin >> matrix [i][j];
}
}
memset ( dp , -1 , sizeof ( dp ));
int min_climb_total = INT_MAX;
for ( int i = 0 ; i < cols ; i++) {
min_climb_total = min ( min_climb_total , min_climb ( rows - 1 , i));
}
cout << " Climb minim: " << min_climb_total << endl ;
return 0 ;
}
# include < iostream >
# include < climits >
using namespace std ;
const int MAX_ROWS = 100 ;
const int MAX_COLS = 100 ;
int matrix [MAX_ROWS][MAX_COLS];
int rows , cols ;
int dx[] = { -1 , -1 , 0 , 1 , 1 }; // Nord-Vest, Nord, Est, Nord-Est, Nord
int dy [] = { -1 , 0 , 1 , 0 , 1 };
bool is_valid ( int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols ;
}
int greedy_min_climb ( int x, int y) {
if (x == 0 ) {
return 0 ;
}
int min_height = INT_MAX;
int min_idx = -1 ;
for ( int i = 0 ; i < 5 ; i++) {
int nx = x + dx[i];
int ny = y + dy [i];
if ( is_valid ( nx , ny ) && matrix [ nx ][ ny ] < min_height ) {
min_height = matrix [ nx ][ ny ];
min_idx = i;
}
}
return min_height + greedy_min_climb (x + dx[ min_idx ], y + dy [ min_idx ]);
}
int main () {
cin >> rows >> cols ;
for ( int i = 0 ; i < rows ; i++) {
for ( int j = 0 ; j < cols ; j++) {
cin >> matrix [i][j];
}
}
int min_climb_total = INT_MAX;
for ( int i = 0 ; i < cols ; i++) {
min_climb_total = min ( min_climb_total , greedy_min_climb ( rows - 1 , i));
}
cout << " Climb minim: " << min_climb_total << endl ;
return 0 ;
}

Ambele programe primesc ca input numărul de rânduri și coloane, iar apoi valorile înălțimilor pentru fiecare celulă din matrice. Programele vor returna înălțimea minimă pe care turistul trebuie să o urce pentru a parcurge traseul.
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ă.
E xemplu de date de intrare pentru ambele programe:
5 5
9 2 7 6 5
8 1 6 2 4
7 2 5 1 3
6 1 4 2 2
5 0 3 1 1
Acest exemplu reprezintă o hartă c u 5 rânduri și 5 coloane. Elementele matricei reprezintă înălțimile subzonelor.
Pentru a testa programul, copiați și inserați datele de intrare în terminal după ce ați rulat programul compilat. Rezultatul va fi înălțimea minimă pe care turistul trebuie să o urce pentru a parcurge traseul.