Clasa a IX-a lecția 3 - 26 oct 2019

Rezolvare probleme lecția anterioară

Soluții aici [1]

Lecție

Problemă încălzire

Se dau două șiruri de câte N numere naturale. Să se spună câte numere K există care respectă următoarele proprietăți:

• K se divide cu toate numerele din primul șir.
• Toate numerele din al doilea șir se divid cu K.

Soluție aici [2]

Pentru începători

În acest moment la cerc vin oameni cu nivel variat de pregătire și având în vedere că majoritatea dintre voi aveți deja antecedente în programare și în lucrul cu C / C++, recomand celor complet începători să urmeze cursul de gimnaziu sau alt curs de introducere în limbaj sau algoritmică doresc.

Data trecută am încercat să lucrez separat cu voi pentru a vă ajuta să prindeți conceptele și noțiunile de bază ale programării și ale limbajului. În continuare sunt prezentate noțiunile pe care nu am apucat să le vorbim până acum. Nu o să intrăm adânc în detalii și va recomand să lucrați cu aceste noțiuni și să încercați să le aprofundați singuri, folosindu-vă de link-urile pe care vi le-am lăsat la dispoziție sau de oricare altă resursă disponibilă online / offline.

Puteți veni în continuare la cerc dacă reușiți să înțelegeți lecțiile pe care le prezint, iar eu am să încerc să vă răsplătesc pentru efortul pe care îl depuneți cu sfaturi sau cu o secțiune specială de teme pentru începători. De asemenea, dacă v-ați înscris pe Slack, mă puteți contacta oricând acolo și vă voi ajuta cu prima ocazie.

Tipuri de date

Până acum am lucrat doar cu numere întregi și pentru reprezentarea lor ne-am folosit de tipul de date int. În practică avem acces la mai multe tipuri de date și am discutat pe scurt despre următoarele: bool, char, int, long long, float, double.

Instrucțiunea for

Similar cu instrucțiunea while, instrucțiunea for ne permite să repetăm o serie de instrucțiuni cât timp se respectă o condiție. Cel mai întâlnit caz în care dorim să folosim această instrucțiune este atunci când vrem să repetăm de un număr cunoscut de pași:

for (i = 0; i < 10; ++i) { // repeta de 10 ori
  //executa...
}

for (i = 0; i < n; ++i) { // repeta de n ori
  //executa...
}

Mai multe informații despre instrucțiunea for găsiți aici.

Vectori

Uneori avem nevoie să lucrăm cu un număr mai mare de variabile de același tip. De exemplu, e posibil să vrem să citim și să memorăm 100 numere. Avem nevoie de un vector pentru acest lucru:

int v[100];

Am declarat un vector de lungime 100, care are elementele înșirate astfel:

v[0], v[1], v[2], ..., v[99]

Citirea și scrierea unui vector

#include <stdio.h>

int v[100];

int main() {
  int n, i;
  scanf("%d", &n);
  
  for (i = 0; i < n; ++i)
    scanf("%d", &v[i]);

  for (i = 0; i < n; ++i)
    printf("Elementul de pe pozitia %d este %d\n", i, v[i]);

  return 0;
}

Mai multe informații despre vectori găsiți aici.

Fișiere

Până acum am folosit doar citirea de la tastatură și scrierea pe ecran, cu funcțiile scanf și printf.

O altă metodă de a furniza date de intrare către un algoritm este să le scriem într-un fișier separat, urmând ca programul să le citească direct de acolo. Similar, algoritmul ne poate scrie rezultatul tot într-un fișier.

Declarare, deschidere și închidere fișiere

Pentru a citi datele dintr-un fișier de intrare, trebuie să parcurgem următorii pași:

• Să declarăm fișierul de intrare
• Să îl deschidem
• Să citim datele din el
• Să îl închidem la finalul programului

#include <stdio.h>

int main() {
  FILE *fin, *fout; // Declaram fisierele de intrare si de iesire
  fin = fopen("fisier.in", "r"); // Deschid fisierul de intrare, "r" - vine de la read
  fout = fopen("fisier.out", "w"); // Deschid fisierul de iesire, "w" - vine de la write

  int n;
  fscanf(fin, "%d", &n); // Citesc numarul n din fisierul de intrare

  fprintf(fout, "%d", n); // Scriu numarul n in fisierul de iesire

  fclose(fin); // Inchid fisierul de intrare
  fclose(fout); // Inchid fisierul de iesire

  return 0;
}

După cum se poate observa, metodele fscanf și fprintf se folosesc în mod similar cu cele deja bine cunoscute. Mai multe informații despre fișiere găsiți aici.

Ciurul lui Eratostene

Descriere

Ciurul lui Eratostene este un algoritm foarte eficient care se folosește în calculul numerelor prime până la o anumită valoare n. Algoritmul spune astfel:

1. Creează o listă a întregilor consecutivi de la 2 la n: [2, 3, 4, ..., n]
2. Caută primul număr p netăiat din listă (inițial nici un număr nu e tăiat).
3. Se taie din listă toate numerele din p în p, începând cu 2 * p: 2 * p, 3 * p, 4 * p, ...
4. Reia de la pasul 2, până depășim n.

Implementarea algoritmului în limbajul C / C++ (din moment ce ne folosim de tipul de date bool):

bool ciur[1000001];
...
fscanf(fin, "%d", &n);

for (d = 2; d <= n; ++d)
  if (ciur[d] == 0)
    for (i = 2 * d; i <= n; i = i + d)
      ciur[i] = 1;

Am codificat vectorul astfel:

• v[i] = 0, dacă i nu a fost tăiat; dacă i este prim
• v[i] = 1, dacă i a fost tăiat; dacă i nu este prim

Optimizare

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.

Implementarea optimizată:

bool ciur[1000001];
...
fscanf(fin, "%d", &n);

for (d = 2; d * d <= n; ++d)
  if (ciur[d] == 0)
    for (i = d * d; i <= n; i += d)
      ciur[i] = 1;

Construire vector numere prime

Uneori avem nevoie să construim un vector în care să reținem primele N numere prime, sau poate să reținem numere prime până la o anumită valoare. Ciurul lui Eratostene ne ajută să marcăm aceste numere prime, iar noi mai apoi putem să parcurgem numerele marcate de acesta și să le adaugăm într-un vector.

bool ciur[1000001];
int prim[100000];
...
fscanf(fin, "%d", &n);

for (d = 2; d * d <= n; ++d)
  if (ciur[d] == 0)
    for (i = d * d; i <= n; i += d)
      ciur[i] = 1;

k = 0;
for (i = 2; i <= n; ++i)
  if (ciur[i] == 0) {
    prim[k] = i;
    ++k;
  }

La finalul algoritmului de mai sus, vom avea primele k numere prime în vectorul prim.

Descompunere în factori primi utilizând vectorul cu numere prime

Având acces la un vector cu numere prime deja calculat, îl putem folosi pe acesta pentru a descompune în factori primi într-un mod și mai eficient.

...
i = 0;
while (i < k && prim[i] * prim[i] <= n) {
  e = 0;
  while (n % prim[i] == 0) {
    n = n / prim[i];
    ++e;
  }

  if (e > 0)
    printf("%d la puterea %d", prim[i], e);

  ++i;
}

if (n > 1)
  printf("%d la puterea 1", n);

Calcul număr divizori

Dacă descompunerea în factori primi a numărului N este:

• N = p₀^e₀ * p₁^e₁ * ... * p_k^e_k

Numărul divizorilor lui N este (e₀+1) * (e₁+1) * ... * (e_k+1).

Problema DOORS

DOORS Codechef
Am discutat o variantă naivă folosind un algoritm similar cu Ciurul lui Eratostene. Soluția optimă pleacă de la următoarea observație: la final, doar ușile care au număr impar de divizori sunt deschise. Un număr are număr impar de divizori doar dacă este pătrat perfect. Deci, problema se reduce la numărarea pătratelor perfecte între 1 și N, și anume sqrt(N).

Probleme

Am discutat mai multe probleme, aplicații la descompunerea în factori primi, scoaterea divizorilor și ciurul lui Eratostene.

Maxd
Exemplu de problemă în care este utilă optimizarea folosind ciurul lui Eratostene în calculul numărului de divizori.

Divizor si multiplu
Soluție aici [3]

Cufar
Aplicație directă a ciurului lui Eratostene, în care pentru fiecare număr nu se marchează doar dacă acesta este prim sau nu, ci se contorizează divizorii primi ai acestuia.

Temă

Temă începători

Începeți cu Lecția 7 și lucrați problemele până la lecția 11, inclusiv. De la lecția 11, ar trebui să aveți deja toate cunoștințele necesare lucrului în C. Puteți rezolva temele de pe varena, îmi scrieți pe Slack iar eu vă voi ajuta și vă voi da feedback pe ele.

Temă

Implementare:

Maxd
Divizor si multiplu
Cufar