Probleme Rezolvate

Justificai criteriul prioritaii de alegere pentru cazul in care coeficienii sunt pozitivi si in multimea a nu exista decat numere negative

Ntr o fabrica s a automatizat procesul de producie si la sfarsitul zilei de munca

Un automobilist porneste dintr

La un cabinet medical

Refaceti programul astfel incat sa se determine valoarea minima a expresiei

Fiind data o mulime a cu n numere reale

Justificati criteriul prioritatii de alegere pentru cazul in care coeficientii sunt negativi si in mulimea a nu exista decat numere pozitive

Un turist trebuie sa strabata un traseu de munte

Ntr un camping exista k casute care pot fi inchiriate 365 de zile din an

Intr un depozit al monetariei statului sosesc n saci cu monede

Fiind date multimea de numere reale a

Manual clasa a Xi a

Tehnici de programare

Metoda greedy

Un automobilist porneşte dintr-un oraş A şi trebuie să ajungă în oraşul B. Rezervorul autoturismului, dacă este plin, îi permite să parcurgă n kilometri. Pe hartă sunt trecute m staţii de alimentare şi distanţele dintre ele. Automobilistul doreşte să oprească la cât mai puţine stații pentru alimentarea autoturismului. Scrieţi un program care să determine stațiile de benzină la care trebuie să se oprească pentru alimentare.
Pentru a rezolva această problemă în C++ putem folosi un algoritm greedy . În acest caz, trebuie să ne asigurăm întotdeauna că mergem cât mai departe posibil fără a depăși capacitatea rezervorului de combustibil. Următorul program C++ implementează această idee:

# include < iostream >
const int MAX_STATIONS = 100 ;
int main () {
int n, m, distance [MAX_STATIONS + 2 ];
std :: cout << " Introduceti numarul de kilometri pe care ii poate parcurge automobilul cu rezervorul plin: " ;
std ::cin >> n;
std :: cout << " Introduceti numarul de statii de alimentare: " ;
std ::cin >> m;
distance [ 0 ] = 0 ;
for ( int i = 1 ; i <= m; i++) {
std :: cout << " Introduceti distanta de la orasul A pana la statia de alimentare " << i << ": " ;
std ::cin >> distance [i];
}
distance [m + 1 ] = distance [m] + n;
int station_index = 0 ;
int prev_station_index = 0 ;
int stops = 0 ;
while ( station_index <= m) {
if ( distance [ station_index + 1 ] - distance [ prev_station_index ] <= n) {
station_index ++;
} else {
if ( station_index == prev_station_index ) {
std :: cout << "Nu se poate ajunge la destinatie ." << std :: endl ;
return 0 ;
}
std :: cout << "Oprire la statia de alimentare " << station_index << std :: endl ;
stops ++;
prev_station_index = station_index ;
}
}
std :: cout << " Numarul de opriri: " << stops << std :: endl ;
return 0 ;
}

Acest program citește n , numărul de kilometri pe care îi poate parcurge automobilul cu rezervorul plin, și m , numărul de stații de alimentare. Apoi, pentru fiecare stație, citește distanța până la ea de la orașul A. Algoritmul greedy în sine este implementat în bucla while .
Acest program nu folosește librăriile vector și algorithm , în schimb, folosește un array static de dimensiunea maximă a stațiilor de alimentare, MAX_STATIONS . Dacă doriți să puteți utiliza un număr mai mare de stații de alimentare, modificați valoarea constantă MAX_STATIONS .