Buna ziua ! Am incercat sa rezolv urmatoarea problema la informatica,dar nu mi-a venit nicio idee :
Gigel si-a pus intrebarea care este numarul maxim de elemente ale unui sir de n numere naturale a caror suma se divide cu 3.
Fiind dat un sir de n numere naturale,determinati numarul maxim de elemente ale sirului a caror suma se divide cu 3.Determinati de asemenea elementele care nu fac parte din suma.
De exemplu,pentru n = 7 si numerele 10, 6, 7, 12, 4, 7, 22 nr maxim de elemente a caror suma se divide cu 3 este k = 5,elementele fiind 6,12,4,7,22. Elementele care nu fac parte din suma sunt 10 si 7.
Imi puteti da un indiciu ca sa ma ajute la determinarea algoritmului pentru problema ? Am cumva nevoie de un vector?
Multumesc anticipat!
Uite o posibilă rezolvare
#include<iostream>
using namespace std;
int main(){
int i,n,n0,n1,n2,nmax,aux;
cin>>n;
for(i=n0=n1=n2=0;i<n;i++){
cin>>aux;
switch(aux%3){
case 0:
n0++;
break;
case 1:
n1++;
break;
case 2:
n2++;
}
}
nmax=n0+(n1/3)*3+(n2/3)*3;
n1%=3;
n2%=3;
nmax+=(n1<n2?n1:n2)*2;
cout<<nmax<<endl;
}
Citat din: tavy din Decembrie 03, 2011, 12:32:46 PM
Uite o posibilă rezolvare
#include<iostream>
using namespace std;
int main(){
int i,n,n0,n1,n2,nmax,aux;
cin>>n;
for(i=n0=n1=n2=0;i<n;i++){
cin>>aux;
switch(aux%3){
case 0:
n0++;
break;
case 1:
n1++;
break;
case 2:
n2++;
}
}
nmax=n0+(n1/3)*3+(n2/3)*3;
n1%=3;
n2%=3;
nmax+=(n1<n2?n1:n2)*2;
cout<<nmax<<endl;
}
La mine aux = nr// nr citit curent,iar nmax = k.
Deci daca restul nr citit curent de la tastatura este:
case 0: atunci n0 creste ; daca restul e 1 atunci n1 creste cu 1,iar daca este 2 atunci n2 creste cu 1.La sfarsit nmax = nmax + suma dintre n0 si (n1/3)*3 si (n2/3) *3 ...
Ideea este următoarea:
Pe măsură ce citim numerele din șir numărăm astfel:
n0 - numărul de numere de forma 3k
n1 - numărul de numere de forma 3k+1
n2 - numărul de numere de forma 3k+2
Numerele de forma 3k vor intra toate în suma finală și în consecință n0 se adună la nmax.
Fiecare 3 numere de forma 3k+1 pot fi adăugate la suma finală așa că (n1/3)*3, adică câtul împărțirii lui n1 la 3 înmulțit cu 3, se adaugă la nmax.
În mod analog, pentru numerele de forma 3k+2 se adaugă la nmax (n2/3)*3.
Mai pot rămâne 0,1 sau 2 numere de forma 3k+1 neadăugate la sumă și tot 0, 1, sau 2 numere de forma 3k+2 neadăugate la sumă. Orice pereche de numere, unul de forma 3k+1 și unul de forma 3k+2, se poate adăuga la sumă așa că adaug la nmax minimul dintre n1 și n2.
Când încercam să demonstrez că algoritmul meu chiar întoarce numărul maxim am realizat că algoritmul este greșit.
Astfel, pentru șirul: 2, 2, 2, 1, 1 algoritmul meu întoarce 3 pentru că va considera că suma ar fi 2+2+2=6 în timp ce răspunsul corect este 4 pentru că este posibil să scriem 2+2+1+1=6.
Așa că, probabil ar trebui luate în calcul întâi toate perechile de numere de forma (3k+1, 3k+2) și abia apoi grupurile de câte 3 numere de forma 3k+1 sau 3k+2.
Revin cu programul rescris puțin mai târziu.
Da,va multumesc mult ! Chiar nu aveam nicio idee cum sa construiesc algoritmul...
Sper că codul de mai jos este, de data aceasta, corect:
#include<iostream>
using namespace std;
int main(){
int i,n,n0,n1,n2,nmax,aux;
cin>>n;
for(i=n0=n1=n2=0;i<n;i++){
cin>>aux;
switch(aux%3){
case 0:
n0++;
break;
case 1:
n1++;
break;
case 2:
n2++;
}
}
nmax=n0;
aux=(n1<n2?n1:n2);
aux-=aux%2;
nmax+=aux*2;
n1-=aux;
n2-=aux;
nmax+=(n1/3)*3+(n2/3)*3;
n1%=3;
n2%=3;
nmax+=(n1<n2?n1:n2)*2;
cout<<nmax<<endl;
}
Astfel, se iau întâi numerele de forma 3k, apoi grupurile de câte 4 numere, 2 de forma 3k+1 și 2 de forma 3k+2, apoi grupurile de câte 3 numere de forma 3k+1 sau 3k+2, apoi grupurile de 2 numere, unul de forma 3k+1 și unul de forma 3k+2.
Nu am inspirația la momentul acesta să demonstrez că algoritmul chiar produce numărul maxim dar intuitiv pare că așa face, cel puțin nu am găsit, la o primă vedere, cazuri în care dă rateuri.
Problema ar fi complet rezolvată abia după demonstrația matematică că algoritmul este corect, probabil se poate face prin metoda reducerii la absurd.
Cred ca am reusit sa fac programul sa mearga si pentru sirul de numere 2,2,2,1,1.
Merge !! ;D
Dar ma gandesc ca ar exista si o metoda mai simpla,nu stiu...
Acesta e codul :
#include<iostream>
using namespace std;
int main()
{
int i, n, n0, n1, n2, aux, nn1, nn2, min;
int nmax = 0;
cin >> n;
for (i=n0=n1=n2=0; i<n; i++) {
cin >> aux;
switch (aux%3) {
case 0: n0++; break;
case 1: n1++; break;
case 2: n2++;
}
}
// adaugam numarul de elemente de forma 3k
nmax += n0;
// determinam numarul maxim de perechi de forma (3k+1, 3k+2)
min = (n1 < n2 ? n1 : n2);
// adaugam numarul de elemente care pot compune perechi de forma (3k+1, 3k+2);
nmax += 2*min;
// eliminam din n1 si n2 numarul de elemente deja folosite in suma
n1 -= min;
n2 -= min;
// determinam cate grupuri de 3 elemente de forma 3k+1 si 3k+2 mai raman
nn1 = n1 - n1%3;
nn2 = n2 - n2%3;
nmax += nn1 + nn2;
// eliminam din n1 si n2 numarul de elemente deja folosite in grupurile de mai sus
n1 -= nn1; // n1 = 0, 1 sau 2
n2 -= nn2; // n2 = 0, 1 sau 2
if (!n1 || !n2) {
cout << nmax << "vvvv" << endl;
return 0;
}
if (n1 == n2 == 2) {
nmax += 4;
cout << "+++" << nmax;
}
if ((n1 + n2)%3 == 0 || n1 == n2 == 1) {
nmax += 2;
cout << "---" << nmax;
}
cout << nmax << endl;
return 0;
}
Citat din: Ayumi din Decembrie 04, 2011, 02:00:06 PM
Cred ca am reusit sa fac programul sa mearga si pentru sirul de numere 2,2,2,1,1.
Merge !! ;D
Dar ma gandesc ca ar exista si o metoda mai simpla,nu stiu...
Mai simplu ar fi cum a făcut eu.
Oricum programul tău greșește pentru șirul 2,2,2,1 pentru ca afișează valoarea 2, luând în considerare 2+1, în loc să afișeze 3 pentru 2+2+2.
Trebuie să elimini mai întâi perechile (2k+2, 2k+2) numai dacă ai câte două astfel de perechi ca să elimini 4 numere, astfel este de preferat să elimini mai întâi 3 numere de forma 3k+1 sau 3k+2.
#include<iostream>
using namespace std;
int main()
{
int i, n, n0, n1, n2, aux, nn1, nn2, min;
int nmax = 0;
cin >> n;
for (i=n0=n1=n2=0; i<n; i++) {
cin >> aux;
switch (aux%3) {
case 0: n0++; break;
case 1: n1++; break;
case 2: n2++;
}
}
// adaugam numarul de elemente de forma 3k
nmax += n0;
// determinam numarul maxim de perechi de forma (3k+1, 3k+2)
min = (n1 < n2 ? n1 : n2);
// adaugam numarul de elemente care pot compune perechi de forma (3k+1, 3k+2);
//aici greșești, nu trebuie să adaugi decât dacă min este par, altfel trebuie să adaugi doar (min-1)*2
//altfel spus mai bine faci min-=min%2
//abia după ce elimini și grupurile de câte 3 mai elimini, dacă-ți mai rămâne o eventuală pereche (3k+1, 3k+2)
nmax += 2*min;
// eliminam din n1 si n2 numarul de elemente deja folosite in suma
n1 -= min;
n2 -= min;
// determinam cate grupuri de 3 elemente de forma 3k+1 si 3k+2 mai raman
nn1 = n1 - n1%3;
nn2 = n2 - n2%3;
nmax += nn1 + nn2;
// eliminam din n1 si n2 numarul de elemente deja folosite in grupurile de mai sus
n1 -= nn1; // n1 = 0, 1 sau 2
n2 -= nn2; // n2 = 0, 1 sau 2
//Deja de aici te complici mult
if (!n1 || !n2) {
cout << nmax << "vvvv" << endl;
return 0;
}
if (n1 == n2 == 2) {
nmax += 4;
cout << "+++" << nmax;
}
if ((n1 + n2)%3 == 0 || n1 == n2 == 1) {
nmax += 2;
cout << "---" << nmax;
}
cout << nmax << endl;
return 0;
}
Da,intr-adevar.Nu imi afiseaza bine pentru sirul acela...