Clasa a V-a lecția 30 - 24 mar 2015

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Rezolvări aici [1]

Lecție

Ciurul lui Eratostene

Eratostene a fost un matematician, geograf, poet, astronom și muzician grec. El a trăit între anii 276 și 195 î.Hr. El a inventat cuvîntul "geografie" în greacă, a inventat un sistem de latitudine și longitudine. A fost primul om care a calculat circumferința pămîntului, a calculat înclinația axei de rotație a pămîntului, a creat conceptul de an bisect, și zi bisectă. Tot el a creat prima hartă a lumii, incluzînd paralele și meridiane.

Eratostene a inventat un algoritm foarte eficient de calcul al tuturor numerelor prime pînă la un număr dat. Acest algoritm se studiază la matematică. El procedează astfel:

  1. Creează o listă a întregilor consecutivi de la 2 la n: [2, 3, 4, ..., n].
  2. Caută primul număr netăiat din listă (inițial nici un număr nu e tăiat). Fie p acel număr.
  3. Mergi din p în p prin listă, începînd cu 2*p și taie toate numerele întîlnite (unele vor fi deja tăiate)
  4. Reia de la pasul 2, pînă ce depășim n.

În final numerele rămase netăiate sînt prime.

Cum implementăm acest algoritm, care la origine se executa manual, cu hîrtie și creion? Pentru a simula tăierea numerelor vom folosi un vector de frecvență, ciur, care pentru fiecare număr între 2 și n ne va spune dacă este tăiat sau nu. Inițial vectorul ciur va fi inițializat cu zero, care semnifică că toate numerele sînt prime, iar pe măsură ce tăiem numere, ele vor fi marcate cu unu. În final ciur[x] va fi zero dacă numărul este prim, sau unu în caz contrar. Deoarece elementele lui ciur sînt zero sau unu nu are rost să folosim întregi pentru ele, ci vom folosi caractere, văzute ca numere mici. Să ne reamintim că un caracter ocupă un octet (opt biți), pe cînd un întreg ocupă 4 octeți (32 de biți). Astfel, memoria folosită va fi de patru ori mai mică. (Vom vedea, în viitor, că memoria se poate reduce în continuare dacă ținem doar un bit pe element.)

Iată implementarea acestei idei. Programul următor calculează vectorul ciur pentru numerele pînă la n, cu n maxim două milioane:

char ciur[2000001];
...
fscanf( fin, "%d", &n );
for ( d = 2; d < n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d + d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Programul se poate optimiza dacă facem următoarele observații:

  1. În a doua buclă for variabila i ia valorile 2∙d, 3∙d, 4∙d, ..., k∙d. Pentru k < d toate valorile de forma k∙d au fost deja tăiate de valorile k anterioare, drept pentru care nu are rost să le mai parcurgem. Putem să pornim cu i de la d∙d.
  2. Conform observației anterioare i pornește de la d∙d. De aceea nu are rost să mergem cu d mai departe de sqrt(n), deoarece nu vom mai găsi i astfel încît i ≤ n.

Iată implementarea optimizată, bazată pe aceste două observații:

char ciur[2000001];
...
fscanf( fin, "%d", &n );
for ( d = 2; d * d <= n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d * d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

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ă

Deoarece ONI bate la ușă am adus modificări formatului temei: testele *nu* vor mai fi disponibile, iar sursele trimise vor fi penalizate, mai puțin prima, astfel: prima sursă primește zero penalizare, a doua sursă trimisă primește 5% penalizare din scorul obţinut, a treia sursă primește 10%, și așa mai departe. Penalizarea se opreşte la 50%.

Vă rog foarte mult să nu trișați. Nu trimiteţi surse la arhivă, pentru a evita penalizarea. Voi verifica acest lucru. De asemenea mă voi uita cu atenție pe campion! Nu trimiteți surse acolo după începerea temei. Vreau să am o evaluare a voastră mai apropiată de regimul de concurs, nu încercați să luați 100p cu orice preț. Punctele la aceste teme nu contează pentru calificarea la cerc, ci doar îmi dau o impresie despre nivelul vostru, pentru a ști pe ce trebuie să pun accentul și cît de mult.

Tema 30 clasa a 5a:

  • prime ca aplicație a ciurului lui Eratostene
  • arme dată la OJI 2012 clasa a 7a ca aplicație a sortării prin selecție
  • prim dată la ONI 2003 clasa a 5a
  • cub1 dată la ONI 2002 clasa a 5a

Rezolvări aici [2]