Welcome, Guest. Please login or register.

Autor Subiect: numar maxim de elemente ale sirului a caror suma se divide cu 3  (Citit de 7095 ori)

0 Membri şi 1 Vizitator vizualizează acest subiect.

Ayumi

  • Vizitator
numar maxim de elemente ale sirului a caror suma se divide cu 3
« : Decembrie 03, 2011, 11:07:46 a.m. »
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!

Offline tavy

  • Experimentat
  • ***
  • Mesaje postate: 544
  • Popularitate: +26/-26
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #1 : Decembrie 03, 2011, 12:32:46 p.m. »
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;
}

Ayumi

  • Vizitator
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #2 : Decembrie 03, 2011, 02:55:51 p.m. »
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 ...

Offline tavy

  • Experimentat
  • ***
  • Mesaje postate: 544
  • Popularitate: +26/-26
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #3 : Decembrie 03, 2011, 05:01:05 p.m. »
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.

Offline tavy

  • Experimentat
  • ***
  • Mesaje postate: 544
  • Popularitate: +26/-26
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #4 : Decembrie 03, 2011, 06:17:40 p.m. »
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.

Ayumi

  • Vizitator
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #5 : Decembrie 03, 2011, 06:28:36 p.m. »
 Da,va multumesc mult ! Chiar  nu aveam nicio idee cum sa construiesc algoritmul...

Offline tavy

  • Experimentat
  • ***
  • Mesaje postate: 544
  • Popularitate: +26/-26
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #6 : Decembrie 03, 2011, 06:50:43 p.m. »
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.

Ayumi

  • Vizitator
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #7 : Decembrie 04, 2011, 02:00:06 p.m. »
 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;
}

Offline tavy

  • Experimentat
  • ***
  • Mesaje postate: 544
  • Popularitate: +26/-26
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #8 : Decembrie 04, 2011, 02:28:29 p.m. »
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.

Offline tavy

  • Experimentat
  • ***
  • Mesaje postate: 544
  • Popularitate: +26/-26
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #9 : Decembrie 04, 2011, 02:35:14 p.m. »

#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;
}

Ayumi

  • Vizitator
Răspuns: numar maxim de elemente ale sirului a caror suma se divide cu 3
« Răspuns #10 : Decembrie 04, 2011, 03:43:57 p.m. »
Da,intr-adevar.Nu imi afiseaza bine pentru sirul acela...
« Ultima Modificare: Decembrie 04, 2011, 03:46:07 p.m. de Ayumi »