Scor maxim pentru setarea A - 2
Punctajul maxim pentru sarcina B - 4
Elemente de conținut Verificat:
- abilitatea de a crea programe personalizate (30-50 rânduri) pentru a rezolva problemele de complexitate medie.
elemente de conținut sunt verificate pentru examen:
- principalele etape ale dezvoltării programului. sarcini distribuiri în subactivități.
sarcina 27
Vi se oferă două locuri de muncă cu condiții similare: sarcina A și B. sarcina Puteți rezolva ambele sarcini, sau unul din propria lor alegere. Setarea B este mai complex, soluția este estimată mai sus. Nota finală este estimarea maximă pentru locuri de muncă A și B.
Setarea A. Există un set de date constând din 6 perechi de numere întregi pozitive. Acesta ar trebui să selecteze exact de una din fiecare pereche de numere astfel încât suma tuturor numerelor selectate nu sunt divizibile cu 3 și, astfel, a fost posibil. Dacă obțineți suma necesară nu este posibil, ca răspuns ar trebui să se acorde o 0.
Scrieti un program pentru a rezolva această problemă. În acest exemplu de realizare, de referință este evaluat numai programul corect, timpul de funcționare și cantitatea de memorie utilizată sunt irelevante.
Punctajul maxim pentru o corecta programmu- 2 puncte.
Sarcina B. Există un set de date constând din perechi de numere întregi pozitive. Acesta ar trebui să selecteze exact de una din fiecare pereche de numere astfel încât suma tuturor numerelor selectate nu sunt divizibile cu 3 și, astfel, a fost posibil. Dacă obțineți suma necesară nu este posibil, ca răspuns ar trebui să se acorde o 0.
Scrieti un program pentru a rezolva această problemă.
Încercați să facă programul eficient în timp și utilizarea memoriei (sau cel puțin una dintre aceste caracteristici).
Programul este considerat a fi eficient în momentul în care funcționarea programului proporțional cu numărul de perechi de numere și anume N. N crește k ori în timp ce programul ar trebui să fie majorat cu nu mai mult de k ori.
Programul este considerat a fi eficient pentru memoria dacă dimensiunea memoriei utilizată în program pentru a stoca date, independent de numărul N și nu mai mult de 1 kilobyte.
Punctajul maxim pentru programul corect, eficient în timp și memorie - 4 puncte.
Punctajul maxim pentru programul corect, eficient în timp, dar ineficient din memorie - 3 puncte.
Ca și în realizarea A și B de realizare în program trebuie să fie tipărit un număr - suma maximă posibilă corespunzătoare condițiilor problemei (sau 0 dacă această sumă nu poate fi obținută).
REMINDER! Nu uitați să specificați care se aplică sarcina fiecare dintre programele prezentate de tine.
Înainte de textul programului descrie pe scurt algoritmul dvs. soluție, selectați limbajul de programare utilizat și versiunea acestuia (de exemplu, Free Pascal 2.6.4).
intrare
Pentru varianta Un program este alimentat la intrarea din cele șase rânduri, fiecare dintre acestea cuprinzând două numere naturale care nu depășește 10.000.
Exemplu de intrare la varianta A:
03 ianuarie
05 decembrie
09 iunie
04 mai
03 martie
01 ianuarie
Pentru varianta B, la intrarea programului în primul rând se alimentează numărul de perechi de N (1 ≤ N ≤100 000). Fiecare dintre următoarele N linii conține două numere întregi pozitive care nu depășesc 10.000.
Exemplu de intrare pentru varianta B:
6
03 ianuarie
05 decembrie
09 iunie
04 mai
03 martie
01 ianuarie
Exemplu de ieșire pentru exemplul de mai sus, datele de intrare 32
Sarcina B.
De la început să ia în considerare soluția unui cadru mai general (opțiunea B).
Pentru a obține valoarea maximă posibilă va fi preluată din fiecare pereche de cel mai mare număr. În cazul în care suma primită și va fi împărțit în 3, ar trebui să fie redusă. Este suficient într-una dintre perechile, în care numerele sunt diferite reziduuri atunci când împărțit la 3, înlocuiți numărul selectat anterior de un alt număr de aceeași pereche. Diferența dintre numerele din pereche trebuie să fie minim posibil. În cazul în care toate perechile de două numere au același rest atunci când împărțit la 3 pentru a obține cantitatea necesară nu este posibilă.
Programul 1. Exemplu de program corect și eficient pentru a seta B în Pascal.
Aici este un exemplu bazat pe acest principiu al programului în Pascal.
Programul 2. Exemplu de programul corect și eficient pentru setarea PASCAL B
Sarcina A.
Această sarcină poate fi realizată „pe frunte“: pentru a salva într-o matrice toate datele brute, prin toate căile posibile pentru a selecta un element din fiecare pereche și pentru a găsi valoarea maximă corespunzătoare condițiilor problemei.
Aici este un exemplu al unei astfel de decizii
Exemplu O soluție a problemei în Pascal.
var
a: array [1..6, 1..2] de longint;
i1, i2, i3, i4, i5, I6: longint;
s, Smax: longint;
începe
pentru i1: = 1 până la 6 do readln (a [i1,1], o [i1,2]);
Smax: = 0;
pentru i1: = 1 la 2 do
pentru i2: = 1 la 2 do
pentru i3: = 1 la 2 do
pentru i4: = 1 la 2 do
pentru i5: = 1 la 2 do
pentru I6: = 1 până la 2 do începe
s: = a [1, i1] + o [2, i2] + o [3, i3] + o [4, i4] + o [5, i5] + o [6, i6];
dacă (s mod 3 <> 0) și (s> Smax) apoi Smax: = s
se încheie;
writeln (Smax)
end.