online: 25; azi: 2076; total: 181498 Manual clasa a xi a - Tehnici de programare - Metoda greedy

Manual clasa a Xi a

Tehnici de programare

Metoda greedy

La un cabinet medical, în sala de aşteptare , se găsesc n pacienți. Timpul necesar pentru consultarea unui pacient i este t;. Cunoscând numărul de pacienţi n şi timpul necesar pentru fiecare consultație î;, scrieţi un program care să afişeze ordinea de tratare a pacienţilor , astfel încât timpul total de aşteptare al pacienților să fie minim. Indicaţie . Deoarece timpul de aşteptare al unui pacient este egal cu suma timpilor de consultație ai pacienţilor tratați înaintea sa, ordonarea pacienților după criteriul candidatului optim inseamna ordonarea crescatoare dupa timpul de consultatie . Demonstrati ca solutia obtinuta este solutia optima
Pentru a minimiza timpul total de așteptare al pacienților, vom utiliza metoda greedy și vom sorta pacienții în ordinea crescătoare a timpilor de consultare. Acest lucru asigură că pacienții cu consultații mai rapide sunt tratați înaintea celor cu consultații mai lungi, reducând timpul de așteptare pentru toți pacienții.
# include < iostream >
struct Patient {
int id ;
int consultationTime ;
};
void selectionSort ( Patient patients [], int n) {
for ( int i = 0 ; i < n - 1 ; i++) {
int min_index = i;
for ( int j = i + 1 ; j < n; j++) {
if ( patients [j]. consultationTime < patients [ min_index ]. consultationTime ) {
min_index = j;
}
}
if ( min_index != i) {
Patient temp = patients [i];
patients [i] = patients [ min_index ];
patients [ min_index ] = temp ;
}
}
}
int main () {
int n;
std :: cout << " Introduceti numarul de pacienti (n): " ;
std ::cin >> n;
Patient patients [n];
std :: cout << " Introduceti timpul de consultatie pentru fiecare pacient (t1, t2, ..., tn ): " ;
for ( int i = 0 ; i < n; i++) {
patients [i]. id = i + 1 ;
std ::cin >> patients [i]. consultationTime ;
}
selectionSort ( patients , n);
std :: cout << "Ordinea de tratare a pacientilor este: " ;
for ( int i = 0 ; i < n; i++) {
std :: cout << patients [i]. id << " " ;
}
std :: cout << std :: endl ;
return 0 ;
}

Acest program citește numărul de pacienți n și timpul de consultare pentru fiecare pacient. Apoi, folosește funcția selectionSort () pentru a sorta pacienții în ordinea crescătoare a timpilor de consultare. La final, programul afișează ordinea de tratare a pacienților.