Clasa a V-a lecția 41 - 9 iun 2015

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Lecție

Elementul majoritar

Majoritar: dat un vector cu n elemente să se spună dacă conține un element majoritar. Un element majoritar este un element care apare de cel puțin n/2 + 1 ori. Încercați să dați o soluție mai bună decît sortarea.

Răspuns: dacă există un element majoritar, maj, rezultă că fiecare din elementele vectorului diferite de maj poate fi cuplat cu un element egal cu maj astfel încît după ce toate cuplările au fost făcute să rămînă cel puțin un element maj necuplat. Ideea de rezolvare este să simulăm această cuplare. Vom porni cu primul element al vectorului ca un candidat de element majoritar. Parcurgem elementele vectorului ținînd minte cîți candidați necuplați avem. De fiecare dată cînd dăm peste un element egal cu candidatul incrementăm numărul de elemente necuplate. Cînd dăm peste un element diferit scădem numărul de elemente necuplate. Dacă la un moment dat vom avea zero candidați necuplați și mai vine un element diferit de candidat rezultă că am eliminat din vector un număr egal de candidați și non-candidați, drept pentru care putem reporni problema pentru vectorul rămas: vom considera elementul curent drept candidat, cu o apariție.

La final vom rămîne cu un candidat ce trebuie acum verificat: numărăm de cîte ori apare el in vector printr-o parcurgere. Dacă apare de măcar n/2+1 ori am găsit elementul majoritar, altfel el nu există. Complexitatea acestei soluții este liniară, O(n), algoritmul făcînd două parcurgeri prin vector.

Iată o implementare posibilă:

#include <stdio.h>

int v[3000000];

int main() {
  FILE *fin, *fout;
  int n, i, nr, maj;

  // citire vector
  fin = fopen( "majoritar.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  // cautam candidatul la element majoritar
  maj = v[0];
  nr = 1;
  for ( i = 1; i < n; i++ )
    if ( v[i] == maj ) // cita vreme avem maj incrementam numarul de maj gasite
      nr++;
    else {
      nr--;            // altfel decrementam numarul de maj
      if ( nr < 0 ) {  // daca am scazut sub zero
        maj = v[i];    // alegem drept candidat elementul curent
        nr = 1;        // care apare o data
      }
    }

  // verificare candidat la element majoritar
  nr = 0;
  for ( i = 0; i < n; i++ ) // numaram de cit ori apare maj in vector
    if ( v[i] == maj )
      nr++;

  fout = fopen ( "majoritar.out", "w" );
  if ( nr > n / 2 ) // daca maj apare de mai mult de n/2 ori este majoritar
    fprintf( fout, "%d %d\n", maj, nr );
  else
    fprintf( fout, "-1\n" );
  fclose( fout );
}

Minime multiple

Să calculăm nrmin, numărul de elemente minime într-un vector. Prima idee, probabil cea mai simplă, este să executăm doi pași. În prima trecere găsim minimul, în cea de-a doua numărăm de cîte ori apare. Iată această soluție:

  min = v[0];
  for ( i = 1; i < n; i++ )
    if ( v[i] < min )
      min = v[i];
  nrmin = 0;
  for ( i = 0; i < n; i++ )
    if ( v[i] == min )
      nrmin++;

O idee care duce la o soluție mai bună este să facem o singură trecere. Atunci cînd găsim un element mai mic decît minimul, îl păstrăm cu un număr de apariții 1. Atunci cînd găsim un element egal cu minimul, pur și simplu incrementăm numărul de apariții. Iată programul:

  min = v[0];
  nrmin = 1;
  for ( i = 1; i < n; i++ )
    if ( v[i] < min ) {
      min = v[i];
      nrmin = 1;
    } else if ( v[i] == min ) {
      nrmin++;
    }

De ce este această soluție mai bună? Deoarece:

  • face o singură trecere prin vector.
  • poate să rezolve problema fără să aibă nevoie de stocarea elementelor într-un vector.

Temă

Tema 41 clasa a 5a

Rezolvări aici [3]