Clasa a V-a lecția 32 - 15 mar 2018

Comentarii temă

1. Felicitări pentru comentarii (cei care mă ajută comentînd programele): Cojocariu, Petcu, Rebengiuc, Tatomir.
2. Benescu m-a inspirat să scriu o soluție trăznită la problema chibrituri, bazată pe vectori preinițializați și precalcularea tuturor răspunsurilor posibile. Programul are 23 de linii, din care trei sînt declararea vectorilor. Pentru cei curioși este ultima sursă pe care am trimis-o la arhivă. Avertisment: nu e tocmai simplu de înțeles și nici nu are vreo valoare deosebită, e doar "șmecheră".
3. Atenție: nu aveți voie să folosiți instrucțiunile: break, continue, goto. La prima sursă care conține astfel de "înjurături" informatice, veți fi descalificați. Înseamnă că fie ignorați cursul, fie ați copiat sursa din altă parte. Ați fost avertizați. Hossu: nu e primul avertisment pe care ți-l dau. Dar este ultimul.
4. Problema ore: v-a dezorientat foarte rău, deși este simplă. Am renunțat să o corectez deoarece am observat că mulți dintre voi ați încercat să ordonați cifrele orei, crescător și descrescător. Este o soluție aproximativă, încîlcită, foarte ușor de greșit, care și dacă duce la soluție va fi una foarte lungă. Vom discuta, în schimb, la oră, o soluție simplă.
5. Problema consiliu: unii din voi au încercat o soluție în care țineați intersecția intervalelor ca fiind formată din unul sau două subintervale. Această soluție nu funcționează, intersecția tuturor intervalelor poate fi formată din mai mult de două subintervale.
6. Problema consiliu: mulți dintre voi au tratat diferit cazul cînd timpul de plecare este mai mic decît cel de sosire, adică atunci cînd profesorul pleacă a doua zi. Atenție, cele două cazuri se pot trata uniform, dacă avansăm cu indicele în vector în mod circular, modulo 1440. Vedeți soluția mai jos.

Tema - rezolvări

Rezolvări aici [1]

Concurs - rezolvări

Rezolvări aici [2]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-03-15-lectie-info-32-720p.mp4</html5media>

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;

Nu uitați! Iată erorile frecvente în implementarea ciurului lui Eratostene:

• Vectorul ciur este un vector de caractere, nu de întregi.
• Vectorul ciur se declară cu un element în plus față de n. Dacă n este 20000 vom declara char ciur[20001].

Adaptări ale ciurului lui Eratostene

Ciurul lui Eratostene poate fi modificat pentru a calcula și alte valori utile, nu doar primalitatea numerelor. În general, adaptările vor avea la bază prima formă a ciurului, cea neoptimizată.

Numărul de divizori primi

Putem adapta algoritmul pentru a calcula numărul de divizori primi ai numerelor de la 1 la n. Tot ce avem de făcut este ca în loc de a seta pe unu numerele din d în d, să adunăm 1 la acele elemente. Va trebui să folosim varianta neoptimizată și va trebui să pornim cu i chiar de la d și nu de la d+d.

Numărul de divizori

Putem adapta algoritmul pentru a calcula numărul de divizori (primi sau neprimi) ai numerelor de la 1 la n. Va trebui să folosim tot varianta neoptimizată și vom "tăia" numerele chiar și pentru numere neprime. La "tăiere" vom aduna unu elementului din vector, întocmai ca la varianta anterioară. Atenție, deoarece numărul de divizori poate fi mare, vectorul ciur va trebui declarat de întregi și nu de caractere.

Temă

Deoarece OJI/ONI bat la ușă am adus modificări formatului temei: testele nu vor mai fi disponibile, iar sursele trimise vor fi penalizate de varena, astfel: prima sursă primește zero penalizare (nu este penalizată), 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% (de la a șasea sursă mai departe nu mai sînteți penalizați suplimentar).

Vă rog foarte mult să nu trișați. Nu trimiteţi surse la arhivă, sau la alte concursuri din care problema face parte, doar 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 32: să se rezolve următoarele probleme (program C trimis la vianuarena):

• prime ca exercițiu de ciurul lui Eratostene
• apropiate1 dată la ONI 2004 clasa a 6^a, tot ca exercițiu de ciurul lui Eratostene
• kdiv ca aplicație (variație) a ciurului lui Eratostene

Rezolvări aici [3]