Clasa a V-a lecția 33 - 22 mar 2018

From Algopedia
Jump to navigationJump to search

Anunț

Duminică 25 martie voi organiza un concurs de simulare ONI la varena. Ela va începe la ora 15:30 și va dura patru ore.

Comentarii olimpiadă, faza pe municipiu

  1. Felicitări tuturor! Ați ajuns pînă aici cu foarte multă muncă.
  2. Felicitări pentru rezultate. Sunteți 30 de copii în primii 80 din țară, cu punctaje peste 108p, cu excepția a doi dintre voi care ați denumit greșit fișierele. Rezultate excepționale!
  3. Felicitări speciale copiilor de clasa a patra: Dragomir, Grecu, Rebengiuc. Sînteți foarte buni, nu uitați. La anul veți fi cei mai buni! :-)
  4. Problemele au fost ușoare, ceea ce a dus la inversiuni de valori. Unii copii excelenți au făcut doar bine, în vreme ce copii buni au făcut excelent.
  5. În special problema patrate4 este mult prea ușoară pentru județeană. Ea are o rezolvare de o singură linie. Încă o dată se vede că unii profesori nu apreciază corect nivelul de greutate al problemelor. Dacă această problemă era mai grea cred că unii din elevi s-ar fi clasat mai aproape de valoarea lor reală. Dar așa, concursul a fost "cine nu greșește nimic la o problemă banală".
  6. Problema a doua, forus, v-a dat de furcă unora. Sînt convins că puteați să o faceți cu toții. Vă recomand să încercați să o rezolvați și la varena.
  7. Ambele probleme au fost sub nivelul celor date la sector, în opinia mea. Aceasta arată nivelul Bucureștiului față de majoritatea restului țării.
  8. Soluțiile oficiale, publicate, ale comisiei, conțin multe din "așa nu"-urile programării. Cu toate acestea ele sînt uzual predate de către profesori copiilor noștri (vă recomand să vă uitați pe ele):
    • ignorarea programării structurate prin folosirea instrucțiunii break; bun venit în epoca de piatră a algoritmilor și programării, anii 1960!
    • folosire de funcții la clasa a cincea - fără comentarii
    • zero comentarii în programe, deși ele ar trebui să fie sursele prin care copiii să înțeleagă soluțiile problemelor
    • indentare incorectă - greșeală de începător, care este extrem de greu de făcut cîtă vreme programezi în Code::Blocks sau orice alt editor de cod. Este un mister cum reușesc această performanță, ei trebuie să se opună activ indentării automate a editorului.
    • formatare inconsecventă a codului - instrucțiuni fie în continuarea acoladelor, fie pe linia următoare, etc
    • mai multe instrucțiuni pe aceeași linie
  9. Statistici interesante:
    • 120 din primii 250 de elevi au avut punctaje sub 40p, din care 20p acordate din oficiu.
    • Se puteau lua 50p afișînd n*8 la prima problemă, respectiv numărînd cîte numere la intrare nu conțin cifra zero la problema a doua. Cu toate acestea, peste jumate din participanții la județeană nu au luat aceste 50p. Vorbim de cunoștințe pe care elevii le-ar putea acumula în două-trei săptămîni de informatică.
    • Numărul elevilor din țară calificați la națională cu punctaj sub 50p: 17 la momentul acestui mesaj, 22 martie 2018. Posibil să crească.
    • Județele acestor elevi: Arad, Bistrița-Năsăud, Brăila, Buzău, Maramureș, Mehedinți, Mureș, Olt, Sălaj, Suceava, Vâlcea, Vrancea
    • Brăila deține recordul, cu 3 copii calificați cu punctaj sub 50p
    • În acest timp ultimul punctaj calificat din București este de 191p. Un punctaj foarte mare (înaintea suplimentării de 10%, cele 8 locuri naționale extra), în vreme ce elevi din țară se califică cu 30p.
    • Voi completa statisticile de mai sus pe site-ul algopedia.ro, pe măsură ce calificările sînt făcute publice
  10. Din nou, nu uitați, important: la IQ Academy nu facem pregătire pentru olimpiadă, ci ne formăm ca informaticieni. Aceasta înseamnă că nu facem dopaj și învățăm să codăm corect. Obiceiurile proaste cu care veniți de la pregătitorii de olimpici nu se acceptă. Printre acestea se numără folosirea lui break, a stegulețelor inutile, a freopen, vectori declarați cu cîteva elemente în plus în caz că vine drăcușorul indicilor și ne încurcă, for pe post de while și invers, if-uri exclusive între ele care nu se înlănțuie unul pe else-ul celuilalt.

Comentarii tema 32

  1. Felicitări pentru jocul fair play. Nu ați trișat, ați trimis toate submisiile la temă.
  2. Problemele v-au pus ceva probleme. Mai ales problema kdiv. Deci ciurul lui Eratostene nu este banal.
  3. În special problema kdiv v-a dat de furcă, deși am discutat algoritmul și l-am scris pe tablă, doar că nu l-am postat pe algopedia. Înțeleg că fără copy/paste viața este mai grea?

Tema - rezolvări

Rezolvări aici [1]

Lecție

Din motive tehnice (scleroza) nu am filmat această lecție. Video-ul nu este disponibil.

Problemele de la olimpiada pe municipiu

Dragilor, cred că sînteți de acord cu mine că problemele de anul acesta au fost simple, ba chiar prea simple.

Să le discutăm.

Problema patrate4

Problema patrate4 a fost dată la faza pe municipiu 2018, clasa a 5a. Ea este o problemă extrem de simplă, dar care poate speria începătorii prin enunț. Să vedem rezolvarea.

Punctul unu

Observăm imediat că numărul de numere din interiorul unui pătrat este de opt ori numărul pătratului. Vom afișa 8*n.

Punctul doi

Din nou, se vede din avion ca fiecare pătrat începe cu un pătrat perfect. Mai mult, ele sînt pătrate perfecte de numere impare. Cum rezolvăm ușor acest punct?

În primul rînd să observăm ceva evident, anume că pentru a afla cel mai mare pătrat perfect mai mic sau egal cu n vom extrage radical din n. Vom obține numărul k, ce ridicat la pătrat ne va da pătratul perfect căutat.

În continuare vom observa că fiecare pătrat începe cu un pătrat perfect de număr impar și mai conține și următorul pătrat perfect, de număr par. De aceea k va fi unul din aceste numere. Observăm că dacă el este par ar trebui să scădem unu pentru a obține primul număr din pătrat. Dar acest lucru nu contează, deoarece numărul pătratului cerut este t = (k + 1) / 2.

Iată soluția banală ce implentează ideile de mai sus:

#include <stdio.h>
#include <math.h>

int main() {
  FILE *fin, *fout;
  int n, c, rez;

  fin = fopen( "patrate4.in", "r" );
  fscanf( fin, "%d%d", &c, &n );
  fclose( fin );

  if ( c == 1 )
    rez = 8 * n;
  else {
    rez = sqrt( n );
    rez = (rez + 1) / 2;
  }
  
  fout = fopen( "patrate4.out", "w" );
  fprintf( fout, "%d\n", rez );
  fclose( fout );

  return 0;
}

Problema forus

Problema forus a fost dată la faza pe municipiu 2018, clasa a 5a. Ea este o problemă ușoară spre medie, algoritmul și implementarea fiind una la nivel de exercițiu din manual. Ea poate speria mai curînd prin enunț, deși el este foarte clar, în opinia mea. Să vedem cum o rezolvăm în sub 60 de linii.

Punctul unu

Punctul unu ne cere în mod complicat ceva foarte simplu: să spunem cîte din numerele de la intrare nu conțin cifre zero. Am putea fi tentați să ne apucăm să scriem direct programul, nu-i așa? Ar fi însă o greșeală. Este bine să citim și punctul doi înainte de a ne apuca de codat. De ce? Pentru că dacă avem de gînd să rezolvăm și punctul doi (ceea ce sper că avem, nu? :-) el conține 99% din rezolvarea punctului unu.

Drept care, opriți caii, pînă ce rezolvăm punctul doi.

Punctul doi

Esența, "carnea" acestui punct este următoarea: dat un număr x să se genereze toate tăieturile posibile. Pentru fiecare număr generat, y, trebuie să aflăm numărul lui de divizori. Înainte de a face o tăietură va trebui să ne întrebăm dacă este posibilă. Dacă nu este posibilă avem cazul de la punctul unu, anume că numărul x conține o cifră zero.

Putem rezolva în mai multe moduri generarea tăieturilor. Voi alege modul direct, cel descris de algoritm: vom tăia numerele după fiecare cifră posibilă, folosind, ca de obicei, o putere a lui 10 care are 1 pe poziția cifrei după care tăiem. Să luăm următorul exemplu:

  x =  3425878
p10 =    10000
  p = 1000

Deoarece vom tăia după cifra din dreptul cifrei 1 din puterea lui 10, trebuie să generăm

y = 5878342

. Pentru aceasta avem formula:

y = x / p10 + x % p10 * p

La fiecare iterație vom împărți p10 la 10 și vom înmulți p cu 10.

Înainte de a calcula y cu formula de mai sus vom avea grijă să nu tăiem înainte de zero. Pentru aceasta vom testa x / (p10 / 10) % 10.

Programul de mai jos implementează cele discutate, dar modificînd p10 pentru a fi mai convenabil în cod.

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, c, i, nr0, are0, x, y, p, p10, miny, mindiv, ndiv, d;

  fin = fopen( "forus.in", "r" );
  fout = fopen( "forus.out", "w" );
  fscanf( fin, "%d%d", &c, &n );
  nr0 = 0; // numarul de elemente care contin macar o cifra zero
  for ( i = 0; i < n; i++ ) { // citim cele n numere in x
    fscanf( fin, "%d", &x );
    p10 = 100000000; // puterea maxima a lui 10 care incape in x
    while ( p10 > x )
      p10 /= 10;

    mindiv = 1000000;  // un numar de divizori mai mare decit orice valoare
    miny = 1000000000; // mai mare ca orice y
    are0 = 0; // numarul de numere x care contin cifre 0
    p = 1;
    while ( p10 > 0 ) {        // taiem inainte de cifra marcata de p10
      if ( x / p10 % 10 == 0 ) // cifra este zero?
        are0 = 1;              // marcam numarul x cum ca are zero
      else {                   // in caz contrar rezolvam punctul 2
        y = x / (p10 * 10) + x % (p10 * 10) * p; // calculam numarul taiat
        // calculam numarul de divizori al lui y, numarul taiat
        ndiv = 0;
        d = 1;
        while ( d * d < y ) {
          if ( y % d == 0 )
            ndiv += 2;
          d++;
        }
        if ( d * d == y )
          ndiv++;

        // retinem noul y si numarul lui de divizori
        if ( ndiv < mindiv ) { // daca numarul de divizori e mai mic
          miny = y;
          mindiv = ndiv;
        } else if ( ndiv == mindiv && y < miny ) // nr div egal, dar y mai mic
          miny = y;
      }
      p10 /= 10;
      p *= 10;
    }
    nr0 += are0; // incrementam daca numarul x contine cifre 0
    if ( c == 2 )
      fprintf( fout, "%d ", miny );
  }

  if ( c == 1 )
    fprintf( fout, "%d", n - nr0 );
  fprintf( fout, "\n" );
  fclose( fin );
  fclose( fout );

  return 0;
}

Exerciții cu vectori (continuare)

Vector mulțime

Se dă un vector v de n elemente. Să se transforme într-un vector mulțime. Cu alte cuvinte, să se elimine duplicatele din vector. Un vector mulțime este un vector în care orice element apare o singură dată.

Avem mai multe soluții posibile. O primă soluție se bazează pe vectori de frecvență. Putem construi un vector de apariții ale elementelor din v. Apoi vom colecta elementele din vectorul de apariții înapoi in v. Această soluție funcționează pentru valori relativ mici ale elementelor din v.

Dacă valorile din v sînt prea mari pentru a folosi un vector de frecvență, atunci putem să verificăm fiecare element din vector și să îl copiem în alt vector, w, numai dacă el nu apare deja în vectorul w. Iată această soluție:

// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului w
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in w
  j = 0;
  while ( j < m && w[j] != v[i] )
    j++;
  if ( j == m ) { // daca elementul v[i] nu exista in vectorul w, il adaugam
    w[m] = v[i];
    m++;
  }
}

Observație importantă: vectorul w are întotdeauna lungime mai mică sau cel mult egală cu vectorul v.

De aceea putem să nu folosim un vector diferit w, ci să lucrăm chiar pe vectorul v! Codul este identic cu cel de mai sus, înlocuind w cu v:

// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului multime
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in multime
  j = 0;
  while ( j < m && v[j] != v[i] )
    j++;
  if ( j == m ) { // daca elementul v[i] nu exista in multime, il adaugam
    v[m] = v[i];
    m++;
  }
}
// in final vectorul v de lungime m contine multimea vectorului original

Căutare subvector în vector

Dați doi vectori, p (vectorul de căutat) și v (vectorul în care se caută) să se spună de cîte ori apare vectorul p în v. De exemplu dacă p = [1, 2, 1] și v = [1, 2, 1, 2, 1, 3, 1, 2, 1] atunci p apare de 3 ori in v.

Să observăm că aparițiile vectorului p în vectorul v pot fi suprapuse, ca în exemplul de mai sus. Un algoritm direct este să încercăm toate pozițiile de suprapunere ale vectorului p peste vectorul v și să testăm dacă toate elementele din p se potrivesc cu cele din v:

   1, 2, 1, 2, 1, 3, 1, 2, 1
0: 1, 2, 1
1:    1, 2, 1
2:       1, 2, 1
3:          1, 2, 1
4:             1, 2, 1
5:                1, 2, 1
6:                   1, 2, 1

Suprapunînd vectorul p peste v observăm că avem potriviri la pozițiile 0, 2 și 6. Iată programul pentru această metodă:

// avem vectorul v de n elemente si vectorul de cautat p, de m elemente
nr = 0;                                // numarul de aparitii este initial zero
for ( poz = 0; poz < n – m + 1; poz++ ) {   // pentru fiecare pozitie posibila
  i = 0;
  while ( i < m && p[i] == v[poz + i] ) // ne oprim la prima inegalitate
    i++;
  if ( i == m )                         // daca toate elementele au fost egale
    nr++;                               // am mai gasit o aparitie a lui p in v
}
// acum nr contine numarul de aparitii ale lui p in v

Vom vedea în anii următori că există și algoritmi mai eficienți pentru rezolvarea acestei probleme.

Comparație vectori

Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.

Un vector v1 este lexicografic mai mic decît alt vector v2 dacă v1 și v2 sînt egale de la 0 la i-1, iar poziția i este fie în afara vectorului v1, fie v1[i] < v2[i]. Vom compara elementele vectorilor pe aceleași poziții cîtă vreme sînt egale, oprindu-ne la prima diferență, sau cînd unul din vectori se termină. Acolo vom decide care din vectori este mai mic.

Iată programul:

// avem vectorii v1 de n1 elemente si v2 de n2 elemente
i = 0;
while ( i < n1 && i < n2 && v1[i] == v2[i] ) // cita vreme avem egalitate
  i++;                                       // avansam i
// pentru ca v1 sa fie primul in ordine lexicografica trebuie ca
// fie i sa fi depasit ultimul element din v1, fie ca v1[i] < v2[i]
// pentru a doua conditie e nevoie ca v2 sa aiba ceva pe pozitia i
if ( i == n1 || (i < n2 && v1[i] < v2[i]) )
  m = 0;
else
  m = 1;

Rotire multiplă de vector *

Se dă un vector v de n elemente și un număr k. Să se rotească vectorul cu o poziție către început cu k poziții. De exemplu, pentru k=3 [1, 6, 2, 7, 4, 3, 2] se va transforma în [7, 4, 3, 2, 1, 6, 2].

O soluție ar putea fi să rotim vectorul cîte o poziție de k ori. Această soluție face multe deplasări, respectiv k∙n. Un algoritm mai bun este următorul:

  1. Răstoarnă vectorul v.
  2. Răstoarnă subvectorul v[0..n-k-1]
  3. Răstoarnă subvectorul v[n-k..n-1]

De ce funcționează acest algoritm?

Care este numărul de deplasări ale acestui algoritm? Demonstrați că este 3∙n.

Sortarea prin selecție (select sort)

Se dă un vector de n elemente. Să se sorteze prin metoda selecției. Prin sortare înțelegem ordonare crescătoare a elementelor vectorului. Metoda selecției este următoarea: vom găsi maximul din vector, împreună cu poziția sa. Apoi vom interschimba maximul cu ultimul element din vector. Astfel ne vom asigura că ultimul element este chiar cel corect în vectorul ordonat. Ne-a rămas astfel un vector cu n-1 elemente, care trebuie sortat. Vom proceda la fel: vom găsi maximul în subvectorul de n-1 elemente, precum și poziția lui, și-l vom muta la coadă, rezultînd un vector de n-2 elemente. Continuăm procedura pînă ce vectorul este sortat.

Iată o exemplificare grafică:

9 2 8 3 6 5 3 9 6 |
6 2 8 3 6 5 3 9 | 9
6 2 8 3 6 5 3 | 9 9
6 2 3 3 6 5 | 8 9 9
5 2 3 3 6 | 6 8 9 9
5 2 3 3 | 6 6 8 9 9
3 2 3 | 5 6 6 8 9 9
3 2 | 3 5 6 6 8 9 9
2 | 3 3 5 6 6 8 9 9
| 2 3 3 5 6 6 8 9 9

Iată programul:

// avem vectorul v de n elemente
for ( u = n – 1; u > 0; u-- ) { // pozitia ultimului element din subvector
  max = v[0];
  p = 0;                        // p este poziția maximului
  for ( i = 1; i <= u; i++ )
    if ( v[i] > max ) {         // memoram noul maxim si pozitia lui
      max = v[i];
      p = i;
    }
  // interschimbam maximul de pe pozitia p cu ultimul element, pe pozitia u
  v[p] = v[u];
  v[u] = max;
}

Vă recomand folosirea algoritmului de sortare prin selecție și nu a sortării cu bule, deoarece face mai puține operații. În practică el este de cinci pînă la zece ori mai rapid. Desigur, și mai rapidă este sortarea prin vectori de frecvență, numită și sortare prin numărare, atunci cînd ea poate fi aplicată (cînd numerele sînt foarte mici).


Temă

Tema 33: să se rezolve următoarele probleme (program C trimis la vianuarena):

  • siruri1 dată la OJI 2004 clasa a 7a
  • case1 dată la ONI 2009 clasa a 5a
  • arme dată la OJI 2012 clasa a 7a, ca aplicație a sortării prin selecție

Rezolvări aici [2]