Clasa a IX-a lecția 9 - 14 dec 2019

From Algopedia
Jump to navigationJump to search

Clasament teme lecțiile 1 - 8

Clasamente avansați

Avansați Infoarena
Avansați Varena

Clasamente începători

Începători Varena

Lecție

Element Majoritar

Cei avansați au avut ca temă problema Livada, problemă în care era necesară găsirea elementului majoritar dintr-un șir de numere. Elementul majoritar dintr-un șir de N numere este acela care apare de cel puțin [N / 2] + 1 ori. Am promis că voi reveni cu o rezolvare optimă la această problemă și am întarziat o lecție cu ea, îmi cer scuze!

Există multe moduri de abordare pentru această problemă și multe dintre acestea sunt exemplificate în acest link: Problema Majorității Votului.

Soluție timp: O(N) memorie: O(1)

În continuare vom dezvolta soluția optimă pentru această problemă. Această soluție nu necesită cunoașterea altor algoritmi sau metode de programare, având în spate o idee simplă și ingenioasă. Și fiindcă îmi este foarte dragă explicația din link-ul de mai sus, am să v-o prezint așa cum este scrisă acolo:

Soluție

„Imaginaţi-vă o sală de conferinţă în care votanţii ţin fiecare o placă ce poartă numele candidatului preferat. Să presupunem că se ajunge la o bătaie generală în care votanţii cu convingeri diferite încep să se lovească reciproc cu plăcile. Să mai presupunem că fiecare votant care pune la pământ un membru cu alte convingeri este simultan şi el pus la pământ de adversar. Este evident că dacă ar fi vreun candidat care are mai multe voturi decât toate voturile celorlalţi candidaţi, atunci această luptă va fi câştigată de acest candidat şi la dispariţia haosului din urma luptei, votanţii ce au rămas în picioare vor fi susţinători ai candidatului amintit. În caz că nu există o majoritate clară pentru un candidat sau altul, la finalul luptei rămân în picioare votanţi care susţin acelaşi candidat, dar acesta poate să nu fie reprezentantul majorităţii. Deci, în general, dacă cineva rămâne în picioare, preşedintele conferinţei este obligat să verifice dacă într-adevar candidatul întruneşte votul a jumătate plus unu din votanţi. Algoritmul practic folosit de noi va fi un fel de joc al împerecherilor între candidaţi de opinii diferite până când toţi votanţii rămaşi necuplaţi vor susţine acelaşi candidat.”

Realizăm acest algoritm parcurgând lista votanţilor şi ţinând un contor cu numărul de candidaţi k neîmperecheaţi până la pasul curent, evident dacă ei sunt neîmperecheaţi trebuie să susţină acelaşi candidat pentru că altfel am fi putut să cuplăm câţiva dintre ei. Menţionăm că această rezolvare are doar operaţii în care se verifică dacă două valori sunt identice, fapt ce se poate dovedi util pentru obiecte complexe care ar substitui candidaţii din problemă. Rezolvările anterioare s-au folosit de faptul că între elementele şirului ar exista o relaţie de ordine sau că am putea efectua asupra lor operaţii aritmetice. 

#include <stdio.h>

int v[100];

int main() {
  FILE *fin, *fout;
  fin = fopen("majoritar.in", "r");
  fout = fopen("majoritar.out", "w");

  int n, candidat, voturi, i;
  fscanf(fin, "%d", &n);
  for (i = 0; i < n; ++i)
    fscanf(fin, "%d", &v[i]);

  candidat = -1;
  voturi = 0;
  for (i = 0; i < n; ++i) {
    if (voturi == 0) {
      candidat = v[i];
      voturi = 1;
    } else if (v[i] == candidat) {
      ++voturi;  // nu am putut împerechea pe votantul i şi astfel trebuie să mărim numărul de votanţi necuplaţi
    } else {
      --voturi;  // cuplăm votantul i cu orice votant ce îl susţine pe cand şi micşorăm astfel numărul de votanţi necuplaţi
    }
  }

  // verificam daca avem suficiente voturi
  voturi = 0;
  for (i = 0; i < n; ++i)
    if (v[i] == candidat)
      ++voturi;

  if (voturi <= n / 2)
    candidat = -1;  // nu avem candidat majoritar

  fprintf(fout, "Elementul majoritar este %d\n", candidat);

  fclose(fin);
  fclose(fout);
}

Baze de numerație - Continuare

După cum am menționat și în lecția trecută, procedeele de transformare în alte baze de numerație sunt similare, ceea ce se schimbă fiind doar numărul folosit în operațiile de înmulțire sau împărțire.

Baza 16

Baza 16 folosește 16 cifre hexazecimale. Primele 10 cifre sunt cele cunoscute. Următoarele 6 cifre sunt primele litere ale alfabetului latin: A, B, C, D, E și F. A are valoarea 10, B are valoarea 11 și așa mai departe până la F care are valoarea 15. De exemplu:

B9A(16) = B×162 + 9×16 + A = 11×162 + 9×16 + 10 = 11×256 + 9×16 + 10 = 2816 + 144 + 10 = 2970(10)

Conversia de la baza 2 la baza 16

Pentru a converti un număr de la baza 2 la baza 16 nu este nevoie să trecem prin baza 10. Putem proceda astfel:

Grupăm cifrele numărului binar câte patru, începând de la dreapta către stînga. Ultima grupă poate să aibă mai puțin de patru cifre binare. Fiecare grup va fi un număr binar între 0 și 15, adică echivalentul unei cifre hexazecimale. Înlocuim aceste grupuri cu cifra echivalentă în baza 16. Exemplu:

1010110110010110111(2) = 101 0110 1100 1011 0111(2) = 5 6 12 11 7 = 56CB7(16)

Conversia de la baza 16 la baza 2

Pentru a converti rapid un număr de la baza 16 la baza 2 vom proceda în sens invers: vom exprima fiecare cifră hexa ca patru cifre binare, făcând conversia la baza 2 a valorii cifrei hexa. Exemplu:

56CB7(16) = 5 6 12 11 7 = 101 0110 1100 1011 0111(2) = 1010110110010110111(2)

Parantezare

Dându-se un șir de paranteze rotunde deschise și închise, să se verifice dacă acestea formează o expresie corectă de paranteze. Exemple:

  • ()(()()) este corectă
  • ((()))( este incorectă

Putem rezolva problema observând următoarele reguli valabile pentru orice expresie corectă:

  • oriunde "rupem" expresia, în partea stângă vom avea un număr de paranteze deschise mai mare sau egal cu cele închise
  • la final numărul de paranteze închise trebuie să fie egal cu cele deschise
#include <stdio.h>

int main() {
  FILE *fin, *foutș
  fin = fopen("paranteze.in", "r");
  fout = fopen("paranteze.out", "w");

  int n, i, sum;
  char c;
  fscanf(fin, "%d", &n);
  fgetc(fin);

  sum = i = 0;
  while ( i < n && sum >= 0 ) {
    c = fgetc(fin);
    if ( c == '(' )
      ++sum;
    else
      --sum;
    ++i;
  }
  if ( sum == 0 )
    fprintf(fout, "Parantezarea este corecta");
  else
    fprintf(fout, "Parantezarea este incorecta");

  fclose(fin);
  fclose(fout);
  return 0;
}

Observație Actualizând la fiecare pas maximul reținut în variabila sum, putem răspunde și la întrebarea: Care este numărul maxim de paranteze una într-alta?.

Exponențiere rapidă

Calculați an în mod cât mai eficient (a și n numere naturale). Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic (exponențiere rapidă). Ideea din spatele acestei rezolvări este următoarea:

  • Dacă n este par, atunci an = a2*n/2 = (a2)n/2
  • Dacă n este impar, atunci n-1 este par și avem an = a * an-1 = a * a2*(n-1)/2 = a * (a2)(n-1)/2 = a * (a2)n/2

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. De aceea atunci când n este impar (n-1)/2 este totuna cu n/2. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile când n este impar vom acumula valoarea curentă a lui a la produsul calculat. Iată soluția bazată pe această idee: 

#include <stdio.h>

int main() {
    int a, n;
    scanf("%d%d", &a, &n);

    int p = 1;
    while (n > 0) {
        if (n % 2 == 1)
            p = p * a;
        a = a * a;
        n = n / 2;
    }
    printf("%d", p);

    return 0;
}

Interclasare vectori

Dați doi vectori ordonați crescător construiți un al treilea vector ordonat crescător cu elementele din primii doi vectori. Sunt permise elemente duplicat. Exemplu: dați vectorii 1 4 6 9 și 2 4 5 9 12 rezultatul este vectorul 1 2 4 4 5 6 9 9 12.

O soluție ar fi să copiem toate elementele în cel de-al treilea vector și apoi să îl ordonăm. Există însă o soluție mai bună, bazată pe faptul că vectorii sunt deja ordonați. Să observăm că primul element din vectorul final este minimul dintre primele elemente din vectorii inițiali. Îl putem deci copia și apoi îl eliminăm din vectorul din care face parte. Apoi reluăm procedura. La un moment dat unul din vectori se va goli. În acel moment copiem ceea ce a rămas din vectorul nevid. Vom folosi trei indici i1, i2 și i3 care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția: 

// avem vectorii v1 de n1 elemente si v2 de n2 elemente
// vrem sa construim vectorul v3 de n1 + n2 elemente
i1 = 0;
i2 = 0;
i3 = 0;
while ( i1 < n1 && i2 < n2 ) { // mai avem elemente in ambii vectori?
  if ( v1[i1] < v2[i2] ) {     // daca v1 are elementul mai mic
    v3[i3] = v1[i1];           // il copiem
    i1++;                      // si avansam pe urmatorul element
  } else {                     // altfel v2 are elementul cel mai mic
    v3[i3] = v2[i2];           // il copiem
    i2++;                      // si avansam pe urmatorul element
  }
  i3++;                        // avansam si in vectorul v3
}
// in acest moment unul din vectorii v1, v2 este vid
while ( i1 < n1 ) { // incercam sa copiem elementele ramase in v1, daca exista
  v3[i3] = v1[i1];
  i1++;
  i3++;
}
while ( i2 < n2 ) { // incercam sa copiem elementele ramase in v2, daca exista
  v3[i3] = v2[i2];
  i2++;
  i3++;
}
n3 = n1 + n2;

Ce complexitate are acest algoritm? Se observă că la fiecare iterație a primei bucle while unul din indicii i1 sau i2 crește cu unu. La final, indicele care nu a parcurs întregul vector o va face în una din buclele while următoare. Vom face, în total, n1 + n2 prelucrări, deci complexitatea este O(n1+n2).

Câtă memorie folosește acest algoritm? Avem, pe de o parte, vectorii inițiali, ce ocupă O(n1+n2). Avem însă nevoie și de vectorul rezultat, care ocupă tot O(n1+n2). Rezultă că memoria totală va fi O(n1+n2). Este important să remarcăm că avem nevoie de un vector suplimentar, vectorul rezultat. Nu putem refolosi vectorii inițiali.

Lecția următoare

Lecția următoare pică în vacanță (21 decembrie), așa că cercul nu se va ține, nu este nevoie să fiți prezenți "fizic".

Concursuri

Vă voi pregăti două concursuri, câte unul pentru fiecare grupă. Vă voi lăsa link-urile pe Slack.

Teme

Continuați să lucrați din teme și în funcție de cum vă descurcați și ce dorință de lucru aveți, voi mai adăuga probleme. Vineri (20 decembrie) voi reactualiza clasamentele!

Temă

Veniți fiecare cu o listă de probleme la care întâmpinați probleme din lecțiile de până acum, inclusiv aceasta. Scrieți-mi lista pe Slack sau aduceți-o la cercul viitor. În funcție de cerere: vă voi ajuta fie personal, fie voi adăuga explicația problemei în lecția în care a fost dată ca temă, fie voi relua problema la una din lecțiile viitoare.

Avansați

infoarena - elmaj
varena - decbin
varena - abc1
varena - portofel


Probleme date la OJI / ONI
Aceste probleme nu necesită cunoștințe adiționale pe lângă cele care au fost deja discutate la cerc. Deci, sunteți invitați să le lucrați!

infoarena - cifre5
infoarena - cern
infoarena - cmmmc

Începători

infoarena - elmaj
infoarena - gsr
varena - decbin (greuță)
varena - puteri2
varena - impletire (greuță)
varena - portofel (greuță)

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_IX-a_lecția_9_-_14_dec_2019&oldid=17055"