Test pentru proba practică

Secvența A vizează competențele specifice 2.1, 2.2 și 2.3, pe conținutul Metode de programare — Metoda de programare Greedy.

TEST — probă practică

Disciplina: Informatică · Clasa: a XI-a, filiera teoretică, profil real, specializarea matematică-informatică

Unitatea de învățare: Metode de programare · Conținutul: Metoda de programare Greedy

Timpul de lucru: 50 de minute · Toate subiectele sunt obligatorii. Se acordă 10 puncte din oficiu.

Programele se scriu în limbajul C++ și se salvează în folderul indicat de profesor, cu numele cerut la fiecare item. Fișierele de intrare se află deja în acest folder.

Itemul 1 — 25 de puncte

Într-un depozit se află n produse (n ≤ 100). Pentru fiecare produs se cunosc denumirea, cantitatea disponibilă, în kilograme, și câștigul obținut prin vânzarea întregii cantități. Un transportator dispune de un vehicul care poate duce cel mult Gmax kilograme. Produsele pot fi transportate și parțial; în acest caz, câștigul este proporțional cu cantitatea încărcată.

Fișierul rucsac.in conține pe prima linie valorile Gmax și n, separate printr-un spațiu, iar pe fiecare dintre următoarele n linii denumirea unui produs, cantitatea și câștigul, separate prin câte un spațiu.

a) Creați fișierul text analiza.txt, în care precizați datele de intrare, datele de ieșire și criteriul de selecție pe care îl folosiți pentru a obține câștigul maxim. (8 puncte)

b) Scrieți programul item1.cpp, care citește datele din fișierul rucsac.in și afișează pe ecran câștigul maxim, cu două zecimale, și denumirile produselor încărcate, în ordinea în care au fost alese, precizând pentru ultimul dintre ele cantitatea încărcată, dacă a fost încărcat parțial. (17 puncte)

Itemul 2 — 35 de puncte

La un festival se desfășoară n spectacole (n ≤ 100), fiecare cu o oră de început și o oră de sfârșit, numere naturale din intervalul [0, 24]. Un spectator dorește să vizioneze integral un număr maxim de spectacole. Un spectacol nou poate începe numai după ce s-a terminat cel vizionat anterior.

Fișierul spectacole.in conține pe prima linie numărul n, iar pe fiecare dintre următoarele n linii denumirea unui spectacol, ora de început și ora de sfârșit, separate prin câte un spațiu.

Scrieți programul item2.cpp, care citește datele din fișier, determină prin metoda Greedy o mulțime de cardinal maxim de spectacole care pot fi vizionate și afișează pe ecran numărul lor, apoi denumirea, ora de început și ora de sfârșit ale fiecăruia, în ordine cronologică. Ordonarea spectacolelor se face într-un subprogram distinct.

Itemul 3 — 30 de puncte

Se cere plata unei sume S cu un număr minim de bancnote, dintr-un sistem de cupiuri dat. Se consideră că din fiecare cupiură există un număr nelimitat de bancnote.

a) Scrieți programul item3a.cpp, care rezolvă problema prin metoda Greedy, alegând la fiecare pas cupiura de valoare cea mai mare care nu depășește suma rămasă de plătit. (8 puncte)

b) Scrieți programul item3b.cpp, care determină numărul minim de bancnote încercând toate posibilitățile de plată. (10 puncte)

c) Rulați ambele programe pe cele trei seturi de date de mai jos, completați tabelul din fișierul comparatie.txt și formulați, în același fișier, o concluzie privind situațiile în care metoda Greedy conduce la soluția optimă. (12 puncte)

BAREM DE EVALUARE ȘI DE NOTARE

• Se punctează orice modalitate de rezolvare corectă a cerințelor.
• Nu se acordă fracțiuni de punct.
• Se acordă 10 puncte din oficiu. Nota finală se calculează prin împărțirea la zece a punctajului total acordat.

Itemul 1 — 25 de puncte

Răspunsul așteptat la subpunctul a). Datele de intrare: Gmax, n și, pentru fiecare produs, denumirea, cantitatea și câștigul. Datele de ieșire: câștigul maxim și lista produselor încărcate. Criteriul de selecție: se încarcă mai întâi produsele cu câștigul pe kilogram cel mai mare, adică cele pentru care raportul dintre câștig și cantitate este maxim.

Etapele necesare obținerii răspunsului la subpunctul b). Citirea datelor din fișier și calcularea, pentru fiecare produs, a câștigului pe kilogram; ordonarea descrescătoare a produselor după această valoare; parcurgerea produselor în ordinea obținută și încărcarea integrală a fiecăruia cât timp cantitatea lui nu depășește capacitatea rămasă, cu scăderea cantității încărcate din capacitatea rămasă și adunarea câștigului la total; încărcarea parțială a primului produs care nu mai încape integral, cu adăugarea câștigului proporțional cu cantitatea încărcată; afișarea rezultatelor.

Pe fișierul de intrare dat, cu Gmax = 50 și produsele de câte 10 kg / 60 lei, 20 kg / 100 lei și 30 kg / 120 lei, câștigul maxim este 240,00, obținut prin încărcarea integrală a primelor două produse și a 20 de kilograme din al treilea.