Ce vei învăța astăzi?
După această lecție vei rezolva problema monedelor: să plătești o sumă S cu numărul minim de monede, folosind strategia greedy.
Enunțul problemei
Cerință: Avem la dispoziție monede de valori 1, 2, 5, 10, 50, 100 (în lei). Trebuie să plătim o sumă S folosind cât mai puține monede.
Strategia greedy: la fiecare pas alegem cea mai mare monedă care încape (adică a cărei valoare nu depășește restul curent) în restul rămas. Repetăm până când restul devine 0.
Analogie: plata la magazin
Vrei să plătești 126 de lei folosind cât mai puține bancnote și monede. Alegi, pe rând, cea mai mare valoare care nu depășește suma rămasă: 100, apoi 10, 10, 5, 1. Astfel folosești doar 5 „piese", în loc să dai 126 de monede de 1 leu.
Urmărim algoritmul pas cu pas
S = 126, monede: 100, 50, 10, 5, 2, 1
numărăm monedeleObservă: 126 = 100 + 10 + 10 + 5 + 1, deci numărul minim de monede este 5. Fiecare alegere locală (cea mai mare monedă) contribuie la soluția globală optimă.
Programul complet în C++
Folosim un tablou cu valorile monedelor, în ordine descrescătoare. Pentru fiecare monedă, cât timp încape în rest, o scădem și numărăm.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int monede[] = {100, 50, 10, 5, 2, 1};
int nr = 0;
for (int i = 0; i < 6; i++) {
while (n >= monede[i]) {
n -= monede[i];
nr++;
}
}
cout << nr << endl;
return 0;
}
Ce învățăm: while (n >= monede[i]) ia toate monedele de valoarea curentă; strategia greedy funcționează optim pentru acest sistem „canonic" de monede.
Exercițiu de completare
Completează descrierea strategiei greedy pentru monede:
La fiecare pas alegem cea mai ______ monedă care încape în rest. Numărul de ______ folosite devine astfel ______. Algoritmul se oprește când restul devine ______.
Bancă de cuvinte:
Exercițiu de completare: codul
Completează descrierea programului:
Folosim un tablou ______ cu valorile 100, 50, 10, 5, 2, 1. Cât timp n este mai mare sau egal cu moneda curentă, ______ moneda din n și ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - problema monedelor:
1. La plata restului cu număr minim de monede, alegem întotdeauna:
2. Pentru S = 16 și monede {1, 5, 10}, numărul minim de monede este:
3. Greedy dă întotdeauna numărul minim de monede?
while, nu if — cu if se ia o singură monedă din fiecare valoare și restul rămâne neplătit; eroare frecvent depistată la barem.Aprofundare
Sisteme canonice de monede: strategia greedy „cea mai mare monedă care încape" dă numărul minim de monede doar pentru sisteme canonice, în care fiecare monedă este un multiplu „comod" al celei mai mici (100 = 2·50 = 10·10 etc.). Pentru alte sisteme, cum ar fi monedele 1, 3, 4, greedy poate da un număr mai mare decât optimul: restul 6 se plătește cu 4 + 1 + 1 (trei monede), dar soluția optimă este 3 + 3 (două monede).
Ce se întâmplă dacă restul nu se poate plăti exact? În sistemul canonic din problemă, orice rest se plătește exact, pentru că există moneda de 1. În alte probleme (de exemplu monede 5 și 7), există sume care nu pot fi plătite exact; atunci algoritmul trebuie să semnaleze imposibilitatea, de exemplu afișând un mesaj când, la final, restul nu a ajuns la 0.
Varianta cu numărare directă: pentru că 100 = 2·50, o variantă mai rapidă calculează direct nr = n / moneda și n %= moneda, fără bucla while. Rezultatul este identic pentru sistemele canonice, iar codul devine mai scurt; totuși, la BAC se acceptă orice variantă corectă.
Și afișarea monedelor folosite: dacă cerința cere nu doar numărul, ci și monedele efectiv folosite, reținem în fiecare iterație câte monede din valoarea curentă am luat: nrMonede = n / monede[i] și afișăm nrMonede de monede[i].
Exemplu din viața reală: un automat de bilete care trebuie să dea rest 88 de lei alege întotdeauna bancnota sau moneda cu cea mai mare valoare care încape, pentru a minimiza numărul de piese date. Casieriile din magazine folosesc instinctiv aceeași strategie: 88 lei = 50 + 10 + 10 + 10 + 5 + 2 + 1. Faptul că algoritmul coincid cu comportamentul uman natural explică de ce pare „evident", dar corectitudinea lui trebuie oricum demonstrată.
PbInfo - Restul cu monede
Enunț:
Cerință: Se dă suma S. Să se afișeze numărul minim de monede cu care poate fi plătită suma S, folosind monede de valori 1, 5, 10, 50, 100 (strategie greedy).
Date de intrare:
Programul citește de la tastatură numărul natural S.
Date de ieșire:
Programul va afișa numărul minim de monede.
Restricții și precizări:
1 ≤ S ≤ 100000; monedele disponibile au valorile 1, 5, 10, 50, 100.
Exemplu:
Intrare:
126
Ieșire:
5
Cum gândim soluția:
- Definim tabloul
monedecu valorile în ordine descrescătoare - Pentru fiecare monedă, cât timp încape în S, o scădem și numărăm
- Afișăm numărul total de monede
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int monede[] = {100, 50, 10, 5, 1};
int nr = 0;
for (int i = 0; i < 5; i++) {
while (n >= monede[i]) {
n -= monede[i];
nr++;
}
}
cout << nr << endl;
return 0;
}
Ce învățăm: 126 = 100 + 10 + 10 + 5 + 1, deci 5 monede. Tabloul este parcurs de la valoarea cea mai mare la cea mai mică.
PbInfo - Plata
Enunț:
Cerință: Un client plătește suma S cu bancnote de valori 1, 5, 10, 50, 100. Să se afișeze numărul minim de bancnote necesare pentru a plăti exact suma S.
Date de intrare:
Programul citește de la tastatură numărul natural S.
Date de ieșire:
Programul va afișa numărul minim de bancnote.
Restricții și precizări:
1 ≤ S ≤ 1000000; se folosește metoda Greedy.
Exemplu:
Intrare:
188
Ieșire:
9
Cum gândim soluția:
- Luăm cât mai multe bancnote de 100, apoi 50, 10, 5, 1
- Numărăm bancnotele folosite
- Afișăm numărul minim
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int bancnote[] = {100, 50, 10, 5, 1};
int nr = 0;
for (int i = 0; i < 5; i++) {
while (n >= bancnote[i]) {
n -= bancnote[i];
nr++;
}
}
cout << nr << endl;
return 0;
}
Ce învățăm: 188 = 100 + 50 + 10 + 10 + 10 + 5 + 1 + 1 + 1, deci 9 bancnote. Problema este identică cu restul cu monede, schimbă doar denumirile.
Exercițiul Practic: variante ale problemei monedelor
Sarcini de lucru
Rezolvă sarcinile de mai jos pentru a aprofunda problema monedelor
Sarcina 1: Câte monede din fiecare tip
Cerință: Se citește suma S. Afișează, pentru fiecare tip de monedă folosit (100, 50, 10, 5, 2, 1), valoarea și numărul de monede, doar dacă numărul este mai mare decât 0.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int monede[] = {100, 50, 10, 5, 2, 1};
for (int i = 0; i < 6; i++) {
int cate = 0;
while (n >= monede[i]) {
n -= monede[i];
cate++;
}
if (cate > 0) {
cout << monede[i] << ": " << cate << endl;
}
}
return 0;
}
Verifică: pentru S = 126, afișăm 100: 1, 10: 2, 5: 1, 1: 1. Numărăm separat fiecare tip în bucla interioară.
Sarcina 2: Rest cu alt set de monede
Cerință: Se citește suma S. Calculează și afișează numărul minim de monede folosind setul de monede {50, 20, 10, 5, 2, 1}.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int monede[] = {50, 20, 10, 5, 2, 1};
int nr = 0;
for (int i = 0; i < 6; i++) {
while (n >= monede[i]) {
n -= monede[i];
nr++;
}
}
cout << nr << endl;
return 0;
}
Verifică: pentru S = 37, folosim 20 + 10 + 5 + 2 = 4 monede. Schimbarea setului de monede înseamnă doar modificarea tabloului monede.
Scrie pe caiet - Problema monedelor (restul minim)
Titlul lecției
- Ora 6: Problema monedelor (restul minim)
Definiția lecției
Problema cere să plătim o sumă S cu numărul minim de monede dintr-un sistem dat (de exemplu 1, 2, 5, 10, 50, 100 de lei). Strategia greedy alege la fiecare pas cea mai mare monedă care încape în restul rămas, fără să reconsidere decizia, până când restul devine 0. Pentru sistemele canonice, această alegere locală garantează optimul global: o monedă mare poate fi înlocuită de mai multe monede mici, niciodată invers. Implementarea folosește un tablou de monede ordonat descrescător și, pentru fiecare valoare, o buclă while care scade și numără (sau împărțiri întregi: nr += n / monede[i]; n %= monede[i];). De exemplu, suma 88 de lei se plătește cu 7 monede: 50, 10, 10, 10, 5, 2, 1.
Definiții esențiale
- Problema restului: se dă suma S și un sistem de monede; se cere numărul minim de monede cu care poate fi plătită suma.
- Strategia greedy: la fiecare pas se alege cea mai mare monedă care încape în restul curent; decizia nu se reconsideră.
- Sistem canonic: sistemul de monede (100, 50, 10, 5, 2, 1) pentru care strategia greedy dă întotdeauna numărul minim de monede.
- Corectitudine: alegerea locală este justificată de faptul că orice monedă mare poate fi înlocuită de mai multe monede mici, niciodată invers; de aceea greedy-ul este optim la acest sistem.
Algoritmul cheie - pseudocod
- Ordonează monedele descrescător.
- Pentru fiecare monedă, cât timp încape în rest: scade-o și numără.
- Afișează numărul total de monede.
Algoritmul cheie - cod C++
int monede[] = {100, 50, 10, 5, 2, 1};for (int i = 0; i < 6; i++) { while (n >= monede[i]) { n -= monede[i]; nr++; } }- Afișează
nr.
Greșeli comune de evitat
- Monedele neordonate descrescător: greedy-ul nu mai alege cea mai mare monedă.
- Folosirea lui
ifîn loc dewhile: se ia o singură monedă din fiecare valoare. - Scăderea din variabila greșită (de exemplu din
nrîn loc den). - Presupunerea că greedy dă optimul la orice sistem de monede: trebuie verificată canonicitatea sistemului.
Sfaturi practice și trucuri
- Pentru sistemele canonice poți folosi și varianta directă:
nr += n / monede[i]; n %= monede[i]; - Verifică pe exemple manuale: 88 → 7 monede, 1 → 1 monedă, 100 → 1 monedă.
- Dacă cerința cere monedele folosite, reține și afișează cantitatea din fiecare valoare.
- La oral, justifică: „cea mai mare monedă lasă cel mai mic rest, deci minimizează numărul de monede".
Exemplu practic
Un elev plătește un caiet de 17 lei folosind număr minim de monede din sistemul 1, 2, 5, 10, 50, 100. Alege 10, apoi 5, apoi 2, adică 3 monede. Alegerea „cea mai mare monedă care încape", repetată până la rest 0, este exact bucla de mai jos:
int monede[] = {100, 50, 10, 5, 2, 1};
int n, nr = 0;
cin >> n;
for (int i = 0; i < 6; i++) {
while (n >= monede[i]) {
n -= monede[i];
nr++;
}
}
cout << nr << endl;