Algopedia - User contributions [en]

Clasa a IX-a lecția 19 - 21 mar 2020

2020-11-27T06:43:13Z

Teodor: /* Optimizare: bordare matrice */

= Clasament teme lecțiile 1 - 18 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/104ca1285ae26ce3fe70bd1b8286267a/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/8095adc29786d3c2f885addce68d72ed/vectori_sortari.html Sortari] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/f79ec36c36bb08ed67d6772902db93ea/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/55bbe89cfbe81a55650f50c4f622d747/cautare_binara.html Cautare binara] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/13d068c7450228ee4716a11653189655/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/39c44cc8d4211599a254ddd05a403ca6/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/6d14cadc8935eeb6cb04418e082858d7/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/ac7ebb8ccb3f4cb5457aa4d7449ddb10/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e754613b42ae94829b108ee/21b8bdefd6c4ee5eb9a35e2f8ee241ee/oji.html Probleme OJI]

= Lecție =

== De acasă ==

Având în vedere că ne aflăm în situația de a nu putea ține cercul fizic, vă invit totuși pe fiecare dintre voi să treceți prin lecțiile pe care vi le pregătesc și să participați la concursuri și să lucrați temele pe care vi le propun.

== Recursivitate (Flood Fill) ==

După cum îi spune și numele, algoritmul Flood Fill "inundă" sau "umple" toate golurile accesibile dintr-un anumit punct.

'''Exemplu''' Avem o matrice plină de valori <tt>0</tt> și <tt>1</tt>, unde <tt>0</tt> înseamnă loc liber iar <tt>1</tt> înseamnă obstacol. Avem un omuleț care se află în căsuța liberă de la poziția <tt>(i, j)</tt> din matrice. Omulețul nostru se poate muta într-o căsuță alăturată în oricare din cele <tt>4</tt> direcții <tt>(N, S, E, V)</tt>, dacă este liberă. Vrem să numărăm câte căsuțe îi sunt accesibile.

'''Soluție''' Pornim o funcție recursivă din punctul <tt>(i, j)</tt>, care va parcurge și se va apela pentru toți vecinii liberi punctului curent, contorizându-i în același timp.

<syntaxhighlight>
int sum = 0;
void fill(int l, int c) { // sunt la pozitia l, c
++sum; // contorizez punctul curent

a[l][c] = 1; // marchez pozitia ca fiind parcursa deja / obstacol

if (l > 0 && a[l - 1][c] == 0) // ma deplasez in Nord
fill(l - 1, c);
if (l < m - 1 && a[l + 1][c] == 0) // ma deplasez in Sud
fill(l + 1, c);
if (c > 0 && a[l][c - 1] == 0) // ma deplasez in Vest
fill(l, c - 1);
if (c < n - 1 && a[l][c + 1] == 0) // ma deplasez in Est
fill(l, c + 1);
}</syntaxhighlight>

=== Exemplificare grafică ===
Sursă: [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_10_-_14_nov_2019 IQAcademy]

Să vedem niște vizualizări ale algoritmului flood fill preluate de la wikipedia: [https://en.wikipedia.org/wiki/Flood_fill algoritm flood fill]:

[[File:Recursive_Flood_Fill_4_wikipedia.gif|frame|none|Flood fill cu 4 direcții]]

[[File:Recursive_Flood_Fill_8_wikipedia.gif|frame|none|Flood fill cu 8 direcții]]

[[File:Wfm_floodfill_animation_stack_wikipedia.gif|frame|none|Exemplu mare de flood fill cu 4 direcții]]

=== Optimizare: bordare matrice ===

O optimizare clasică care ajută mai ales în claritatea codului este bordarea matricii. Această tehnică reprezintă împrejmuirea matricii cu obstacole. Mai precis, în funcție de datele de intrare, trebuie găsită o valoare cu care să se umple linia <tt>0</tt>, coloana <tt>0</tt>, linia <tt>m + 1</tt> și coloana <tt>n + 1</tt> a matricii. Astfel nu mai este nevoie să întrebăm dacă vecinul către care ne îndreptăm este sau nu în matrice.

<syntaxhighlight>
int sum = 0; // sum este initial 0, declarata global

void fill(int l, int c) { // sunt la pozitia l, c
++sum; // contorizez punctul curent

a[l][c] = 1; // marchez pozitia ca fiind parcursa deja / obstacol

if (a[l - 1][c] == 0) // ma deplasez in Nord
fill(l - 1, c);
if (a[l + 1][c] == 0) // ma deplasez in Sud
fill(l + 1, c);
if (a[l][c - 1] == 0) // ma deplasez in Vest
fill(l, c - 1);
if (a[l][c + 1] == 0) // ma deplasez in Est
fill(l, c + 1);
}
...
int main() {
...
for (j = 0; j <= n + 1; ++j) {
a[0][j] = 1; // bordez linia 0
a[m + 1][j] = 1; // bordez linia m + 1
}
for (i = 0; i <= m + 1; ++i) {
a[i][0] = 1; // bordez coloana 0
a[i][n + 1] = 1; // bordez coloana n + 1
}
...
}
</syntaxhighlight>

'''Atenție''' Trebuie să avem grijă să declarăm matricea suficient de mare pentru a face loc acestei bordări.

=== Extindere la 8 vecini ===

Este evident că acest algoritm se poate extinde ușor și în cazul în care omulețul nostru poate parcurge toate cele 8 direcții: <tt>N, S, E, V, NE, NV, SE, SV</tt>.

=== Quick tip: vectori de direcție ===

Nu este o optimizare, dar poate oferi claritate codului prin evitarea repetărilor, mai ales în cazul în care avem de apelat aceeași funcție pentru 8 direcții diferite. Vom declara doi vectori cu valori implicite în care vom reține diferențele necesare pentru a ne deplasa în toate direcțiile în care dorim:

<syntaxhighlight>
int dirl[] = {-1, 0, 1, 0};
int dirc[] = { 0, 1, 0, -1};

int sum = 0; // sum este initial 0, declarata global

void fill(int l, int c) { // sunt la pozitia l, c
++sum; // contorizez punctul curent

a[l][c] = 1; // marchez pozitia ca fiind parcursa deja / obstacol
for (d = 0; d < 4; ++d) // parcurg cele 4 directii
if (a[l + dirl[d]][c + dirc[d]] == 0) // daca este liber
fill(l + dirl[d], c + dirc[d]); // deplasez
}</syntaxhighlight>

=== Complexitate ===

Complexitate timp: O(<tt>M * N</tt>), fiecare poziție fiind vizitată cel mult o dată

Complexitate spațiu: O(<tt>M * N</tt>) suplimentar! Adică, pe lângă matricea pe care o avem deja în memorie, deoarece trebuie să reținem și stiva de recursie

== Aplicații ==

Lucrați secțiunea [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_10_-_14_nov_2019#Aplica.C8.9Bii Aplicații], citiți problemele și explicațiile.

= Temă =

[http://varena.ro/problema/oras oras - varena] 
[http://varena.ro/problema/enclave enclave - varena]

Participați la concursul de săptămâna viitoare, îl voi face public și vă voi anunța cât de curând pe Slack.

Clasa a IX-a lecția 8 - 7 dec 2019

2020-10-16T19:28:55Z

Teodor: /* Submulțimile unei mulțimi (folosind operații pe biți) */

= Clasament teme lecțiile 1 - 7 =

Am observat că aceste clasamente vă stârnesc puțin mai tare interesul de a lucra deci vi le-am făcut publice. Ca regulă, voi actualiza clasamentul la finalul fiecărei săptămâni (vineri seară, cel mai probabil).

Felicitări celor care ocupă primele locuri și mult spor tuturor la teme!!!

=== Clasamente avansați ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5deba584dff26985d150e55a/cc35ccabe3901f7e678b3ae78a37aece/avansati_iarena.html Avansați Infoarena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5deba584dff26985d150e55a/102c9df3c6350ac81164e46a48ad29ea/avansati_varena.html Avansați Varena]

=== Clasamente începători ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5deba584dff26985d150e55a/610e4536dc11737eca5c911e17a12d2b/incepatori_varena.html Începători Varena]

= Lecție =

== Caractere ==

Pe lângă citire, scriere și prelucrare de numere, calculatorul poate manipula și caractere sau șiruri de caractere. Fiecare caracter este reținut de calculator cu ajutorul unui cod, iar această codificare poartă și numele de [https://en.wikipedia.org/wiki/ASCII ASCII]. Puteți găsi [https://www.ascii-code.com/ aici] toate codurile ASCII.

=== Citirea și afișarea unui caracter ===

Există mai multe modalități de a citi și de a afișa caractere. În exemple, vom folosi funcțiile <code>fgetc</code> și <code>fputc</code>:

<syntaxhighlight>
#include <stdio.h>

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

char c;
c = fgetc(fin); // Citire caracter

fputc(c, fout); // Afisare caracter

fclose(fin);
fclose(fout);
return 0;
}
</syntaxhighlight>

Similar cum parcurgem numere consecutive cu instrucțiunea <code>for</code>, putem parcurge și caractere consecutive, cum ar fi <tt>ABCDEF...XYZ</tt>:

<syntaxhighlight>
#include <stdio.h>

int main() {
FILE *fout;
fout = fopen("fisier.out", "w");

char c;
for (c = 'A'; c <= 'Z'; ++c)
fputc(c, fout);

fclose(fout);
return 0;
}
</syntaxhighlight>

=== Citirea unui șir de caractere ===

Vrem să citim caractere din fișier până când dăm de rând nou și să le afișăm. Vom proceda astfel:

<syntaxhighlight>
#include <stdio.h>

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

char c = fgetc(fin); // Citim caracter din fisier
while (c != '\n') { // Cat timp nu am ajuns la rand nou
fputc(c, fout); // Scriem caracterul
c = fgetc(fin); // Citim urmatorul caracter
}

fclose(fin);
fclose(fout);
return 0;
}
</syntaxhighlight>

Vrem să citim din fișier un număr <tt>N</tt> de pe primul rând, urmat de <tt>N</tt> caractere pe cel de-al doilea rând:

<syntaxhighlight>
#include <stdio.h>

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

int n, i;
char c;
fscanf(fin, "%d", &n); // Citim n
fgetc(fin); // ATENTIE! Citim urmatorul caracter dupa n, caracterul \n
for (i = 0; i < n; ++i) {
c = fgetc(fin); // Citim al i-lea caracter
fputc(c, fout); // Il afisam
}

fclose(fin);
fclose(fout);
return 0;
}
</syntaxhighlight>

Vrem să citim toate caracterele din fișier, până la finalul acestuia. Pentru aceasta, există un caracter special codificat EOF (End of File):

<syntaxhighlight>
#include <stdio.h>

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

char c;
c = fgetc(fin);
// ATENTIE! Este posibil ca unele fisiere sa se termine cu: \nEOF
// Depinde de caz, este posibil sa nu vrem sa luam in considerare caracterul \n
while (c != '\n' && c != EOF) {
fputc(c, fout);
c = fgetc(fin);
}

fclose(fin);
fclose(fout);
}
</syntaxhighlight>

=== Linkuri utile ===

Mai multe despre caractere găsiți [http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_18_-_7_dec_2017 aici].

== Baze de numerație ==

=== Din baza 10 în baza 2 ===

Pentru a transforma un număr din baza 10 în baza 2, vom folosi un algoritm similar cu cel prin care extragem cifrele unui număr în baza 10:

<syntaxhighlight>
#include <stdio.h>

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

while (n > 0) {
printf("%d", n % 2);
n /= 2;
}

return 0;
}
</syntaxhighlight>

'''Atenție!''' Acest algoritm ne oferă cifrele în ordine inversă! Pentru a afișa cifrele în ordinea corectă, le putem reține într-un vector pe care îl vom răsturna.

=== Din baza 2 în baza 10 ===

<syntaxhighlight>
#include <stdio.h>

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

int n = 0;
char c = fgetc(fin);
while (c != '\n' && c != EOF) {
// c este un caracter și are un cod ASCII asociat (număr întreg)
// c - '0' este conversia de la codul ASCII la valoarea pe care o reprezintă caracterul
n = n * 2 + (c - '0');
c = fgetc(fin);
}

fprintf(fout, "%d\n", n);

fclose(fin);
fclose(fout);
}
</syntaxhighlight>

=== Generalizare ===

Procesul de transformare a unui număr din baza 10 în baza B sau din baza B în baza 10 este similar.

=== Linkuri utile ===

Mai multe despre baze de numerație găsiți [http://algopedia.ro/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_5_-_18_oct_2018 aici] și [http://algopedia.ro/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_6_-_25_oct_2018 aici].

== Submulțimile unei mulțimi ==

Vrem să afișăm toate submulțimile nevide ale mulțimii <tt>{1, 2, 3, ..., n}</tt>.

Cum abordăm această problemă? La prima vedere pare foarte grea. Va trebui, probabil, să afișăm toate submulțimile de un element. Aceasta e simplu. Apoi cele de două elemente. Tot simplu, vom selecta perechile cu două bucle for. Apoi cele cu trei elemente. Hmmm, de data asta avem nevoie de trei bucle for. Apoi de patru. Apoi de cinci. Cînd se oprește? Răspunsul depinde de n. Dar stai! Nu putem scrie un număr variabil de bucle for una într-alta!

Ne trebuie o altă abordare. Vom codifica mulțimile. Cum? Foarte simplu: folosind vectorul lor caracteristic. Pentru fiecare element al mulțimii, de la 1 la n, vom avea un element în vectorul v. Pentru o submulțime dată v[i] este 1 dacă elementul i apare în submulțime.

Acest mod de codificare demonstrează un lucru interesant: numărul de submulțimi al unei mulțimi, incluzînd mulțimea vidă, este 2n. Interesant!

Cum vom folosi acest vector? Destul de neclar. Ne-ar trebui un mod în care să variem toate elementele sale de la zero la unu. Și iar ne întoarcem la buclele for una într-alta. Dar există un mod natural în care elementele pot trece prin toate combinațiile posibile de 0 și 1: dacă în loc să folosim un vector cu n elemente folosim un număr binar cu n cifre. Dacă pornim cu numărul binar de la zero și îl incrementăm pînă ce ajungem la 2n cele n cifre ale sale vor trece prin toate configurațiile posibile. Exact ce ne dorim!

În concluzie, care este algoritmul? Iată-l descris mai jos:

1. Pentru i de la 1 la 2^n - 1
1.1 Descompune i în baza 2
1.2 Pentru fiecare cifră binară 1 care se află pe poziția j
1.2.1 Afișează j
1.3 Sfîrșit de submulțime, treci la linia următoare

Sursă: [http://algopedia.ro/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_6_-_25_oct_2018 IQ Academy]

== Operații pe biți ==

Pe lângă operatorii despre care am vorbit până acum, există și operatori care ne permit să jonglăm mai ușor cu biții unui număr (cifrele din baza 2).

{| class="wikitable"
!Operator
!Semnificație
!Exemplu
|-
| <tt><<</tt>
| Shiftare biți către stânga (înmulțire cu 2)
| <tt>x ← 1 << n</tt> (shiftăm de n ori către stânga biții lui 1, obținând în x valorea 2n)
|-
| <tt>>></tt>
| Shiftare biți către dreapta (împărțire la 2)
| <tt>x ← 20 >> n</tt> (shiftăm de n ori către dreapta biții lui 20, obținând în x valorea 20 / 2n)
|-
| <tt>&</tt>
| Operația "și" pe fiecare bit în parte
| <tt>x ← a & b</tt> (și între fiecare pereche de biți ale numerelor a și b)
|}

=== Exemple ===

* <code>1 << 10 = 1024;</code>
* <code>1 << n = 2n;</code>
* <code>1024 >> 10 = 1;</code>
* <code>1000 >> 2 = 250;</code>
* <code>5 << 2 = 20;</code>
* <code>5 & 1 = 1;</code>
* <code>x & 1 = x % 2;</code>
* <code>x & 7 = x % 8;</code>
* <code>x & (2n - 1) = x % 2n;</code>
* <code>x & 2n = 0 sau 1, al n-lea bit al lui x (din descompunerea în baza 2);</code>

== Submulțimile unei mulțimi (folosind operații pe biți) ==

Cum arată un algoritm care se folosește de regulile operațiilor pe biți prezentate mai sus pentru a genera submulțimile unei mulțimi:

1. Pentru i de la 1 la 2^n - 1
1.2. Pentru j de la 1 la n
1.2.3. Dacă al (j - 1)-lea bit al lui i este 1, afișează j
1.3. Sfârșit de submulțime, treci la linia următoare

Același lucru, dar în limbaj:

<syntaxhighlight>
#include <stdio.h>

int main() {
int n, max2, i, j;
scanf("%d", &n);

max2 = 1 << n;
for (i = 1; i < max2; ++i) {
for (j = 1; j <= n; ++j)
if ((i & (1 << (j - 1)) == 1)
printf("%d ", j);
printf("\n");
}

return 0;
}
</syntaxhighlight>

'''Atenție!''' Operațiile pe biți au prioritate mică în ordinea efectuării operațiilor. De aceea este indicat să "forțați" executarea acestora în ordinea dorită folosind paranteze (ca în exemplul anterior).

'''Performanță''' Operațiile pe biți sunt mai rapide decât operațiile simple de înmulțire sau împărțire cu puteri ale lui 2. Recomand să le folosiți unde aveți ocazia.

== Probleme ==

=== Avansați ===
[http://varena.ro/problema/puteri Puteri] 
[https://www.infoarena.ro/problema/gsr Gigel si Resturile] 
[http://varena.ro/problema/leo Leo] 
[https://infoarena.ro/problema/numere8 Numere8] 
[https://infoarena.ro/problema/reteta Reteta]

=== Începători ===
Lucrați probleme de inițiere în caractere:

[http://varena.ro/problema/numchar Numchar] 
[http://varena.ro/problema/sumacifre Sumacifre] 
[http://varena.ro/problema/alfanumeric Alfanumeric] 
[http://varena.ro/problema/fgetc Fgetc] 
[http://varena.ro/problema/plusminus Plusminus] 

Probleme cu baze de numerație:

[http://varena.ro/problema/dconv Dubla Conversie] 
[http://varena.ro/problema/monsters Monsters] 
[http://varena.ro/problema/suprapuneri Suprapuneri] 
[http://varena.ro/problema/submultimi1 Submultimi]

Clasa a IX-a lecția 22 - 03 apr 2020

2020-10-14T17:29:31Z

Teodor: /* Soluții */

= Concurs =

Ați participat la un [http://varena.ro/runda/2020-04-03-test concurs de acasă].

== Problemele din concurs ==

[http://varena.ro/problema/dwarfland Problema Dwarfland] 
[http://varena.ro/problema/scaderi Problema Scăderi]

Soluții aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_22_-_03_apr_2020]

Clasa a IX-a lecția 20 - 27 mar 2020

2020-10-14T17:26:28Z

Teodor: /* Soluții */

= Concurs =

Ați participat la un [http://varena.ro/runda/2020-03-27-test concurs de acasă].

== Problemele din concurs ==

[http://varena.ro/problema/tari Problema Țări] 
[http://varena.ro/problema/mrgary Problema Merele lui Gary] 
[http://varena.ro/problema/tripletrouble Problema Triple Trouble]

Soluții aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_20_-_27_mar_2020]

= Parsare =

La primele lecții am povestit despre cum calculăm câte operații execută un program și despre faptul că unele operații au o "greutate" mai mare asupra timpului de execuție pe care îl are programul în practică (exemplu: operațiile modulo sunt mai lente). Deși nu este prea băgată în seamă și citirea unui număr din fișier este considerată "o operație", deși nu este întocmai o singură operație. Ce este important de reținut este că citirea este o operație lentă.

Să zicem că avem de citit multe numere naturale, cum putem optimiza acest proces? Ne vom construi o funcție care citește și returnează următorul număr din fișier:

<syntaxhighlight>
// citire numar natural
int readInt() {
char ch;
int res = 0;

// eliminam caracterele de dinaintea numarului (spatiu, rand nou, orice caracter care nu este cifra)
while (!isdigit(ch = fgetc(fin)));

// adaugam cifrele la numar pana cand caracterul citit nu mai este cifra
do {
res = 10 * res + ch - '0';
} while (isdigit(ch = fgetc(fin)));

return res;
}
...
int main() {
...
// citire n si apoi n numere naturale
n = readInt();
for (i = 0; i < n; ++i)
a[i] = readInt();
}
</syntaxhighlight>

Odată ce avem deja funcția de citire scrisă, parcă e și mai ușor de folosit și mai puțin de scris decât folosind <tt>scanf</tt>!

== Utilități ==

Parsarea îmbunătățește timpul de execuție în cazul în care este necesar să citim multe numere dintr-un fișier, indiferent dacă suntem sau nu la vreun concurs, olimpiadă sau dacă lucrăm la un proiect personal.

Legat strict de concursuri, deși majoritatea problemelor au timp de execuție suficient încât o soluție bună să treacă testele și fără parsare, este posibil ca alte probleme să aibă timpul de execuție mai strict, pentru a diferenția soluții ineficiente sau mici neatenții în scrierea codului. Parsare este deci o practică bună și destul de simplă încât să o putem folosi pe viitor, unde este cazul.

În cazul concursului de astăzi, cred ca unii dintre voi ați fi beneficiat de folosirea acestei tehnici, în special în rezolvarea problemei [http://varena.ro/problema/tripletrouble Triple Trouble]. Se putea totuși lua <tt>100</tt> puncte și fără, sursa oficială nefolosindu-se de parsare.

Clasa a IX-a lecția 18 - 14 mar 2020

2020-10-14T17:23:47Z

Teodor: /* Concurs (de acasă) */

= Clasament teme lecțiile 1 - 17 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/a0120e6234a60d79dad6e453505d1eb9/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/14f082d4e471ca50d9572fc5f546aa92/vectori_sortari.html Sortari] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/e7eb6d8f6ca456e7d7649f06e088c761/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/041b6a6c392d80a22e7f612f9d46a258/cautare_binara.html Cautare binara] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/ee23774bbd6cdb45bdb5b8d93bcb8834/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/2a9c33c04605224b419aac8db521c29d/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/311ae534309fe7661feb32434d3f4509/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/921fbbe425e353d10948fe1bc597e066/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e6caa8e2b171309a52ea004/57cf7bcd3c0cf9be0642c4d5f02b7703/oji.html Probleme OJI]

= Lecție =

== Concurs (de acasă) ==

Ați participat la un concurs cu 3 probleme: [http://varena.ro/runda/2020-03-12-test9 Concurs clasa a 9-a (de acasă)].

=== Div & Mul ===

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_18_-_14_mar_2020#Div_.26_Mul]

'''Teste''' Primele teste au fost grupate pentru a diferenția soluțiile ineficiente din punct de vedere al timpului de execuție.

=== Numere aproape prime ===

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_18_-_14_mar_2020#Numere_aproape_prime]

'''Atenție''' Aveți grijă când declarați vectori, uitați-vă întotdeauna și la limitele de memorie! Nu declarați vectorii mai mari decât aveți nevoie și nu folosiți tipuri de date mari unde nu este necesar. Dezobișnuiți-vă din a folosi <tt>int</tt> peste tot, există și alte tipuri de date.

=== Dreptunghiurile lui Gary ===

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_18_-_14_mar_2020#Dreptunghiurile_lui_Gary]

= Temă =

[http://varena.ro/problema/divsimul Div & Mul] 
[http://varena.ro/problema/nraprime Numere aproape prime] 
[http://varena.ro/problema/drgary Dreptunghiurile lui Gary]

Participați la [https://www.infoarena.ro/runda/fmi-no-stress-9-warmup FMI No Stress 9 Warm-Up]. Acesta este un concurs pentru studenți, conține probleme cu grad variat de dificultate. Uitați-vă pe clasament ca să urmăriți în timp real ce probleme sunt făcute, nu vă blocați pe o problemă cu orele. Este posibil ca unele probleme să necesite structuri de date / tehnici despre care încă nu ați învățat.

Clasa a IX-a lecția 15 - 15 feb 2020

2020-10-14T17:20:37Z

Teodor: /* Aplicații */

= Clasament teme lecțiile 1 - 14 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/298069aebf6c268e42976c9758d0da5d/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/86fd8ebc0d9eadf0d4ef1b2ba4fda4ee/vectori_sortari.html Sortari] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/b93681f76b30710f24d5142ae22346d0/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/39bbdfeebfb067d8e0ee8abb308695f5/cautare_binara.html Cautare binara] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/dac4c60d5b479c5b592f2c2b7545e150/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/7397809b6a39a21a9f6ab779afc952a2/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/23dd3c8357a35616e84d425613d9dc9e/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e4952258886b76d9c35c170/6458e9d51a76730f111f4edecedd9406/oji.html Probleme OJI]

= Lecție =

== Stivă ==

Am mai auzit de acest termen în lecțiile de la început, când v-am dat exemple de memoria "globală" versus cea de pe stivă. Pe lângă vectori, stiva este prima structură de date mai "specială" despre care învățăm.

=== Definiție ===

Stiva este o structură de date de tip LIFO ''(last in, first out)''. Asta înseamnă că elementele sunt adăugate în ordine (ca într-un vector obișnuit), dar ele trebuiesc scoase în ordinea inversă adăugării lor. Un exemplu bun de structură de stivă din viața reală este un teanc de farfurii: putem oricând să adăugăm o farfurie în teanc deasupra tuturor celorlalte, dar dacă vrem să începem să scoatem farfurii din teanc, va trebui să începem cu ultima farfurie adăugată (în practică putem să scoatem și farfurii care au fost adăugate mai devreme, dar de dragul teoriei vom presupune că acestea sunt foarte fragile și este interzis să facem asta).

=== Implementare ===

Având în vedere definiția stivei, în implementarea structurii de date de tip stivă sunt în general necesare următoarele operații:
* push(value) - inserează o valoare în capătul stivei
* pop - șterge valoarea din capătul stivei
* top - returnează valoarea din capătul stivei
* size - returnează numărul de elemente din stivă

Exemplu implementare (sursă [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_2_-_26_sep_2019 IQAcademy]):

<syntaxhighlight>
#define MAXN 1000

int stack[MAXN]; // stocarea valorilor propriu-zise
int stack_pointer = 0; // indice la prima valoare nefolosita in vector (totuna cu numărul de elemente din stiva)

// adauga valoarea 'val' la stiva, daca aceasta nu este plina
// returneaza 1 in caz de succes, 0 in caz de stiva plina
int push( int val ) {
if ( stack_pointer >= MAXN ) // stiva este plina?
return 0; // returnam eroare

stack[stack_pointer++] = val; // adaugam valoarea in stiva
return 1; // returnam succes
}

// returnează valoarea aflată în virful stivei, dacă ea exista
// in caz contrar returneaza -1
int top() {
return stack_pointer > 0 ? stack[stack_pointer - 1] : -1;
}

// elimina ultimul element din stiva daca se poate
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
if ( stack_pointer == 0 ) // testam cazul de eroare
return 0;

stack_pointer--; // daca avem elemente pe stiva, il eliminam pe ultimul
return 1;
}

// returneaza numarul de elemente din stiva
int size() {
return stack_pointer;
}
</syntaxhighlight>

=== Aplicații ===

[http://varena.ro/problema/paranteze1 paranteze1 - varena] 
[https://www.infoarena.ro/problema/parantezare parantezare - infoarena]

Soluții aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_15_-_15_feb_2020#Aplica.C8.9Bii]

= Temă =

[http://varena.ro/problema/paranteze1 paranteze1 - varena] 
[https://www.infoarena.ro/problema/parantezare parantezare - infoarena] 
[http://varena.ro/problema/bile2 bile2 - varena] 
[http://varena.ro/problema/turn turn - varena] 
[https://infoarena.ro/problema/trompeta trompeta - infoarena]

Clasa a IX-a lecția 5 - 16 nov 2019

2020-10-14T17:19:49Z

Teodor: /* Probleme */

= Lecție =

== Cuvânt înainte ==

Am observat mai multe cazuri de elevi care nu își fac temele. Dacă nu vă faceți temele și nu lucrați, nu veți progresa la acest cerc. Profitați de faptul că aveți în fața voastră un om cu puțin mai multă experiență decât voi în programare care este disponibil să vă ajute să vă dezvoltați în acest domeniu. Nu vă ies problemele? Aveți nevoie de ajutor? Aveți adresa mea de Slack, scrieți-mi, profitați de mine și de disponibilitatea mea.

Cei care au teme restante, vreau să le văd făcute până data viitoare. Din nou: Nu vă ies? Nici o problemă, sunteți aici să învățați lucrând și greșind iar eu sunt aici să vă ajut.

== Descărcare teste ==

Această secțiune este în principal pentru cei începători. Să zicem că nu luați 100 puncte pe o problemă și deși ați încercat să vă dați multe teste, nu reușiți să vă dați seama ce este greșit. Pe lângă varianta de a îmi scrie și de a îmi cere ajutorul, sunt câteva probleme la care aveți acces direct la teste. Vedeți pe ce test vă dă rezultat greșit, luați fișierele <tt>.in</tt> și <tt>.ok</tt> de la acel test și comparați rezultatul cu al vostru.

'''Important''' 
Este important să nu abuzați de asta. Învățați să vă dați teste singuri, este o abilitate importantă pe care trebuie să o dezvoltați!

== Problemă încălzire ==
Se dau două numere <tt>N</tt> și <tt>K</tt>. Să se afișeze exponentul lui <tt>K</tt> din descompunerea în factori primi ai lui <tt>N!</tt>.

'''Soluție''' 
Avem:
* <tt>N! = 1 * 2 * 3 * ... * K * (K + 1) * ... * (2 * K) * ... * N</tt>

Din produsul de mai sus, singurele numere care influențează exponentul lui <tt>K</tt> sunt multiplii de <tt>K</tt>. Mai mult de atât:
* Fiecare multiplu de <tt>K</tt> influențează exponentul cu <tt>1</tt>. În total avem <tt>N / K</tt> multiplii de <tt>K</tt>.
* Fiecare multiplu de <tt>K2</tt> influențează exponentul cu încă <tt>1</tt> factor față de multiplii de <tt>K</tt>. În total avem <tt>N / K2</tt> multiplii de <tt>K2</tt>.
* ...

Deci, rezultatul problemei este:
* <tt>N / K + N / K2 + N / K3 + ...</tt>

O metodă simplă și elegantă de a scrie acest lucru:

<syntaxhighlight>
...
exponent = 0;
while (n >= k) {
exponent += n / k;
n /= k;
}

printf("%d\n", exponent);
</syntaxhighlight>

La temă veți avea o problemă care se folosește de această tehnică.

== Vectori caracteristici ==

Vectorii caracteristici sunt folosiți pentru a marca dacă un număr apare sau nu într-o anumită entitate (secvență de numere, mulțime, etc.) sau dacă un număr are sau nu o anumită proprietate (dacă este prim, de exemplu). După cum le spune și numele, ei sunt folosiți pentru a reține dacă un număr are sau nu o anumită caracteristică. Am folosit o variantă a vectorilor caracteristici la implementarea ciurului lui Eratostene. Astăzi îi vom aplica în mai multe probleme.

De exemplu, dacă am un șir de numere: <tt>2, 7, 5, 1, 2, 6, 7</tt> și vreau să știu care din numerele de la <tt>1</tt> la <tt>10</tt> se găsesc în această mulțime, pot construi un vector caracteristic care va arăta așa: 
<tt>| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |</tt> 
<tt>| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |</tt>

== Vectori de frecvență ==

Vectorii de frecvență sunt folosiți pentru a marca numărul de apariții ale unui număr într-o anumită entitate. Vectorul de frecvență pentru exemplul anterior ar arăta astfel: 
<tt>| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |</tt> 
<tt>| 0 | 1 | '''2''' | 0 | 0 | 1 | 1 | '''2''' | 0 | 0 | 0 |</tt>

Se observă că <tt>2</tt> și <tt>7</tt> apar de două ori.

== Sortare vector ==

Vectorii pot fi sortați prin mai multe modalități, de multe dintre acestea ați auzit și voi și din câte am înțeles, pe unele știți să le implementați deja. O să încep prin a prezenta o sortare în complexitate <tt>O(N2)</tt>.

=== Sortare prin selecție ===

Acest algoritm de sortare se bazează pe faptul că la fiecare pas vom selecta minimul / maximul din vector și îl vom pune în poziția corespunzătoare: primul / ultimul element din șir.

<syntaxhighlight>// 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;
}</syntaxhighlight>

Complexitatea algoritmului este <tt>O(N2)</tt>. Diferența dintre acest algoritm și cel mai "popular" algoritm de sortare în aceeași complexitate (bubble-sort) este constanta cu care se înmulțeste numărul de pași în practică. Chiar dacă în teorie au aceeași complexitate, algoritmul de sortare prin selecție performează mai bine în practică.

=== Sortare în complexitate <tt>O(N*logN)</tt> ===

Vom vorbi despre algoritmii de sortare Merge Sort și Quick Sort mai târziu în acest curs.

=== Sortare prin vectori de frecvență ===

Vectorii de frecvență sunt minunați când trebuie să sortăm un vector cu multe elemente ale cărui elemente se află într-un interval de lungime mică. De exemplu, dacă elementele vectorului pot lua valori din intervalul <tt>[1, 100], [1, 1000], [9000, 10000], etc.</tt> Evident, trebuie să ținem cont și de dimensiunea vectorului.

Complexitatea de timp a algoritmului este <tt>O(N + V)</tt>, unde <tt>N</tt> este numărul de elemente din vector iar <tt>V</tt> este lungimea intervalului din care elementele fac parte. Spre deosebire de sortarea prin selecție, acest algoritm are și o complexitate adițională de memorie egală cu <tt>O(V)</tt>.

Este indicat să folosim acest algoritm când avem suficientă memorie la dispoziție și când <tt>N + V < N2</tt> (respectiv <tt>N + V < N * logN</tt>, în cazul în care folosim un algoritm de complexitate optimă). Un exemplu de implementare:

Se dă un vector <tt>V</tt> cu <tt>N</tt> elemente. Se știe că elementele vectorului sunt din intervalul <tt>[0, 100]</tt>, iar <tt>1 <= N <= 1000000</tt>. Să se afișeze elementele vectorului în ordine crescătoare.

<syntaxhighlight>
#include <stdio.h>

int v[1000000], freq[101];

int main() {
int n, i, j;
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &v[i]);
++freq[v[i]]; // contorizez o aparitie a lui v[i]
}

for (i = 0; i <= 100; ++i) // parcurg tot intervalul
for (j = 0; j < freq[i]; ++j) // afisez numarul din interval de cate ori apare
printf("%d ", i);

return 0;
}
</syntaxhighlight>

=== Sortare STL ===

În C++, există o librărie de algoritmi care are câțiva algoritmi generici gata implementați. Aceasta se numește <code><algorithm></code> și conține o funcție de sortare în complexitate optimă <tt>O(N logN)</tt>, care se folosește astfel:

<syntaxhighlight>
#include <stdio.h>
#include <algorithm> // includem libraria algorithm

// trebuie inclus pentru a recunoaste functiile din librarie
// mai multe despre namespace la un search pe google
using namespace std;

int v[1000000];

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

// sortez vectorul incepand cu pozitia 0 inclusiv, pana la pozitia n exclusiv.
sort(v, v + n); // sau: sort(v + 0, v + n);

for (i = 0; i < n; ++i)
printf("%d ", v[i]);

return 0;
}
</syntaxhighlight>

==== Important ====

Acesta este un algoritm eficient și vă recomand să îl folosiți la olimpiadă de oricâte ori aveți nevoie de o sortare în complexitate <tt>O(N logN)</tt>. '''De reținut că sunt totuși cazuri în care algoritmul de sortare prin vectori de frecvență este mai eficient!'''

Pe lângă olimpiadă am pretenția de la voi să știți să și implementați algoritmii de sortare predați aici, nu doar să îi folosiți pe cei gata implementați. Sunteți aici să învățați programare de-a binelea, nu doar să învățați să folosiți câteva funcții care vă sunt puse la dispoziție de limbaj.

== Probleme ==

[http://varena.ro/problema/subsecventa Subsecventa] 
[https://infoarena.ro/problema/nrtri Nrtri] 
[http://varena.ro/problema/ploaie Ploaie] 
[https://infoarena.ro/problema/livada Livada] 
[https://infoarena.ro/problema/cool Cool] 

Soluții aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_5_-_16_nov_2019#Probleme]

= Temă =

=== Temă începători ===

Rezolvați probleme restante din temele trecute. Cereți-mi ajutorul dacă aveți nevoie.

Problemă bonus: [http://varena.ro/problema/rude Rude]

=== Temă avansați ===

Implementare probleme:

[http://varena.ro/problema/subsecventa Subsecventa] 
[https://infoarena.ro/problema/nrtri Nrtri] 
[http://varena.ro/problema/ploaie Ploaie] 
[https://infoarena.ro/problema/livada Livada] 
[https://infoarena.ro/problema/cool Cool]

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

2020-10-04T17:31:03Z

Teodor: /* Probleme */

= Rezolvare probleme lecția anterioară =

Soluții aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_3_-_26_oct_2019#Rezolvare_probleme_lec.C8.9Bia_anterioar.C4.83]

= Lecție =

=== Problemă încălzire ===

Se dau două șiruri de câte <tt>N</tt> numere naturale. Să se spună câte numere <tt>K</tt> există care respectă următoarele proprietăți:
* <tt>K</tt> se divide cu toate numerele din primul șir.
* Toate numerele din al doilea șir se divid cu <tt>K</tt>.

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_3_-_26_oct_2019#Problem.C4.83_.C3.AEnc.C4.83lzire]

== 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 [http://algopedia.ro/wiki/index.php/Cercul_de_informatic%C4%83_gimnaziu 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 <code>int</code>. În practică avem acces la mai multe tipuri de date și am discutat pe scurt despre următoarele: <code>bool, char, int, long long, float, double</code>.

=== 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:

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

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

Mai multe informații despre instrucțiunea for găsiți [http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_13_-_4_nov_2014 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:
<syntaxhighlight>int v[100];</syntaxhighlight>

Am declarat un vector de lungime 100, care are elementele înșirate astfel:
<syntaxhighlight>v[0], v[1], v[2], ..., v[99]</syntaxhighlight>

=== Citirea și scrierea unui vector ===

<syntaxhighlight>
#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;
}
</syntaxhighlight>

Mai multe informații despre vectori găsiți [http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_21_-_13_ian_2015 aici].

=== Fișiere ===

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

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

<syntaxhighlight>
#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;
}
</syntaxhighlight>

După cum se poate observa, metodele <code>fscanf</code> și <code>fprintf</code> se folosesc în mod similar cu cele deja bine cunoscute. Mai multe informații despre fișiere găsiți [http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_11_-_21_oct_2014 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:
# Creează o listă a întregilor consecutivi de la <tt>2</tt> la <tt>n</tt>: <tt>[2, 3, 4, ..., n]</tt>
# Caută primul număr <tt>p</tt> netăiat din listă (inițial nici un număr nu e tăiat).
# Se taie din listă toate numerele din <tt>p</tt> în <tt>p</tt>, începând cu <tt>2 * p</tt>: <tt>2 * p, 3 * p, 4 * p, ...</tt>
# Reia de la pasul 2, până depășim <tt>n</tt>.

Implementarea algoritmului în limbajul <tt>C / C++</tt> (din moment ce ne folosim de tipul de date <code>bool</code>):
<syntaxhighlight>
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;
</syntaxhighlight>

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:

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

Implementarea optimizată:

<syntaxhighlight>
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;
</syntaxhighlight>

=== Construire vector numere prime ===

Uneori avem nevoie să construim un vector în care să reținem primele <tt>N</tt> 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.

<syntaxhighlight>
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;
}
</syntaxhighlight>

La finalul algoritmului de mai sus, vom avea primele <code>k</code> 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.

<syntaxhighlight>
...
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);
</syntaxhighlight>

=== Calcul număr divizori ===

Dacă descompunerea în factori primi a numărului N este:
* <tt>N = p0e0 * p1e1 * ... * pkek</tt>

Numărul divizorilor lui <tt>N</tt> este <tt>(e0+1) * (e1+1) * ... * (ek+1)</tt>.

== Problema DOORS ==

[https://www.codechef.com/BTCD2012/problems/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 <tt>1</tt> și <tt>N</tt>, și anume <tt>sqrt(N)</tt>.

== Probleme ==

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

[https://www.infoarena.ro/problema/maxd Maxd] Exemplu de problemă în care este utilă optimizarea folosind ciurul lui Eratostene în calculul numărului de divizori.

[https://infoarena.ro/problema/divmul Divizor si multiplu] Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_3_-_26_oct_2019#Probleme]

[https://infoarena.ro/problema/cufar 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 [http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_7_-_23_sep_2014 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:

[https://www.infoarena.ro/problema/maxd Maxd] 
[https://infoarena.ro/problema/divmul Divizor si multiplu] 
[https://infoarena.ro/problema/cufar Cufar]

Clasa a IX-a lecția 4 - 2 nov 2019

2020-10-02T21:36:55Z

Teodor: /* Problema Divizori Primi */

= Rezolvare probleme lecția anterioară =

=== Problema cufăr ===
Problema [https://infoarena.ro/problema/cufar Cufăr] este singura problemă de la temă pe care nu am discutat-o în detaliu în timpul cursului.

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_4_-_2_nov_2019#Problema_cuf.C4.83r]

= Lecție =

== Pentru începători ==

Am lucrat în continuare de pe algopedia și am trimis primele surse pe varena (problemele [http://varena.ro/problema/balaur Balaur] și [http://varena.ro/problema/lascoala La Școală]).

== Pentru avansați ==
=== Problema Oz ===

[https://www.infoarena.ro/problema/oz Oz]

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_4_-_2_nov_2019#Problema_Oz]

=== Problema Cmmdc2 ===

[https://www.infoarena.ro/problema/cmmdc2 Cmmdc2]

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_4_-_2_nov_2019#Problema_cmmdc2]

Pentru că am avut elevi care au rezolvat rapid cele două probleme propuse de mai sus, am mai pus la bătaie încă două probleme.

=== Problema NrDivUnique ===

[https://infoarena.ro/problema/nrdivunique NrDivUnique]

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_4_-_2_nov_2019#Problema_NrDivUnique]

=== Problema Divizori Primi ===

[https://infoarena.ro/problema/divprim Divizori Primi] 
'''Vom reveni la această problemă și la tehnicile nediscutate încă la curs în curând.'''

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_4_-_2_nov_2019#Problema_Divizori_Primi]

= Temă =

=== Temă începători ===
Am încercat să aranjez problemele în ordinea dificultății:

[http://varena.ro/problema/reuniune Reuniune] 
[http://varena.ro/problema/lascoala La școală] 
[http://varena.ro/problema/minute Minute] 
[http://varena.ro/problema/ucif Ucif] 
[http://varena.ro/problema/prim Prim] 
[http://varena.ro/problema/test Test] 

=== Temă avansați ===
Implementare:

[https://www.infoarena.ro/problema/oz Oz] 
[https://www.infoarena.ro/problema/cmmdc2 Cmmdc2] 
[https://infoarena.ro/problema/nrdivunique NrDivUnique] 
[https://infoarena.ro/problema/divprim Divizori Primi] Pentru cei puternici ;)

Clasa a IX-a lecția 1 - 12 oct 2019

2020-09-22T19:44:21Z

Teodor: /* Probleme de gândire */

= Introducere =
== Prezentarea instructorului ==
Numele meu este Teodor Plop și voi susține acest curs de informatică. Sunt un fost elev al liceului Tudor Vianu, sunt pasionat de programare, grafică și jocuri pe calculator iar de mai bine de 5 ani de zile lucrez ca programator în industria jocurilor din România.

== Prezentarea cercului ==
Cercul are ca scop dezvoltarea gândirii algoritmice și logice, punerea bazelor informaticii și aprofundarea ei la cel mai înalt nivel, incluzând evident și materia de olimpiadă. Pentru a da o șansă și celor care nu au avut tangență cu informatica pânâ în această clasă, voi incepe informatica de la zero, având câteva lecții de introducere. Țin să îi asigur pe cei care au deja experiență în ale informaticii că au ce învăța de la acest curs și că dificultatea acestuia le va atinge așteptările.

=== Structura cercului ===
Vom avea ~3 lecții de introducere în algoritmică, în care vom rezolva probleme folosind scheme logice. Apoi, vom susține un test de selecție în urma căruia se va forma grupa alături de care vom continua cercul, care va conține în mod ideal maxim 15 elevi. Nivelul de performanță al cercului este unul înalt și este imposibil să atingem acest nivel având un număr mare de studenți.
Dupa testul de selectie vom intra in limbajul C si in materia propriu-zisa.

=== Reguli ===
Cercul este opțional. Eu vă promit că am sa dedic timp și efort în pregătirea voastră. Deci, mă aștept să văd implicare și efort și din partea voastră. Veniți la acest cerc doar dacă vreți să învățați ceva în plus, ceva nou, ceva ce vă place suficient de mult încât sa fiți serioși și dedicați. Nu vă ține nimeni cu forța aici și singurul lucru pe care îl obtineți dacă veniți contra voinței proprii este timp pierdut.

Acestea fiind spuse, regulile cercului:
* Prezența
** Prezența este obligatorie
* Seriozitate, implicare & dorința de a învăța
** Tratați cercul cu seriozitate
** Aveți o atitudine pozitivă (Pot și '''vreau''' să fac asta!)
** Temele sunt obligatorii

=== Grup de discuții ===
Am creat un grup de Slack la care înscrierea este obligatorie pentru cei care vin la cercul de informatică, și opțională pentru ceilalți. Vom folosi grupul în două scopuri:
* Pentru a face anunțuri oficiale.
* Pentru a vă corecta temele și a vă oferi sfaturi individual.
Veți primi invitații pe adresele voastre de mail.

= Lecție =
== Algoritmi ==
=== Definiție ===
Algoritm = set de instrucțiuni sau reguli care, pornind cu un set de date inițiale, rezolvă o clasă de probleme folosind operații precise, executate mecanic, fără intervenția creativă a omului.

=== Exemple ===
Rețete de bucate, instrucțiuni asamblare IKEA, ...

=== Proprietăți ===
# '''Precizie''' - Sau neambiguitate. Fiecare pas trebuie să fie neambiguu și executabil fără intervenție creativă.
# '''Generalitate''' - Să rezolve o clasă de probleme, nu doar o problemă în particular.
# '''Finitudine''' - Algoritmul trebuie să se termine în timp finit. Din punct de vedere practic trebuie să se termine într-un timp rezonabil.
# '''Corectitudine''' - Rezultatul final trebuie să fie corect pentru toate datele de intrare.

== Scheme logice ==
Schemele logice sunt un mod de descriere a algoritmilor (un alt mod este pseudocodul). Ele conțin următoarele blocuri:

<gallery widths=76px>
File:flow-assign.gif|'''Bloc de calcul'''
File:flow-io.gif|'''Bloc de citire sau scriere'''
File:flow-decision.gif|'''Bloc de decizie'''
File:flow-terminator.gif|'''Bloc terminator'''
</gallery>

=== Bloc terminator ===
Singurul rol al acestui bloc este de a marca începutul și sfârșitul algoritmului. Iată cele două blocuri pe care le vom folosi:

* [[Image:Flow-terminator-example-01.gif]] este locul unde începe schema logică.
* [[Image:Flow-terminator-example-02.gif]] este locul unde se termină schema logică.

=== Bloc de citire/scriere ===
Aceste blocuri controlează fluxul de date către și dinspre algoritmul nostru.
* '''Citire''' = furnizăm algoritmului setul de date inițial de care are nevoie pentru a rezolva problema.
* '''Scriere''' = algoritmul ne întoarce rezultatele.

Exemple:
* [[Image:sl-citire-x.gif]] citește o valoare și o depozitează în <code>x</code>. 'C' vine de la 'citește'.
* [[Image:sl-citire-x-y.gif]] citește două valori, una ce va fi depozitată în <code>x</code> iar a doua în <code>y</code>.
* [[Image:sl-scriere-y.gif]] scrie valoarea stocată în <code>y</code>. 'S' vine de la 'scrie'.

=== Bloc de calcul ===
Așa cum sugerează și numele, aceste blocuri sunt folosite pentru a calcula expresii. De obicei conțin calcule matematice. Exemple:

* [[Image:Flow-assign-example.gif]] calculează expresia <code>2 + 3</code> și stochează rezultatul (în acest caz <code>5</code>) în <code>x</code>.
* [[Image:Flow-assign-example-02.gif]] ia vechea valoare a lui x <code>x</code>, îi adună <code>1</code> și stochează rezultatul în variabila <code>x</code>, suprascriind vechea valoare. Dacă <code>x</code> era <code>5</code> inițial, valoarea finală va fi <code>6</code>, după execuția acestui bloc.

=== Bloc de decizie ===
Un bloc de decizie este folosit în momentul în care vrem să acționăm diferit în funcție de o anumită expresie. Dacă expresia este adevărată execuția algoritmului continuă pe ramura din dreapta. Dacă expresia este falsă execuția continuă cu ramura din stînga.
Putem considera că acest bloc "pune o întrebare". Dacă răspunsul întrebării este pozitiv, algoritmul se continuă cu ramura din dreapta. Dacă răspunsul este negativ, cu ramura din stânga.

* [[Image:sl-test-x-10.gif]] testează dacă <code>x</code> este mai mic ca zece, atunci cînd se ajunge în acest punct al algoritmului. Dacă <code>x</code> este mai mic ca zece continuăm cu blocurile de pe ramura dreaptă. Dacă <code>x</code> este mai mare ca zece, sau egal cu zece, continuăm cu ramura din stînga.
* [[Image:Flow-decision-example-02.gif]] testează dacă valoarea lui <code>x</code> este mai mare sau egală cu valoarea lui <code>y</code> plus <code>3</code>. În acest caz continuăm pe ramura din dreapta. Dacă nu, continuăm pe ramura din stânga.

=== Exemplu: distanța până la Stormwind ===
Orașul Stormwind se află pe autostrada A1 la kilometrul 60. Se știe că noi ne aflăm pe autostradă la kilometrul k (k citit). La ce distanță de Stormwind ne aflăm? Să construim o schemă logică care o calculează (vezi figura de mai jos).

Pentru a executa o schemă logică pornim de la blocul de '''START''' si urmăm săgețile. Primul pas este să citim <code>k</code>, kilometrul la care ne aflăm pe autostradă. Apoi vom testa dacă am depășit Stormwind, adică dacă am trecut de kilometrul 60. Dacă <code>k</code> este mai mare decît 60 o vom lua pe ramura din dreapta, numită și ramura <code>DA</code>, unde vom calcula distanța <code>d</code> ca fiind valoarea <code>k - 60</code>. Dacă <code>k</code> este mai mic sau egal cu 60 vom urma ramura din stînga (ramura <code>NU</code>) unde vom calcula distanța ca fiind <code>60 - k</code>. Indiferent ce ramură am urmat vom ajunge în final la conectorul cerculeț. În acest moment <code>d</code> conține valoarea corectă a distanței. Tot ce mai avem de făcut este să o afișăm, după care ne oprim la blocul '''STOP'''.

[[Image:stormwind.gif|frame|none|Distanța până la Stormwind]]

== Programarea structurată ==
Programarea structurată este un mod de a scrie scheme logice care îmbunătățește claritatea, citibilitatea, calitatea și ușurința modificării ulterioare. Denumirea vine de la ''Programarea cu structuri''. Mai exact, programarea structurată ne limitează modul în care putem folosi și îmbina blocurile. Ele pot fi aranjate în trei feluri distincte, conform unor modele numite structuri. În continuare vom studia două dintre aceste structuri.
=== Structura liniară ===
Se mai numește și structură de calcul. Ea constă dintr-o înșiruire de blocuri de calcul și blocuri de citire/scriere.
[[Image:sl-structura-liniara.gif|frame|none|Structura liniară]]

=== Structura alternativă ===
Structura alternativă este compusă dintr-un bloc de decizie, două ramuri de execuție, ''DA'' și ''NU'', care se reunesc la final.
[[Image:sl-structura-alternativa.gif|frame|none|Structura alternativă]]

=== Structura repetitivă de tip WHILE-DO ===
Structura repetitivă de tip WHILE-DO (câtă vreme - execută) este o structură în care câtă vreme condiția <nowiki><cond></nowiki> este adevărată se execută prelucrarea <nowiki><prel></nowiki>, după care se revine înaintea blocului de decizie. Atunci când <nowiki><cond></nowiki> devine falsă se iese din structură: [[Image:sl-while-do.gif|frame|none|Structura repetitivă de tip WHILE-DO]]

== Operatori ==
Vom enumera principalii operatori pe care îi vom folosi în scheme logice.

=== Operatori aritmetici ===
Operatorii aritmetici pe care îi putem folosi în blocurile de calcul sunt:
{| class="wikitable"
!Operator
!Semnificație
!Exemplu
|-
| <tt>+</tt>
| Adunarea a două numere
| <tt>x ← a + b</tt>
|-
| <tt>-</tt>
| Scăderea a două numere
| <tt>y ← y - 10</tt>
|-
| <tt>*</tt>
| Înmulțirea a două numere
| <tt>x ← a * 10</tt>
|-
| <tt>/</tt>
| Împărțirea întreagă a două numere (cîtul împărțirii)
| <tt>x ← 14 / 3</tt> (<tt>x</tt> primește valoarea 4)
|-
| <tt>%</tt>
| Împărțirea întreagă a două numere (restul împărțirii)
| <tt>x ← 14 % 3</tt> (<tt>x</tt> primește valoarea 2)
|-
| <tt>( )</tt>
| Paranteze: schimbul ordinii operațiilor
| <tt>x ← 2 * (10 - (3 + 4))</tt> (<tt>x</tt> primește valoarea 6)
|-
| <tt> __ √</tt>
| Radical: partea întreagă a operațiunii radical
| <tt>     __ x ← √10</tt> (<tt>x</tt> primește valoarea 3)
|}
=== Operatori de comparație și logici ===
Operatori de comparație și logici: <tt>= ≠ < ≤ > ≥ și sau</tt>

== Probleme ==

=== Testul de divizibilitate ===
Testul de divizibilitate <tt>n</tt> cu <tt>k</tt>, discuție cele două metode, prima folosind operatorul <tt>%</tt>, a doua folosind operatorul <tt>/</tt>.

{|
| [[Image:sl-n-div-k-var-1.gif|frame|none|n divizibil cu k, varianta 1]]
| [[Image:sl-n-div-k-var-2.gif|frame|none|n divizibil cu k, varianta 2]]
|}

=== Extragerea ultimei cifre ===
Să se afișeze ultima cifră a unui număr n, folosind operatorul '%', respectiv restul împărțirii la 10. Am demonstrat că restul împărțirii la 10 este ultima cifră a unui număr.
[[Image:sl-ultima-cifra.gif|frame|none|Ultima cifră a lui n]]

=== Extragerea primei cifre ===
Se citește n, un număr natural strict mai mic decît 100. Să se afișeze prima cifră a lui n. [[Image:prima-cifra.gif|frame|none|Prima cifră a lui n, n < 100]]

=== Cifrele unui număr în ordine inversă ===
Se dă un număr <tt>n</tt> între zero și 999 inclusiv. Să se afișeze cifrele lui în ordine inversă. [[Image:sl-nr-3-cifre.gif|frame|none|Afișare cifre număr în ordine inversă (0 ≤ n ≤ 999)]]

=== Strângeri de mână ===
Avem <tt>n</tt> oameni care dau mâna fiecare cu fiecare o singură dată. În total sunt <tt>k</tt> strângeri de mână. Să se scrie o schemă logică care citește <tt>k</tt> (numărul de strângeri de mînă), apoi calculează și afișează <tt>n</tt> (numărul de oameni).

'''Soluție''' Avem în total <code>n * (n - 1) / 2</code> strângeri de mână. Egalând, obținem <code>n * (n - 1) / 2 = k</code>, rezultă <code>n * (n - 1) = 2 * k</code>. Deci <code>n - 1 = sqrt(2 * k)</code>, rezultă <code>n = 1 + sqrt(2 * k)</code>.
[[Image:sl-stringeri-de-mina.gif|frame|none|n oameni dau mâna. Sunt k strângeri de mână. Dându-se k să se calculeze n.]]

=== Maximul a trei numere ===
Se citesc trei numere, <tt>a</tt>, <tt>b</tt> și <tt>c</tt>. Să se afișeze valoarea maximă.
{|
| valign="top"| [[Image:sl-max-3-nr-1.gif|frame|none|maximul a trei numere, varianta 1]]
| valign="top"| [[Image:sl-max-3-nr-2.gif|frame|none|maximul a trei numere, varianta 2]]
|}

=== Laturile unui triunghi ===
Se citesc trei numere, a, b și c. Să se spună dacă pot fi laturile unui triunghi.
{|
| [[Image:laturi-triunghi.gif|frame|none|a, b, c pot fi laturile unui triunghi? varianta 1]]
| [[Image:laturi-triunghi-2.gif|frame|right|a, b, c pot fi laturile unui triunghi? varianta 2]]
|}

=== Afișare cifre număr în ordine inversă ===
Se citește n. Să se afișeze cifrele lui n în ordine inversă. [[Image:sl-cifre-număr-invers.gif|frame|none|Afișare cifre număr în ordine inversă]]

= Probleme de gândire =

Având în vedere că mulți dintre voi erați deja familiarizați cu programarea, v-am delectat cu câteva probleme de gândire:

=== Numărul lipsă ===
Se dau n - 1 valori distincte de numere între 1 și n. Să se afle numărul lipsă.

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_1_-_12_oct_2019#Num.C4.83rul_lips.C4.83]

=== Numerele lipsă ===
Se dau n - 2 valori distincte de numere între 1 și n. Să se afle numerele lipsă.

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_1_-_12_oct_2019#Numerele_lips.C4.83]

=== Problemă fun / interviu ===
Aveți dreptul la următoarele operații:
* Declarare variabilă (e.g. <code>int a;</code>)
* Decrementare variabilă (e.g. <code>--a;</code>)
* Cât timp expresie (e.g. <code>while (--a)</code>)

Să se implementeze <code>a = 0</code>.

Soluție aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_1_-_12_oct_2019#Problem.C4.83_fun_.2F_interviu]

=== Problemă fun / interviu #2 ===
Aveți dreptul la următoarele operații:
* Declarare variabilă (e.g. <code>int a;</code>)
* Decrementare variabilă (e.g. <code>--a;</code>)
* Cât timp expresie (e.g. <code>while (--a)</code>)

Să se implementeze <code>a = b</code>.

'''Soluție''' V-am promis că voi veni cu soluția la această problemă data viitoare! Este de apreciat dacă vă gândiți în continuare la ea și veniți și voi cu idei.

= Temă =

Tema pentru această dată este să acceptați invitațiile pe '''Slack''' și să urmăriți anunțurile de acolo. Vă voi comunica unde vom ține cercul de acum înainte (laborator sau sală de clasă, depinde câți doritori avem).

Clasa a IX-a lecția 2 - 19 oct 2019

2020-09-22T19:29:35Z

Teodor: /* Rezolvare problemă lecția anterioară */

= Rezolvare problemă lecția anterioară =

Rezolvare aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_2_-_19_oct_2019#Problem.C4.83_fun_.2F_interviu_.232]

= Lecție =

În urma întrebărilor pe care vi le-am adresat, a rezultat că în acest moment la cerc vin elevi cu un nivel variat de pregătire. Pentru a avea o perspectivă mai bună despre nivelul fiecăruia dintre voi, am continuat cu o lecție introductivă a cărei nivel de dificultate a crescut variat și opțional, am pus la bătaie problema [https://infoarena.ro/problema/expresie Expresie].

== Limbajul C ==
Am continuat cu o mini introducere în limbajul C, limbaj pe care îl vom aprofunda în lecțiile ce urmează la acest curs.

=== Limbaje de programare ===
Spre deosebire de schema logică care exprimă logica de bază a unui algoritm, limbajele de programare adaugă toate detaliile necesare pentru ca algoritmul sa fie înțeles și executat de calculator.

=== Structura unui program în C ===
Orice program C conține anumite elemente fixe:
* Includerea bibliotecilor / librăriilor care vor fi folosite pentru rezolvarea algoritmului (exemplu: biblioteca <code>stdio</code>, care ne permite să folosim funcții de citire și scriere).
* Începutul funcției principale (main). Programul va executa instrucțiunile în ordine, începând cu această funcție.
* Finalul funcției principale, în care se returnează valoarea zero (succes).

=== Hello World ===
Un program simplu: Hello World (programul clasic pe care programatorii îl scriu atunci când învață un nou limbaj de programare):<syntaxhighlight>#include <stdio.h>

int main() {
printf( "Hello world!" );
return 0;
}</syntaxhighlight>

=== Instrucțiuni de intrare/ieșire ===
Instrucțiunile [http://www.cplusplus.com/reference/clibrary/cstdio/scanf/ scanf] și [http://www.cplusplus.com/reference/clibrary/cstdio/printf/ printf] sunt echivalentul blocului paralelogram în schemă logică. Exemplu: citirea a două numere și afișarea sumei lor:<syntaxhighlight>#include <stdio.h>

int main() {
int a, b;

printf( "Introduceti doua numere: " );
scanf( "%d%d", &a, &b );
printf( "Suma numerelor este %d\n", a + b );
return 0;
}</syntaxhighlight>

Am discutat pe scurt despre cum sunt aranjate variabilele declarate în memorie pentru a înțelege mai bine semnificația operatorului <code>&</code> și a denumirii de "memorie pe stivă".

== Probleme ==
=== Suma a două numere ===
Suma a două numere folosind o variabilă intermediară, de calcul:
<syntaxhighlight>#include <stdio.h>

int main() {
int a, b, c;

scanf( "%d%d", &a, &b );
c = a + b;
printf( "Suma numerelor este %d\n", c );
return 0;
}</syntaxhighlight>

=== Calcul expresie ===
Scrieți la calculator programul care să calculeze expresia 24 / a + 100 / (c3 + b / (d2 + e2))<syntaxhighlight>#include <stdio.h>

int main() {
int a, b, c, d, e, expr;

scanf( "%d%d%d%d%d", &a, &b, &c, &d, &e );
expr = 24/a + 100 / (c * c * c + b / (d * d + e * e));
printf( "expresia este %d\n", expr );
return 0;
}</syntaxhighlight>

== Limbajul C ==

=== Intrucțiunea <tt>if</tt> ===
Am vorbit despre instrucțiunea <tt>if</tt>. Ea implementează structura alternativă. Apoi am vorbit despre operatorii de comparație <nowiki>==, !=, <, <=, >, >=.</nowiki> Exercițiu:
Să se spună dacă n divizibil cu k
{|
| [[Image:sl-n-div-k.gif|frame|none|Schemă logică]]
| valign="top"|<syntaxhighlight>#include <stdio.h>

int main() {
int n, k;

scanf( "%d%d", &n, &k );
if ( n % k == 0 )
printf( "Da" );
else
printf( "Nu" );
return 0;
}</syntaxhighlight>
|}

=== Instrucțiunea compusă ===
Instrucțiunea <tt>if</tt> permite cîte o singură instrucțiune pe fiecare ramură. Ce facem dacă avem mai multe instrucțiuni pe o ramură? Folosim instrucțiunea compusă, folosind acolade. Exercițiu: ecuația de gradul 1. Fie ecuația

:a · x = b

Să se calculeze x. Atenție! Ecuația poate avea multiple soluții, sau nici o soluție!

{|
| [[Image:ecuatia-grad-1.gif|frame|none|Schemă logică]]
| valign="top"| <syntaxhighlight>#include <stdio.h>

int main() {
int a, b, x;

scanf( "%d%d", &a, &b );
if ( a == 0 )
if ( b == 0 )
printf( "x oricare\n" );
else
printf( "x nu exista\n" );
else {
x = b / a;
printf( "x este %d\n", x );
}
return 0;
}</syntaxhighlight>
|}

=== Instrucțiunea <tt>while</tt> ===
Am vorbit despre instrucțiunea <tt>while</tt>. Ea implementează structura repetitivă de tip WHILE-DO.

'''Problemă''': Se dă un număr natural n. Să se afișeze prima cifră a acestuia.

<syntaxhighlight>#include <stdio.h>

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

while (n > 9)
n = n / 10;

printf("Prima cifra a lui n este %d\n", n);
return 0;
}</syntaxhighlight>

== Complexitate ==

Am vorbit despre complexitatea unui algoritm (numărul de pași pe care acesta va trebui să îi execute pe cazul cel mai "rău").

== Divizori & Descompunere în factori primi ==
=== Exercițiul 1 - Divizor propriu ===
Se citește un număr n. Să se afișeze cel mai mare divizor propriu al lui n (strict mai mic decât n). Exemplu: dacă n=24 cel mai mare divizor propriu este 12. Dacă n=7 cel mai mare divizor propriu este 1. Dacă n=125 cel mai mare divizor propriu este 25. Dacă n = 175 cel mai mare divizor propriu este 35.

<syntaxhighlight>
#include <stdio.h>

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

d = 2;
while (d * d <= n && n % d > 0)
d = d + 1;

if (n % d == 0)
printf("%d\n", n / d);
else
printf("1\n");

return 0;
}</syntaxhighlight>

Am discutat despre cum este aranjată mulțimea divizorilor unui număr și cum putem parcurge divizorii acestuia în complexitate <code>O(sqrt(N))</code>.

=== Exercițiul 2 - Divizorii unui număr ===
Se citește un număr n, Să se afișeze toți divizorii lui <tt>n</tt>.

Folosindu-ne de observația anterioară, am parcurs divizorii lui <tt>n</tt> în perechi de câte doi divizori, ținând cont și de cazul special în care <tt>n</tt> este pătrat perfect.

<syntaxhighlight>
#include <stdio.h>

int main() {
int n, d;

scanf("%d", &n);
printf("Divizorii lui %d sunt:", n);
d = 1;
while (d * d < n) {
if (n % d == 0)
printf("%d %d ", d, n / d);
d = d + 1;
}
if (n % d == 0)
printf("%d", d);
printf("\n");

return 0;
}</syntaxhighlight>

=== Exerciţiul 3 - Descompunere în factori primi ===
Se citește un număr <tt>n</tt>. Să se scrie descompunerea acestuia în factori primi.

Ne-am folosit de o observație similară cu cea folosită pentru afișarea divizorilor. În momentul în care întâlnim un divizor, împărțim numărul la acel divizor de câte ori este posibil și numărăm. Astfel avem garanția că de fiecare dată când dăm de un divizor, acesta este prim.

Atenție și la cazul în care numărul are un factor prim mai mare decât radicalul acestuia. Am demonstrat că dacă există, este unul singur și se află la puterea 1.

<syntaxhighlight>
#include <stdio.h>

int main() {
int n, p, e;

scanf("%d", &n);
p = 2;
while (p * p <= n) {
e = 0;
while (n % p == 0) {
n = n / p;
++e;
}

if (e > 0)
printf("%d la puterea %d\n", p, e);

++p;
}

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

return 0;
}</syntaxhighlight>

=== Exerciţiul 4 - Numărul de pătrate perfecte între a și b ===
Se citesc două numere <tt>a</tt> și <tt>b</tt>. Să se afișeze câte pătrate perfecte între <tt>a</tt> și <tt>b</tt> există.

'''Soluție''': Am dezbătut mai multe soluții la această problemă și am căzut de acord pe cea mai simplă sau intuitivă dintre ele:
* Calculăm câte pătrate perfecte sunt în intervalul <tt>[1, b]</tt> și notăm valoarea obținută cu <tt>N0</tt>.
* Calculăm câte pătrate perfecte sunt în intervalul <tt>[1, a - 1]</tt> și notăm valoarea obținută cu <tt>N1</tt>.
* Rezultatul este <tt>N0 - N1</tt>.

Am demonstrat că numărul pătratelor perfecte din intervalul <tt>[1, x]</tt> este <tt>sqrt(x)</tt>.

'''Mențiune''': De reținut această metodă de a număra într-un interval, poate ușura munca în multe situații!

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

int main() {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", sqrt(b) - sqrt(a - 1));
return 0;
}</syntaxhighlight>

Observăm că pentru a putea calcula radicalul unui număr (funcția <code>sqrt</code> în C), trebuie să includem biblioteca <code>math.h</code>.

== Algoritmul lui Euclid ==

=== Cel mai mare divizor comun ===

Algoritmul lui Euclid este o metodă eficientă de a calcula cel mai mare divizor comun al două numere. El pornește de la următoarea idee:
* <code>cmmdc(a, b) = cmmdc(a - b, b)</code>, unde <code>a > b</code>.

Aplicând repetat metoda scăderilor repetate de mai sus, concluzionăm că:
* <code>cmmdc(a, b) = cmmdc(a % b, b)</code>. Am arătat că în acest caz, nu contează dacă inițial se respectă condiția <code>a > b</code>.

<syntaxhighlight>
#include <stdio.h>

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

while (b != 0) {
r = a % b;
a = b;
b = r;
}

printf("Cel mai mare divizor comun este %d\n", a);

return 0;
}</syntaxhighlight>

=== Cel mai mic multiplu comun ===

Ne folosim de calculul celui mai are divizor comun și obținem: <code>cmmmc(a, b) = a * b / cmmdc(a, b)</code>.

=== Extindere pentru mai multe numere ===

Dacă vrem să extindem algoritmul pentru mai mult de două numere, avem:
* <code>cmmdc(a, b, c) = cmmdc(cmmdc(a, b), c)</code>.
* <code>cmmmc(a, b, c) = cmmmc(cmmmc(a, b), c)</code>.

Atenție! Următoarea variantă este INCORECTĂ: <code>cmmmc(a, b, c) = a * b * c / cmmdc(a, b, c)</code>.

= Temă =

=== Slack ===
Acceptați invitațiile de pe Slack, ca să putem comunica și să vă pot da feedback mai ușor pe problemele implementate.

=== Temă începători ===
Cei începători aveți ca temă să vă familiarizați cu limbajul ca să putem ajunge la un numitor comun în dificultatea cercului cât mai rapid. Treceți prin [http://algopedia.ro/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_1_-_12_oct_2019 Prima lecție] și trimiteți problemele în format <code>.cpp</code> pe Slack.

Lucrați și cereți-mi ajutorul și cu suficient efort și dorință veți putea ajunge la nivelul cercului. Recomandare de citit / exersat / învățat: [http://algopedia.ro/wiki/index.php/Cercul_de_informatic%C4%83_gimnaziu Cercul de informatică gimnaziu].

=== Temă ===

Rezolvați problemele rămase ca gândire în timpul cercului. Ma voi uita pe sursele voastre și vă voi oferi feedback.

* [https://infoarena.ro/problema/vase Vase]
* [https://infoarena.ro/problema/numar4 Numar4]

Cercul de informatică, Colegiul Național de Informatică Tudor Vianu, clasa a IX-a, anul 2019-2020

2020-05-24T09:33:04Z

Teodor: /* Note de curs */

Aceasta este pagina cercului de informatică pentru clasa a IXa predat la Colegiul Național de Informatică Tudor Vianu, București, Romania, și susținut de [http://francu.org/ Fundația Frâncu pentru Progres și Educație]. Mai jos aveți textul lecțiilor predate, precum și alte link-uri utile. Elevii înscriși la acest curs trebuie să citească și să își însușească regulile acestui curs.

== Spiritul cercului de informatică ==
* [[Reguli ale cercului de informatică]]: spiritul acestor lecții
 

== Componența cercului ==
* [[Cerc clasa a 9-a, anul 2019-2020]] (sîmbătă, ora 10:00)
 

== Note de curs ==
* [[Clasa a IX-a lecția 1 - 12 oct 2019]] Prezentare cerc; algoritmi; scheme logice
* [[Clasa a IX-a lecția 2 - 19 oct 2019]] Limbajul C; divizori; descompunere în factori primi; algoritmul lui Euclid
* [[Clasa a IX-a lecția 3 - 26 oct 2019]] Vectori; Ciurul lui Eratostene; Aplicații divizori și numere prime
* [[Clasa a IX-a lecția 4 - 2 nov 2019]] Aplicații divizori, cmmdc și numere prime
* [[Clasa a IX-a lecția 5 - 16 nov 2019]] Vectori caracteristici; Vectori de frecvență; Sortare; Aplicații
* [[Clasa a IX-a lecția 6 - 23 nov 2019]] Concurs; Aplicații cu secvențe, vectori, sortări
* [[Clasa a IX-a lecția 7 - 30 nov 2019]] Aplicații
* [[Clasa a IX-a lecția 8 - 7 dec 2019]] Caractere; Baze de numerație; Submulțimi; Operații pe biți
* [[Clasa a IX-a lecția 9 - 14 dec 2019]] Element majoritar; Baze de numerație - Continuare; Parantezare; Exponențiere rapidă
* [[Clasa a IX-a lecția 10 - 21 dec 2019]] Concurs
* [[Clasa a IX-a lecția 11 - 18 ian 2020]] Căutare binară
* [[Clasa a IX-a lecția 12 - 25 ian 2020]] Aplicații; Pregătire olimpiada pe scoală
* [[Clasa a IX-a lecția 13 - 1 feb 2020]] Matrici
* [[Clasa a IX-a lecția 14 - 8 feb 2020]] Funcții; Aplicații
* [[Clasa a IX-a lecția 15 - 15 feb 2020]] Stivă; Aplicații
* [[Clasa a IX-a lecția 16 - 22 feb 2020]] Recursivitate; Aplicații
* [[Clasa a IX-a lecția 17 - 29 feb 2020]] Sortări partea a II-a; Struct; Aplicații
* [[Clasa a IX-a lecția 18 - 14 mar 2020]] Concurs de acasă
* [[Clasa a IX-a lecția 19 - 21 mar 2020]] De acasă; Recursivitate; Flood Fill
* [[Clasa a IX-a lecția 20 - 27 mar 2020]] Concurs de acasă; Parsare
* [[Clasa a IX-a lecția 21 - 28 mar 2020]] De acasă; Coadă; Algoritmul lui Lee
* [[Clasa a IX-a lecția 22 - 03 apr 2020]] Concurs de acasă
* [[Clasa a IX-a lecția 23 - 02 mai 2020]] Divide et impera; Mergesort; Quicksort
* [[Clasa a IX-a lecția 24 - 09 mai 2020]] Programare dinamică
* [[Clasa a IX-a lecția 25 - 16 mai 2020]] Backtracking - combinări, permutări; Programare dinamică - continuare; Problema rucsacului
* [[Clasa a IX-a lecția 26 - 24 mai 2020]] Liste; Union-find
 

== Link-uri utile ==
* [[Setări necesare în Code::Blocks]]
* [[Instrucțiuni de intrare/ieșire în limbajul C]]
* [[Testarea timpului de execuție al unui program]]
* [[Unelte software necesare|Download: unelte software necesare]]
* [[Cercul de informatică - sfaturi pentru olimpiadă | Sfaturi pentru olimpiadă]]
* [[Cercul de informatică: pregătirea în vacanța de vară pentru elevii de gimnaziu | Pregătirea în vacanța de vară pentru elevii de gimnaziu]]

Clasa a IX-a lecția 26 - 24 mai 2020

2020-05-24T09:32:29Z

Teodor: /* Clasament teme lecțiile 1 - 25 */

= Clasament teme lecțiile 1 - 25 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/437f303d139fcf1bdcc314d73a7a7e66/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/3ae0764bab976d53d42aec31759d8771/vectori_sortari.html Sortări] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/cec8093d5d441fba76864812d8226de6/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/26eeae900c6d5a756c40f12d90da46bb/cautare_binara.html Căutare binară] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/602a6c71bcbf878c937b62dbf10ac714/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/dafe24bdd08675eadab0cb7ba50feb2f/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/3e7542f2e4cedee1bf78cedeb0da2c29/parcurgeri_matrice.html Parcurgeri matrice] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/bfc1c8fa4f9610249712004f49d7b3ce/divide_et_impera.html Divide et Impera] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/e23609de062d207f621d28d2b65a0f33/dinamica.html Programare dinamică] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/21fa3b8e7850272e54def8d356a4378a/backtraking.html Backtracking] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/1f31d71b47af7bd164796a81c2c86e11/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/558b8fda8af3af52d7c7ebfcf7116f3c/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eca3e002815aa7539d17960/8702201cde04e6283c2b0a613e7f9e43/oji.html Probleme OJI]

= Lecție =

== Liste înlănțuite ==

=== Definiție ===

O listă înlănțuită este o structură de date care reprezintă o înlănțuire secvențială de noduri. Fiecare nod este format dintr-un element (care conține date, poate fi un număr natural, un caracter, etc.) și o referință către următorul nod din listă. Lista înlănțuită permite inserarea și ștergerea eficientă a elementelor de pe orice poziție.

=== Implementare ===

Sunt mai multe moduri de a implementa o listă. Să luăm ca exemplu o listă care este formată din elemente numere întregi. Vom citi elementele într-un vector <tt>V</tt>. Inițial, lista conține toate elementele, iar după fiecare element <tt>V[i]</tt> în listă, urmează elementul <tt>V[i + 1]</tt>. Deci, ne putem declara un vector auxiliar <tt>NEXT</tt>, unde <tt>NEXT[i] = j</tt> reprezintă că elementul <tt>V[j]</tt> este următorul dupa <tt>V[i]</tt> în listă. Evident, ultimul element din listă nu are un succesor, deci îi putem da o valoare terminală/invalidă (-1 de exemplu).

==== Crearea listei din citirea unui vector ====

<syntaxhighlight>
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &v[i]);
next[i] = i + 1;
}
next[n - 1] = -1; // marcam ca este ultimul element din lista
</syntaxhighlight>

Citim un vector și creăm o structură de tip listă care ține valorile din vectorul citit.

==== Afișarea listei ====

<syntaxhighlight>
i = 0;
while (i != -1) { // cat timp nu am ajuns la o pozitie terminala
printf("%d ", v[i]); // afisam elementul
i = next[i]; // mutam cursorul la urmatorul element
}
</syntaxhighlight>

Afișăm elementele din listă. Se observă că în vectorul <tt>next</tt> reținem pozițiile din vector care fac parte din listă, vectorul <tt>v</tt> conținând valorile efective.

==== Ștergere element din listă după poziție ====

Vrem să ștergem din listă elementul care se află după elementul de la poziția <tt>i</tt>.

<syntaxhighlight>
if (next[i] != -1) // daca avem ceva dupa elementul i
next[i] = next[next[i]]; // luam ce avem in dreapta acelui element
</syntaxhighlight>

==== Afișarea elementului de pe pozitia k ====

Spre deosebire de un vector, unde avem acces direct la poziția <tt>k</tt> prin <tt>V[k]</tt>, într-o listă suntem nevoiți să parcurgem elementele.

<syntaxhighlight>
i = 0; // Setam pozitia de start ca fiind primul element din lista
for (j = 1; j < k; ++j) // Avansam de k-1 ori
i = next[i];
printf("%d", v[i]);
</syntaxhighlight>

'''Atenție''' În codul de mai sus, nu am verificat dacă nu cumva lista noastră are mai puțin de <tt>k</tt> elemente. Puteam verifica acest lucru asigurându-ne că nu ajungem niciodată cu valoarea lui <tt>i</tt> pe nodul terminal, <tt>-1</tt>. Acest lucru este însă ineficient, pentru că adăugăm o operație în plus, o întrebare la fiecare pas din parcurgere. Este mai eficient să reținem numărul de elemente din listă și să ne asigurăm că îl actualizăm de fiecare dată când este cazul. Vom compara <tt>k</tt> cu acel număr o singură dată, fiind astfel eficienți.

=== Aplicație ===

==== Enunț ====
Sursă [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_2_-_26_sep_2019#Aplica.C8.9Bie_1:_v-a.C8.9Bi_ascunselea IQAcademy]

<tt>n</tt> copii numerotați de la <tt>1</tt> la <tt>n</tt> și așezați în cerc numără la ''v-ați ascunselea'', din <tt>k</tt> în <tt>k</tt>, începând cu copilul <tt>1</tt>. Date <tt>n</tt> și <tt>k</tt> să se afișeze ordinea în care ies copiii din cerc.

==== Rezolvare ====

Problema are multe modalități de abordare. Folosind vectori simpli, putem să ne jucăm cu diverse parcurgeri/eliminări ale elementelor și vom ajunge în majoritatea cazurilor la o complexitate <tt>O(N2)</tt>. Soluțiile sunt prezentate foarte fain [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_2_-_26_sep_2019#Aplica.C8.9Bie_1:_v-a.C8.9Bi_ascunselea aici]. Voi prezenta soluția care folosește liste. Aceasta este, întâmplător și cea mai eficientă, având o complexitate egală cu <tt>O(N * K)</tt>.

Ideea este simplă: la fiecare pas, luăm cel de-al <tt>k</tt>-lea element, îl ștergem din listă și repetăm procedeul.

<syntaxhighlight>
#include <stdio.h>

int v[100], next[100];

int main() {
int n, k, i, j, pos;

scanf("%d%d", &n, &k);
// initializam lista
for (i = 0; i < n; ++i) {
v[i] = i + 1;
next[i] = (i + 1) % n; // copiii sunt asezati in cerc, copilul din dreapta ultimului este primul
}

pos = n - 1; // pos e pozitia copilului din-nainte de copilul de eliminat
for (i = 0; i < n; ++i) {
// avanseaza k - 1 elemente deoarece eliminarea conteaza ca un element
for (j = 1; j < k; ++j)
pos = next[pos];

printf("%d ", v[next[pos]]);
next[pos] = next[next[pos]];
}
printf("\n");

return 0;
}
</syntaxhighlight>

== Union-find ==

=== Enunț ===

Avem <tt>N</tt> valori distincte de la <tt>0</tt> la <tt>N - 1</tt>, fiecare valoare făcând parte din "submulțimea ei". Se dau două tipuri de operații:

* Unifică submulțimile valorilor <tt>i</tt> și <tt>j</tt>. (''union'')
* Fac valorile <tt>i</tt> și <tt>j</tt> parte din aceeași submulțime? (''find'')

=== Rezolvare ===

==== Ideea #1 ====

Vom reține un vector <tt>m[i] = </tt> indicatorul unic al mulțimii din care face parte valoarea <tt>i</tt>. Avem astfel:

===== Operația find =====

<syntaxhighlight>
int find(int i) {
return m[i];
}
</syntaxhighlight>

Funcția find ne întoarce chiar indicatorul mulțimii. Avem complexitate <tt>O(1)</tt>.

===== Operația union =====

<syntaxhighlight>
void union(int i, int j) {
int mj = m[j]; // retinem multimea din care face parte j
for (int k = 0; k < N; ++k) // parcurgem toate valorile
if (m[k] == mj) // daca dam de un element care face parte din multimea lui j
m[k] = m[i]; // il setam sa faca parte din multimea lui i
}
</syntaxhighlight>

Avem complexitate <tt>O(N)</tt>.

==== Ideea #2 - Optimizare union ====

Vom reține pentru fiecare valoare <tt>i</tt>, care este șeful suprem acesteia (sau dacă preferați termeni de corporație, managerul). Inițial, fiecare valoare <tt>i</tt> se are pe ea însăși pe post de manager. În momentul în care vrem să facem union între două valori, vom găsi șefii acestora, și vom seta șeful unuia dintre ei ca fiind celălalt. Implementarea arată cam așa:

===== Operația find =====

<syntaxhighlight>
int find(int i) {
if (sef[i] == i) // daca seful meu sunt eu, inseamna ca eu sunt seful suprem
return i; // il returnam
return find(sef[i]); // altfel returnam seful sefului meu
}
</syntaxhighlight>

Se observă că de data aceasta, pe cel mai rău caz, funcția ''find'' poate face <tt>N</tt> operații, deci are complexitate <tt>O(N)</tt>

===== Operația union =====

<syntaxhighlight>
void union(int i, int j) {
int sefi, sefj;

sefi = find(i); // seful suprem al lui i
sefj = find(j); // seful suprem al lui j

sef[sefj] = sefi; // seful suprem al lui sefj devine sefi
}
</syntaxhighlight>

Funcția ''union'' apelează de două ori ''find'' și mai face încă o operație. Chiar dacă ''find'' este o funcție lentă, putem considera că ''union'' este optimizată, pentru că am scăpat de acea parcurgere de complexitate <tt>N</tt>.

==== Ideea #3 - Optimizare find ====

O optimizare foarte importantă pentru funcția ''find'' pleacă de la observația că atunci când vrem să găsim șeful suprem al valorii <tt>i</tt>, noi trecem prin mai mulți șefi, șefi ai cărui șef suprem este egal cu cel al valorii <tt>i</tt>. Astfel, putem să actualizăm șefii acestor șefi în timpul parcurgerii recursive:

<syntaxhighlight>
int find(int i) {
if (sef[i] == i) // daca seful meu sunt eu, inseamna ca eu sunt seful suprem
return i; // il returnam
return sef[i] = find(sef[i]); // altfel legam i la seful suprem, pe care il si returnam
}
</syntaxhighlight>

Astfel ajungem la o complexitate de <tt>O(logN)</tt> atât pe ''find'', cât și pe ''union'', unde <tt>logN</tt> este adâncimea arborelui de manageri.

==== (Opțional) Ideea #4 - Optimizare union #2 ====

Putem optimiza și mai mult algoritmul, având grijă ca în momentul în care vrem să unim două mulțimi să alegem corespunzător care șef devine subordonat celuilalt. Altfel spus, trebuie să alegem cum trebuie dacă șeful lui <tt>i</tt> devine seful șefului lui <tt>j</tt> sau viceversa. Pentru aceasta, trebuie să reținem pentru fiecare mulțime numărul elementelor ale acesteia, iar atunci când împreunăm două mulțimi, vom atașa mulțimea mică la mulțimea mare.

= Temă =

[http://varena.ro/problema/zigzag zigzag - varena] Aplicație la liste 
[http://varena.ro/problema/lacoada lacoada - varena] Aplicație la liste 

[http://varena.ro/problema/disjoint disjoint - varena] 
[http://varena.ro/problema/bile3 bile3 - varena]

Clasa a IX-a lecția 25 - 16 mai 2020

2020-05-24T09:30:08Z

Teodor: /* Backtracking */

= Clasament teme lecțiile 1 - 24 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/928a661184c1e5f4af11d09c576c2ff5/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/85dfbb71a3e6a9f87a1f995204214355/vectori_sortari.html Sortări] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/2915ce5767dfc38383160746b81b8e34/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/94e7c6c20b7728734ab96cbe0f036b65/cautare_binara.html Căutare binară] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/fcc0e379719195fdfeb553ed2dacd74d/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/99a8034c2baee3d4902da8cbdbe8860c/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/54a6e65d3c148f74a7e98fd1f26830db/parcurgeri_matrice.html Parcurgeri matrice] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/bbc4ebf796fea1e90c6d8681408e3cd6/divide_et_impera.html Divide et Impera] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/0cd5ce860365b88e79bd94e26c8ff3d6/dinamica.html Programare dinamică] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/8ab43be69bf8bc51e5e1f8a1126636ce/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/7daae70344c04d707f4e0fc6ee65ddfe/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5ebf0285ca85bd37f655ff71/2ee9550752b971eccc9eeb3a0bf4cef9/oji.html Probleme OJI]

= Lecție =

== Backtracking ==

Așa zisa metodă backtracking reprezintă generarea tuturor soluțiilor unei probleme, urmând ca mai apoi să se aleagă soluția optimă dintre acestea. Am folosit această metodă la diverse probleme în lecțiile anterioare ([https://infoarena.ro/problema/numere8 Numere8], [https://infoarena.ro/problema/reteta Rețetă], în care am fost nevoiți să generăm toate submulțimile unei mulțimi. Am făcut acest lucru cu ajutorul descompunerii într-o bază de numerație (în baza 2 pentru problema [https://infoarena.ro/problema/numere8 Numere8], în baza 3 pentru problema [https://infoarena.ro/problema/reteta Rețetă]). Am specificat și atunci de existența unei alte tehnici numită backtracking, dar generarea submulțimilor folosind baze de numerație este o tehnică superioară, fiind mult mai rapidă și mai simplu de scris în practică.

La ce este atunci bună această tehnică de backtracking? Cum procedăm atunci când vrem să generăm nu toate submulțimile unei mulțimi, ci toate combinările, sau toate permutările?

=== [https://www.infoarena.ro/problema/combinari Combinări] ===

==== Enunț ====

Să se genereze toate combinările de <tt>N</tt> luate câte <tt>K</tt> în ordine lexicografică.

==== Exemplu ====

Pentru <tt>N = 4, K = 3</tt>, avem:
<tt>1 2 3 
1 2 4 
1 3 4 
2 3 4 </tt>

==== Soluție ====

Vom declara un vector de lungime <tt>K</tt>. Vom genera toate combinările pe rând cu ajutorul vectorului și le vom afișa. Vom parcurge pozițiile de la stânga la dreapta, și pe fiecare poziție în parte vom încerca să punem toate valorile posibile. După ce setăm o valoare pe o anumită poziție, trecem la următoarea poziție și tot așa, până completăm combinarea, pe care o vom afișa. Apoi ne vom întoarce și vom continua să punem celelalte valori rămase valori în fiecare poziție din vector.

Poate sună complicat, dar având în vedere proprietățile recursivității, algoritmul este chiar foarte simplu de scris:

<syntaxhighlight>
// avem completate toate pozitiile de la 1 la pos - 1
// vrem sa completam pozitia pos
void bkt(int pos) {
if (pos == k + 1) {
// am completat toate pozitiile
// afisam vectorul
for (int i = 1; i <= k; ++i)
printf("%d ", v[i]);
printf("\n");
} else {
// completam pozitia pos
// incepem de la valoarea trecuta in pozitia anterioara + 1
for (int val = v[pos - 1] + 1; val <= n; ++val) {
v[pos] = val; // scriem valoarea in vector la pozitia pos
bkt(pos + 1); // apelam functia pentru pos + 1
}
}
}
</syntaxhighlight>

=== [https://www.infoarena.ro/problema/permutari Permutări] ===

==== Enunț ====

Avem mulțimea <tt>{1, 2, ..., N}</tt>. Să se afișeze toate permutările mulțimii.

==== Exemplu ====

Pentru <tt>N = 3</tt>, avem:
<tt>1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1</tt>

==== Soluție ====

Soluția este similară cu cea folosită pentru generarea combinărilor. De această dată, fiind vorba de permutări, nu vrem să avem elemente duplicate și nu ne putem baza pe faptul că elementele sunt în ordine crescătoare. Deci, trebuie să verificăm soluția în momentul obținerii acesteia.

<syntaxhighlight>
// functie care returneaza daca in vector avem o permutare
bool perm() {
...
}

// avem completate toate pozitiile de la 1 la pos - 1
// vrem sa completam pozitia pos
void bkt(int pos) {
if (pos == n + 1) {
// am completat toate pozitiile
// verificam daca este o permutare
if (perm()) {
// afisam
for (int i = 1; i <= n; ++i)
printf("%d ", v[i]);
printf("\n");
}
} else {
// completam pozitia pos
// trecem prin toate valorile posibile
for (int val = 1; val <= n; ++val) {
v[pos] = val; // scriem valoarea in vector la pozitia pos
bkt(pos + 1); // apelam functia pentru pos + 1
}
}
}
</syntaxhighlight>

Putem mai bine decât să verificăm de fiecare dată când generăm o soluție dacă aceasta este optimă? Da! Putem verifica de fiecare dată când introducem o valoare în vector, dacă aceasta a mai fost deja introdusă. Vom folosi un vector caracteristic pentru asta.

<syntaxhighlight>
// avem completate toate pozitiile de la 1 la pos - 1
// vrem sa completam pozitia pos
void bkt(int pos) {
if (pos == n + 1) {
// am completat toate pozitiile
// stim deja ca este o permutare, ne-am asigurat cand am construit solutia
// afisam
for (int i = 1; i <= n; ++i)
printf("%d ", v[i]);
printf("\n");
} else {
// completam pozitia pos
// trecem prin toate valorile posibile
for (int val = 1; val <= n; ++val)
if (!marked[val]) { // daca valoarea nu este marcata
v[pos] = val; // scriem valoarea in vector la pozitia pos
marked[val] = true; // marcam valoarea ca fiind folosita
bkt(pos + 1); // apelam functia pentru pos + 1
marked[val] = false; // la intoarcere, valoarea nu mai este folosita, o demarcam
}
}
}
</syntaxhighlight>

== Problema rucsacului fracționar ==

=== Enunț ===

Se dau N obiecte pentru care se cunosc greutatea g si pretul p si un rucsac de capacitate G. Se cere sa se calculeze si sa se afiseze profitul maxim ce se poate obtine adaugand o submultime din cele N obiecte in rucsac. Se pot selecta si fractiuni ale obiectelor. Profitul este suma preturilor integrale la care se adauga fractiuni ale preturilor pentru obiectele selectate partial.

=== Exemplu ===

Avem <tt>G = 4</tt> și următoarele obiecte:

{| class="wikitable"
! Nr. || 1 || 2 || 3
|-
! Greutate
| 2 || 2 || 1
|-
! Valoare
| 4 || 5 || 3
|}

Pentru a obține profitul maxim, vom lua <tt>1</tt> unitate din al treilea obiect, <tt>2</tt> unități din cel de-al doilea și <tt>1</tt> unitate din primul. Vom avea deci suma egală cu <tt>10</tt>.

=== Soluție ===

Având în vedere că putem lua fracțiuni din fiecare obiect, merită să luăm mai întâi cât se poate din obiectele rămase ale călor valoare per unitate este cea mai mare, repetând procedeul până când fie epuizăm toate obiectele, fie umplem rucsacul.

Vom sorta descrescător obiectele după valoarea lor per unitate (raportul <tt>preț / greutate</tt>) și vom aplica algoritmul descris mai sus.

Tipul acesta de rezolvare, în care la fiecare pas luăm soluția optimă locală pentru ca la final să obținem soluția optimă globală mai poartă și numele de '''Greedy'''. Atenție totuși, alegând la fiecare pas soluția locală optimă nu ne garantează întotdeauna că obținem soluția globală optimă.

=== Complexitate ===

Din punct de vedere al timpului, avem o complexitate egală cu <tt>O(N logN)</tt>, datorită sortării.

'''Atenție''' Pentru a sorta vectorul, trebuie să comparăm fracții (exemplu: <tt>p[i]/g[i]</tt> ? <tt>p[j]/g[j]</tt>). Făcut direct, acest lucru este ineficient pentru că ne obligă să folosim tipul de date <tt>float</tt>. Algoritmul se va mișca mai lent și putem întâlni probleme de precizie. Putem să transformăm această comparație într-o comparație de produse (exemplu: <tt>p[i]*g[j] ? g[i]*p[j]</tt>). Păstrăm astfel tipul de date <tt>int</tt>, algoritmul este eficient și nu avem probleme de precizie.

Din punct de vedere al spațiului consumat, algoritmul nu ocupă memorie în plus, ocupând astfel <tt>O(1)</tt> spațiu suplimentar.

== Problema rucsacului ==

=== Enunț ===

Este aceeași problemă ca cea anterioară, doar că de această dată nu putem lua fracțiuni de obiecte, ci suntem obligați să luăm obiectele întregi.

=== Exemplu ===

Avem <tt>G = 4</tt> și următoarele obiecte:

{| class="wikitable"
! Nr. || 1 || 2 || 3
|-
! Greutate
| 2 || 2 || 1
|-
! Valoare
| 4 || 5 || 3
|}

Vom lua primele două obiecte, obținând suma <tt>9</tt>.

=== Soluție ===

Soluția prezentată la varianta fracționară a problemei nu funcționează în acest caz (după cum se poate observa și din exemplu). Soluția corectă implică programare dinamică. Un mit popular este că problemele care "par" că se rezolvă folosind metoda Greedy, dar produc răspunsuri incorecte, se pot rezolva folosind programarea dinamică. Este totuși doar un mit și trebuie tratat ca atare. Nu este întotdeauna adevărat!

O soluție corectă ar fi o metodă de tip backtracking, generând toate submulțimile posibile. Evident, această soluție nu este tocmai eficientă, având o complexitate egală cu <tt>O(2N)</tt>, unde <tt>N</tt> este numărul de obiecte.

Cum construim dinamica pentru această problemă? Variantele "simple", de 1 singură dimensiune, folosite în lecția anterioară nu vor funcționa pentru că în această problemă ne confruntăm cu două dimensiuni: atât greutatea rucsacului și valoarea obiectelor.

Exemplu:
* D[i] = suma maximă care se poate obține dintr-o submulțime a primelor i obiecte. Nu avem deloc informații despre cât loc mai avem disponibil în rucsac la fiecare pas.
* D[g] = suma maximă care se poate obține într-un rucsac de greutate g. Nu avem deloc informații despre ce obiecte am selectat deja, pentru a ne asigura că nu luăm un obiect de două ori.

Vom construi deci o dinamică pe două dimensiuni:
* D[i][g] = suma maximă care se poate obține dintr-o submulțime a primelor i obiecte, într-un rucsac de mărime g.

Răspunsul problemei se află chiar în <tt>D[N][G]</tt>.

Cum calculăm <tt>D[N][G]</tt>? Vom porni cu un indice <tt>i</tt> de la stânga la dreapta șirului de obiecte, și pentru fiecare <tt>i</tt> vom parcurge toate greutățile cu o variabilă <tt>g</tt> de la <tt>0</tt> la <tt>G</tt>. La fiecare pas, avem de ales între a introduce sau nu în rucsac cel de-al <tt>i</tt>-lea obiect. Avem astfel:

* <tt>D[i][g] = D[i - 1][g]</tt>; dacă alegem să nu introducem în rucsac obiectul
* <tt>D[i][g] = D[i - 1][g - g[i]] + p[i]</tt>, unde <tt>g[i]</tt> și <tt>p[i]</tt> reprezintă greutatea și prețul celui de-al <tt>i</tt>-lea obiect; dacă alegem să introducem obiectul

Vom alege evident, varianta optimă dintre acestea, deci <tt>D[i][g] = max(D[i - 1][g], D[i - 1][g - g[i]] + p[i])</tt>.

<syntaxhighlight>
for (int i = 0 i < N; ++i)
for (int s = 0; s <= G; ++s) {
d[i][s] = d[i - 1][s];
if (g[i] <= s) // ne asiguram ca avem suficient spatiu in rucsac
d[i][s] = max(d[i][s], d[i - 1][s - g[i]] + p[i]);
}
</syntaxhighlight>

=== Complexitate ===

Complexitatea de timp a algoritmului este <tt>O(N*G)</tt>.

Din punct de vedere al spațiului consumat, acesta este egal tot cu <tt>O(N*G)</tt>. Poate fi optimizat către <tt>O(G)</tt> observând că la fiecare pas, ne folosim doar de rezultatele din linia anterioară.

<syntaxhighlight>
for (int i = 0; i < N; ++i)
for (int s = 0; s <= G; ++s) {
d[i & 1][s] = d[(i - 1) & 1][s];
if (g[i] <= s)
d[i & 1][s] = max(d[i & 1][s], d[(i - 1) & 1][s - g[i]] + p[i]);
}
</syntaxhighlight>

= Temă =

Da, știu că pare o temă foarte stufoasă. Dar problemele sunt similare, deci nu vă fie frică! :P

[https://www.infoarena.ro/problema/combinari infoarena - Combinări] 
[https://www.infoarena.ro/problema/permutari infoarena - Permutări] 
[https://www.infoarena.ro/problema/submultimi infoarena - Submulțimi] 
[http://varena.ro/problema/submultimi varena - Submulțimi] 
[http://varena.ro/problema/permfix varena - Permfix] 
[http://varena.ro/problema/treicc varena - Trei cifre consecutive] 
[http://varena.ro/problema/partnr varena - Partițiile unui număr] 
[https://www.infoarena.ro/problema/flip infoarena - Flip] 
[http://varena.ro/problema/regine varena - Regine] 
 
[http://varena.ro/problema/rucsacfr varena - Rucsac fracționar] 
[http://varena.ro/problema/rucsac1 varena - Rucsac1] 
[https://infoarena.ro/problema/rucsac infoarena - Problema rucsacului] 
[https://infoarena.ro/problema/jocul infoarena - Jocul] 
[http://varena.ro/problema/camelot varena - Camelot]

Clasa a IX-a lecția 24 - 09 mai 2020

2020-05-15T19:09:46Z

Teodor:

= Clasament teme lecțiile 1 - 23 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/2225c3b78050bd98e2be421457e909a8/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/48f1e21a19f5f5d1de83298a131e3487/vectori_sortari.html Sortări] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/253b0069cf8e9fb2c3f87ce07caa75a8/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/e4b8774287e90e18c7ac7b0f1486949c/cautare_binara.html Căutare binară] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/bed2c349d53e1b9cd8017f21d46c56fc/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/f3378d904d08417fb6e9d08ed7a632ab/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/85f194e32064621287393bc02613b856/parcurgeri_matrice.html Parcurgeri matrice] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/ef676fed0f2d8b53af306370dbb554d3/divide_et_impera.html Divide et Impera] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/8c35077581f19262299194b9a1b189b0/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/1d2f67712af61c2f0a19112c6f81c72b/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eb657355ea32f484cfc94a6/862bcb9e318228afca36de75c57e0ca4/oji.html Probleme OJI]

= Lecție =

== Programare dinamică ==

=== Introducere ===

Similar cu tehnica ''Divide et impera'', programarea dinamică este o metodă prin care rezolvăm probleme mai complexe, descompunându-le în subprobleme mai simple. Este însă o diferență majoră între cele două tehnici: ''Divide et impera'' poate fi aplicată doar dacă subproblemele în care descompunem problema originală '''nu se suprapun'''. De exemplu, ''Mergesort'' și ''Quicksort'' se pot folosi de tehnica ''Divide et impera'' pentru că la fiecare pas se împarte vectorul în două submulțimi complet distincte.

În general, problemele care se rezolvă folosind metoda programării dinamice sunt cele care necesită găsirea unei soluții optime. Folosind programarea dinamică, vom împărți în subprobleme pentru care găsim mai ușor soluția optimă și le vom combina pentru a calcula soluția optimă în problema originală.

=== Metodă ===

Înainte de a aplica programarea dinamică, trebuie să ne dăm seama dacă problema noastră se poate rezolva folosind această metodă. Altfel spus, trebuie să ne dăm seama dacă putem ajunge la o soluție optimă, din soluții optime obținute în subprobleme mai mici. Și pentru asta, avem de răspuns la două întrebări:

* Cum știm în ce subprobleme mai mici putem împărți problema mare?
* Cum știm să combinăm rezultatele optime obținute în subprobleme, pentru a răspunde la problema mare?

Nu există un răspuns generic la aceste întrebări. Totul depinde de problema pe care vrem să o rezolvăm. Experiența este foarte importantă în lucrul cu programarea dinamică, ea ne va ajuta să răspundem mai rapid la aceste întrebări.

Odată ce descoperim cum putem împărți problema și cum putem combina rezultatele, implementarea este cel de-al treilea pas. Acesta este, de obicei, cel mai simplu. Vom implementa o formulă de recurență prin care combinâm rezultatele, implementată de jos în sus (pornind de la cele mai mici probleme, către cele mai mari, până la soluția cerută).

=== Subsecvența de sumă maximă ===

Se dă un șir <tt>V</tt> de <tt>N</tt> elemente. Să se găsească subsecvența de sumă maximă.

==== Exemplu ====

Avem șirul: <tt>5, -6, 3, 4, -2, 3, -3</tt>. Subsecvența de sumă maximă este formată din elementele <tt>3, 4, -2, 3</tt>.

==== Soluție ====

Împărțim problema în subprobleme:

* <tt>S[i]</tt> = Suma maximală a unei subsecvențe care se termină pe poziția <tt>i</tt>

Putem scoate răspunsul la problema originală combinând răspunsul acestor subprobleme? Da, răspunsul este chiar <tt>max(S[i])</tt>.

Cum calculăm <tt>S[i]</tt>? Vom presupune că am calculat deja toate sumele până la <tt>i - 1</tt>. Secvența de sumă maximă care se termină pe poziția <tt>i</tt> are două cazuri:

* Dacă <tt>S[i - 1]</tt> este pozitiv, atunci <tt>S[i] = S[i - 1] + V[i]</tt> (adăugăm <tt>V[i]</tt> la subsecvența de sumă maximă care se termină pe <tt>i - 1</tt>
* Dacă <tt>S[i - 1]</tt> este negativ, atunci <tt>S[i] = V[i]</tt> (subsecvența de sumă maximă care se termină pe <tt>i</tt> este formată doar din elementul <tt>V[i]</tt>)

==== Complexitate ====

Algoritmul este liniar, având complexitate de timp <tt>O(N)</tt>. Ca memorie, algoritmul are nevoie de <tt>O(1)</tt> memorie suplimentară, nefiind nevoie să reținem toate valorile din vectorul <tt>S</tt>, ci doar valoarea anterioară în sensul parcurgerii.

=== Subșir crescător maximal ===

Se dă un șir <tt>V</tt> de <tt>N</tt> elemente. Să se găsească un subșir ordonat strict crescător care are lungimea maximă.

==== Exemplu ====

Avem șirul: <tt>24, 12, 15, 15, 19</tt>. Subșirul crescător maximal este format din elementele <tt>12, 15, 19</tt>.

==== Soluție ====

Împărțim în subprobleme:

* <tt>D[i]</tt> = lungimea celui mai lung subșir care se termină cu elementul de pe poziția <tt>i</tt>

Putem scoate răspunsul la problema originală combinând răspunsul acestor subprobleme? Da, răspunsul este chiar <tt>max(D[i])</tt>.

Cum calculăm <tt>D[i]</tt>? Vom presupune că am calculat deja toate lungimile până la <tt>D[i - 1]</tt>. Astfel, avem:

* <tt>D[i] = max(D[j] + 1])</tt>, unde <tt>j < i</tt> și <tt>V[j] < V[i]</tt>.

În alte cuvinte, încercăm să adăugăm elementul <tt>V[i]</tt> la toate șirurile din stânga, pentru care <tt>V[i] > V[j]</tt>.

==== Complexitate ====

Complexitatea de timp a algoritmului este <tt>O(N2)</tt>. Există și o implementare de complexitate <tt>O(N logN)</tt>, pe care o vom discuta cu altă ocazie.

Complexitatea de spațiu adițional este <tt>O(N)</tt>.

=== Subsecvență comună maximală ===

Se dau două șiruri de numere. Să se găsească o subsecvență de valori inclusă în ambele șiruri.

==== Exemplu ====

Primul șir: <tt>1, 2, 1, 2, 3, 7</tt>.
Cel de-al doilea șir: <tt>3, 2, 1, 2, 1, 4, 3, 7</tt>.

Sunt două subsecvențe comune de lungime maximă: <tt>1, 2, 1</tt> și <tt>2, 1, 2</tt>.

==== Soluție ====

Împărțim problema în subprobleme. Având în vedere că sunt două șiruri în cazul de față, avem nevoie de subprobleme mai "complexe":

* D[i][j] = lungimea subsecvenței comune maximale care se termină pe poziția <tt>i</tt> în primul șir, respectiv pe poziția <tt>j</tt> în cel de-al doilea șir.

Ne putem aceleași întrebări ca și în problemele precedente.

Putem scoate răspunsul la problema originală combinând răspunsul acestor subprobleme? Da, răspunsul este chiar <tt>max(D[i][j])</tt>.

Cum calculăm <tt>D[i][j]</tt>? Vom presupune că avem calculate toate valorile precedente din parcurgere și avem două cazuri:

* <tt>A[i] == B[j]</tt>, atunci <tt>D[i][j] = D[i - 1][j - 1] + 1</tt> (putem continua subsecvența maximală care se termină pe pozițiile de dinainte în ambele șiruri)
* <tt>A[i] != B[j]</tt>, atunci <tt>D[i][j] = 0</tt> (nu avem o subsecvență care se termină pe aceste poziții, pentru că ele diferă)

==== Complexitate ====

Complexitatea de timp este <tt>O(N * M)</tt>, unde <tt>N</tt> și <tt>M</tt> sunt lungimile celor două șiruri.

Complexitatea de spațiu poate fi redusă la <tt>O(min(N, M))</tt>. Din câte se observă, la fiecare pas al parcurgerii avem nevoie doar de linia / coloana precedentă din matrice, deci nu este nevoie să reținem toată matricea.

=== Subșir comun maximal (Cel mai lung subșir comun) ===

Se dau două șiruri de numere. Să se găsească un subșir de valori care apare în ambele șiruri.

==== Exemplu ====

Primul șir: <tt>1, 7, 3, 9, 8</tt>.
Cel de-al doilea șir: <tt>7, 5, 8</tt>.

Subșirul comun de lungime maximă este format din elementele <tt>7, 8</tt>.

==== Soluție ====

Împărțim problema în subprobleme. Similar ca la problema anterioară, cu o mică schimbare care să ne ajute să luăm în considerare subșiruri, nu subsecvențe:

* <tt>D[i][j]</tt> = lungimea celui mai lung subșir inclus în șirurile <tt>A[1..i]</tt> și <tt>B[1..j]</tt>

Putem scoate răspunsul pentru problema originală? Da, este chiar <tt>D[N][M]</tt>, unde N și M sunt lungimile șirurilor.

Cum calculăm <tt>D[i][j]</tt>? Vom presupune din nou că avem calculate toate valorile precedente:

* <tt>A[i] == B[j]</tt>, atunci <tt>D[i][j] = D[i - 1][j - 1] + 1</tt> (putem continua subșirul de dinainte cu această valoare)
* <tt>A[i] != B[j]</tt>, atunci <tt>D[i][j] = max(D[i - 1][j], D[i][j - 1]</tt> (avem elemente diferite, deci luăm în considerare doar subșirurile de dinaintea lor)

==== Complexitate ====

Complexitatea de timp este <tt>O(N * M)</tt>, unde <tt>N</tt> și <tt>M</tt> sunt lungimile celor două șiruri.

Complexitatea de memorie este tot <tt>O(N * M)</tt>.

==== Reconstrucția soluției ====

Pentru a reconstrui soluția, pentru fiecare <tt>(i, j)</tt> vom reține atât lungimea subșirului si direcția din care a provenit. Direcția poate fi stânga <tt>(D[i][j - 1])</tt>, sus <tt>(D[i - 1][j])</tt>, sau diagonală <tt>(D[i - 1][j - 1])</tt>. Vom porni din poziția finală <tt>(N, M)</tt> și vom urmări aceste direcții, reținând fiecare literă pentru care direcția în care ne ducem este diagonală (asta înseamnă că această literă se găsește în subșir). Ne oprim evident, când ieșim din matrice.

= Temă =

[https://www.infoarena.ro/problema/ssm infoarena - Subsecvență de sumă maximă] 
[https://www.infoarena.ro/problema/scmax infoarena - Subșir crescător maximal] 
[https://www.infoarena.ro/problema/cmlsc infoarena - Subșir comun maximal (Cel mai lung subșir comun)] 
[http://varena.ro/problema/sclm varena - Subșir comun de lungime maximă]

Clasa a IX-a lecția 23 - 02 mai 2020

2020-05-09T07:15:11Z

Teodor: Undo revision 17764 by Teodor (talk)

= Clasament teme lecțiile 1 - 22 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/021137da51f785f338c7f53b6dcb0958/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/329f0912ef1a229c3f05409646beb9a9/vectori_sortari.html Sortari] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/d8f1e41f31a826f42435d2271434e26c/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/c54e838e2998628bc21508c47721efb9/cautare_binara.html Cautare binara] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/b05b64b82a6b8dbeff798b2b66ff481d/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/b6fd8dbf1d971e4698351d1fb60c7deb/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/95c957639753e3e37648b32f1655e45d/parcurgeri_matrice.html Parcurgeri matrice] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/cc0344a2cf619f33d4cde10be5da8755/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/156b4685d16844ccef72303f0aa2b74b/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5eac18f100d29e0e29929afc/3e6efe660836debb8d8ec43ac7a748c3/oji.html Probleme OJI]

= Lecție =

== Divide et impera ==

Deși am folosit această tehnică în câteva aplicații recursive, acum vom intra mai în detaliu.

Tehnica de programare divide et impera constă în împărțirea problemei în subprobleme mai mici, nesuprapuse, care sunt mai ușor de rezolvat. Rezultatul final se obține combinând rezultatele problemelor mai mici deja rezolvate.

== Divide et impera simplu ==

Exemple de probleme în care tehnica divide et impera împarte problema originală într-o singură problemă, mai simplă:

=== Algoritmul lui Euclid ===

Algoritmul lui Euclid poate fi privit ca un exemplu al tehnicii divide et impera. Acesta împarte problema de la aflarea <tt>cmmdc(a, b)</tt> la aflarea <tt>cmmdc(a % b, b)</tt>.

=== Căutare binară ===

Căutarea binară împarte vectorul / mulțimea originală în două, algoritmul urmând să se aplice pe o singură ramură dintre acestea.

=== [https://infoarena.ro/problema/z ZParcurgere] ===

O problemă pe care am discutat-o anterior, rezolvată tot prin divide et impera, evaluând cadranul în care se află numărul nostru și apelând recursiv funcția pe acel cadran.

'''Observație''' Pentru aceste probleme, tehnica divide et impera se poate implementa iterativ, deoarece împărțim problema într-o singură altă problemă.

== Divide et impera ==

Exemple de probleme în care tehnica divide et impera împarte problema originală în mai multe probleme:

=== Mergesort ===

Sortarea prin interclasare este o sortare în complexitate de timp <tt>O(N logN)</tt>, folosind <tt>O(N)</tt> memorie suplimentară. Este prima sortare de această complexitate pe care o învățăm.

Cum funcționează? Ne vom folosi de proprietățile recursivității. Vom crea o funcție <tt>mergesort</tt>, care primește ca parametru un vector. La început, vom apela funcția pentru întreg vectorul inițial. Funcția va împărți vectorul în două părți egale, și se va apela pe ea însăși pentru ambele părți. Acest procedeu recursiv se va repeta până când funcția ajunge la un singur element. Ne putem întoarce atunci, pentru ca acel element reprezintă un vector sortat. La întoarcere din recursivitate, vom considera că funcția ne-a întors doi vectori sortați, iar noi îi vom interclasa pentru a întoarce la rândul nostru un vector sortat.

<syntaxhighlight>
void mergesort(int v[], int left, int right) {
if (left == right) // Un singur element, deci "vectorul" format din acest singur element este sortat
return; // Ne intoarcem

int mid = (left + right) / 2; // Mijlocul vectorului
mergesort(v, left, mid); // Sortam stanga
mergesort(v, mid + 1, right); // Sortam dreapta

merge(v, left, mid, right); // Functie care interclaseaza v[left...mid] cu v[mid + 1...right]
}
...
mergesort(v, 0, n - 1);
</syntaxhighlight>

==== Complexitate timp ====

Să calculăm numărul de operații, ''T(N)'', pentru a sorta un vector de ''N'' elemente:

''T(N) = 2 '''·''' T(N/2) + N''
''T(N) = 2 '''·''' (2 '''·''' T(N/4) + N/2) + N''
''T(N) = 4 '''·''' T(N/4) + 2 '''·''' N''
''T(N) = 4 '''·''' (2 '''·''' T(N/8) + N/4'') + 2 '''·''' N''
''T(N) = 8 '''·''' T(N/8) + 3 '''·''' N''
...
''T(N) = N '''·''' T(N/N) + log N '''·''' N''
''T(N) = N '''·''' T(1) + log N '''·''' N''

Deci, complexitatea de timp a algoritmului este <tt>O(N logN)</tt>.

==== Complexitate spațiu ====

Funcția <tt>merge</tt>, responsabilă pentru interclasarea celor două jumătăți de vector are nevoie de un vector suplimentar. Deci, algoritmul folosește <tt>O(N)</tt> suplimentar.

==== Aplicație mergesort - inversiunile unei permutări ====
Sursă [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_19_-_30_ian_2020#Aplica.C8.9Bie_mergesort_-_inversiunile_unei_permut.C4.83ri IQAcademy]

O problemă care apare uneori la concursuri este următoarea: se dă o permutare a numerelor de la 1 la ''N''. Să se numere cîte inversiuni are ea. O inversiune este o pereche de indici ''(i, j)'' astfel încît ''i < j'' și ''P[i] > P[j]''.

În linii mari, algoritmul este următorul:

* Sortăm prima jumate a vectorului folosind un mergesort special, care ne returnează numărul de inversiuni din vectorul de sortat.
* Sortăm a doua jumate a vectorului.
* În acest moment știm inversiunile din cele două jumătăți - le adunăm.
* Interclasăm cele două jumătăți. În timpul interclasării cînd selectăm un număr din prima jumătate știm că numerele deja selectate din jumătatea a doua sînt mai mici, deci putem aduna numărul lor la numărul total de inversiuni.

=== Quicksort ===

Un alt algoritm de sortare important este sortarea rapidă. Cum funcționează?

* 1. Alegem o poziție la întâmplare din vectorul de sortat. Vom denumi valoarea de la acea poziție pivot.
* 2. Rearanjăm vectorul astfel încât în prima parte să avem elemente mai mici sau egale cu pivotul iar în a doua parte elemente mai mari sau egale cu pivotul. Numim acest pas pivotare.
* 3. Reapelăm quicksort pe acele două părți.

Trebuie să acordăm atenție la alegerea pivotului și la implementarea pasului de pivotare.

'''Alegerea pivotului'''

Similar cu mergesort, ar fi ideal ca la fiecare pas să împărțim vectorul în două părți cât mai egale ca dimensiune. Astfel, vom obține o complexitate de timp aproximativ egală cu <tt>O(N logN)</tt>.

Se poate "nimeri" să alegem pivotul astfel încât la fiecare pas, să împărțim vectorul în doi vectori dintre care unul are dimensiunea 1. În acest caz, vom avea o complexitate de timp egală cu <tt>O(N2)</tt>. Putem deduce de aici că pe cel mai rău caz, algoritmul poate face <tt>N2</tt> pași.

Acest "cel mai rău caz" poate fi evitat în mare măsură printr-o alegere aleatoare a pivotului la fiecare pas. Vom atribui pivotului o valoare aleatoare între [left, right].

'''Pasul de pivotare'''

Am ales un pivot și vrem să rearanjăm vectorul astfel încât toate elementele mai mici sau egale cu acesta sunt la stânga lui, iar toate mai mari sau egale cu acesta sunt la dreapta.

* Pornim cu doi indici, unul la începutul vectorului și unul la final de vector, să le spunem b si e.
* Avansăm indicele b până la primul element mai mare sau egal cu pivotul
* Devansăm indicele e până la primul element mai mic sau egal cu pivotul
* Interschimbăm elementele din vector de la pozițiile b și e
* Repetăm până ce indicii se ating, b >= e

<syntaxhighlight>
void qsort(int v[], int begin, int end) {
int pivot = v[begin + rand() % (end - begin)]; // alegem pivotul aleator

int b = begin, e = end;
while (v[b] < pivot) // cauta primul element mai mare sau egal cu pivotul
b++;

while (v[e] > pivot) // cauta primul element mai mic sau egal cu pivotul
e--;

while(b < e) { // daca indicii nu s-au atins
swap(v[b], v[e]); // interschimba pozitiile

do // cauta primul element mai mare sau egal cu pivotul
b++;
while (v[b] < pivot);

do // cauta primul element mai mic sau egal cu pivotul
e--;
while (v[e] > pivot);
}

// acum [begin..e] sunt mai mici sau egale cu pivotul
if (begin < e)
qsort(begin, e);
// si [e+1..end] sunt mai mari sau egale cu pivotul
if (e + 1 < end)
qsort(e + 1, end);
}
...
qsort(v, 0, n);
</syntaxhighlight>

==== Complexitate timp ====

Am discutat deja de complexitatea de timp, și anume <tt>O(N logN)</tt>.

==== Complexitate spațiu ====

Complexitatea spațiu este egală cu numărul de apeluri recursive ale funcției. În urma discuției de la alegerea pivotului, avem o complexitate de spațiu suplimentar egală cu <tt>O(log N)</tt>.

=== Sortarea din STL ===

Chiar dacă sortarea din STL poate fi suficient de rapidă, mai ușor de scris și își face treaba, este important să știți acești algoritmi prezentați astăzi. În sortările gata scrise din diverse librării ale limbajului de programare pe care îl folosiți nu aveți control total asupra tehnicii sau asupra memoriei folosite și puteți avea surprize neplăcute. Deci, recomand să folosiți aceste sortări ori de câte ori aveți posibilitatea, pentru a vă acomoda cu implementarea corectă a lor.

= Temă =

Rezolvați problema [https://infoarena.ro/problema/algsort algsort], implementând ambii algoritmi de sortare învățați în lecția de astăzi.

[http://varena.ro/problema/latin latin - varena] 
[http://varena.ro/problema/tabela tabela - varena] 
[https://infoarena.ro/problema/granita granita - infoarena] 
[https://infoarena.ro/problema/sport sport - infoarena]

Clasa a IX-a lecția 21 - 28 mar 2020

2020-04-02T18:58:18Z

Teodor: /* Implementare */

= Clasament teme lecțiile 1 - 20 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/2653d056fc40698d22e54edee5bc6822/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/b0fb259e03e8d22f5ebe996976fa15a9/vectori_sortari.html Sortari] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/b7ff861a6087b26b176c0b2adf87af36/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/20708b73ca3403584d3997a6468c2db7/cautare_binara.html Cautare binara] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/7cc24bb3e0b54e23a97638c1a5707bfc/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/d1d6c8f74b5f585f9f9915e34cd35801/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/46fe4c46f02c10ebb1a08156329e976c/parcurgeri_matrice.html Parcurgeri matrice] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/4c8306606edf6eef31f4915d14287802/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/ded94c7c7f61cde8607c9a2b1d2c4766/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e7e5e19c0373c6e311b964b/75236f3cab3c3e8e876258c9d1666c4d/oji.html Probleme OJI]

= Lecție =

== De acasă ==

Având în vedere că ne aflăm în situația de a nu putea ține cercul fizic, vă invit totuși pe fiecare dintre voi să treceți prin lecțiile pe care vi le pregătesc și să participați la concursuri și să lucrați temele pe care vi le propun.

== Coadă ==

=== Definiție ===

Coada este o structură de date de tip FIFO ''(first in, first out)''. Asta înseamnă că elementele sunt adăugate în ordine (ca într-un vector obișnuit) și trebuiesc scoase în ordinea în care au fost adăugate. Un exemplu bun de coadă din viața reală este chiar o coadă de la un magazin: primul venit (primul element adăugat în coadă) este primul servit (primul element care iese din coadă). Prin contrast, stiva era o structură de date de tip LIFO ''(last in, first out)''.

=== Implementare #1 ===

Sunt necesare următoarele operații:
* push/enqueue(value) - inserează o valoare în coadă
* pop/dequeue - șterge prima valoare din coadă
* front - returnează prima valoare din coadă
* size - returnează numărul de elemente din coadă

Exemplu implementare:

<syntaxhighlight>
#define MAXN 1000

int queue[MAXN]; // stocarea valorilor propriu-zise
int queue_left = 0; // indice la prima pozitie din coada
int queue_right = 0; // indice la dreapta ultimului element din coada

// adauga valoarea 'val' la coada, daca aceasta nu este plina
// returneaza 1 in caz de succes, 0 in caz de coada plina
int push( int val ) {
if ( queue_right >= MAXN ) // coada este plina?
return 0; // returnam eroare

queue[queue_right++] = val; // adaugam valoarea in coada
return 1; // returnam succes
}

// returnează valoarea care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top() {
return queue_left < queue_right ? queue[queue_left] : -1;
}

// elimina elementul care este la rand in coada
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
if ( queue_left >= queue_right ) // testam cazul de eroare
return 0;

++queue_left; // daca avem elemente in coada, il eliminam pe primul, mutand cursorul mai in dreapta
return 1;
}

// returneaza numarul de elemente din coada
int size() {
return queue_right - queue_left;
}
</syntaxhighlight>

==== Problemă implementare #1 ====

Coada implementată are o dimensiune maximă egală cu <tt>1000</tt> de adăugiri. Ce se întâmplă dacă vrem să adăugăm <tt>1000</tt> elemente în coadă, să scoatem <tt>500</tt> dintre acestea, și să mai adăugăm încă <tt>500</tt> după? Ar fi ideal să putem face asta, dar implementarea de mai sus nu ne permite.

== Implementare #2: folosind vectori circulari ==

Vom folosi o metodă de implementare care să ne permită să avem un total de maxim <tt>1000</tt> elemente în coadă, nu doar <tt>1000</tt> adăugiri. Vom face acest lucru refolosind golurile care se creează prin eliminarea elementelor din coadă. Vom ține ca și înainte, poziția primului element din coadă și al ultimului. Când depășim limita vectorului adăugând elemente, vom considera că vectorul este circular și vom încerca să adăugăm elementul în "dreapta" limitei. Iar dreapta limitei este chiar poziția <tt>0</tt>.

Exemplu implementare:

<syntaxhighlight>
#define MAXN 1000

int queue[MAXN]; // stocarea valorilor propriu-zise
int queue_left = 0; // indice la prima pozitie din coada
int queue_size = 0; // numarul de elemente din coada

// adauga valoarea 'val' la coada, daca aceasta nu este plina
// returneaza 1 in caz de succes, 0 in caz de coada plina
int push( int val ) {
if (queue_size == MAX_N) // coada este plina?
return 0; // returnam eroare

queue[(queue_left + queue_size) % MAX_N] = val; // adaugam valoarea in coada
++size; // incrementam numarul de elemente
return 1; // returnam succes
}

// returnează valoarea care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top() {
return queue_size > 0 ? queue[queue_left] : -1;
}

// elimina elementul care este la rand in coada
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
if (queue_size == 0) // testam cazul de eroare
return 0;

queue_left = (queue_left + 1) % MAX_N; // daca avem elemente in coada, il eliminam pe primul, mutand cursorul mai in dreapta
--queue_size;
return 1;
}
</syntaxhighlight>

=== Optimizare ===

Am spus într-una din lecțiile anterioare că operațiile modulo sunt lente. Pentru a scăpa de ele în cazul de față, putem declara dimensiunea cozii ca fiind putere a lui 2 și ne vom folosi de operații pe biți, optimizând astfel timpul real de execuție al programului.

== Algoritmul lui Lee ==

Algoritmul lui Lee este similar cu algoritmul Flood Fill, în sensul că face parte din aceeași "familie" a parcurgerilor în matrice. Diferența principală constă în ordinea parcurgerii. Flood Fill parcurge elementele "în adâncime", pornind de la o poziție și extinzându-se într-o direcție cât timp se poate. Când nu se mai poate, schimbă direcția și continuă. Algoritmul lui Lee în schimb, pornește de la o poziție și se extinde în același timp în toate direcțiile posibile, pas cu pas.

=== Aplicații ale algoritmului ===

* Găsirea drumului minim de la un punct la celălalt
* Calcularea distanței minime dintre un punct și toate celelalte

Este de menționat că algoritmul lui Lee poate fi folosit și pentru Fill. Va folosi mai puțină memorie dar va fi mai lent în execuție (din experiență proprie, mult mai lent). Personal, prefer să folosesc Fill când este suficient, pentru că este util, simplu de scris (nu are nevoie de structuri auxiliare, ne putem folosi de stiva recursivității), rapid și își face foarte bine treaba.

=== Exemplificare grafică ===
Sursă: [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_14_-_12_dec_2019#Exemplificare_grafic.C4.83 IQAcademy]

[[File:Wfm_floodfill_animation_queue_wikipedia.gif|frame|none|Exemplu de BFS fill cu 4 direcții]]

A se observa diferența de extindere cu cea din algoritmul [http://algopedia.ro/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_19_-_21_mar_2020#Exemplificare_grafic.C4.83 Flood Fill]

=== Implementare ===

Din punct de vedere al implementării, diferența dintre Lee și Flood Fill este structura folosită. La implementarea algoritmului lui Lee, vom folosi o coadă, spre deosebire de stiva folosită în Fill.

'''Enunț''' Se dă un labirint codificat ca o matrice cu zero și unu, zero semnificând loc liber și unu fiind element obstacol (zid). Se dau de asemenea un punct de start și unul de final. În matrice ne putem deplasa pe linie sau pe coloană, cu condiția să nu avem un obstacol. Să se calculeze, lungimea drumului minim între cele două puncte, dacă există un astfel de drum.

Vom implementa mai întâi coada pe care o vom folosi în algoritmul lui Lee. O posibilă implementare poate arăta așa:

<syntaxhighlight>
#define MAXN 1000

int queue_line[MAXN], queue_col[MAX_N]; // stocarea pozitiilor in coada: linie, coloana
int queue_left = 0; // indice la prima pozitie din coada
int queue_size = 0; // numarul de elemente din coada

// adauga pozitia in coada, daca mai este loc
int push(int line, int col) {
if (queue_size == MAX_N) // coada este plina?
return 0; // returnam eroare

int pos = (queue_left + queue_size) % MAX_N;
queue_line[pos] = line; // adaugam linia in coada
queue_col[pos] = col; // adaugam coloana in coada
++size; // incrementam numarul de elemente
return 1; // returnam succes
}

// returnează linia pozitiei care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top_line() {
return queue_size > 0 ? queue_line[queue_left] : -1;
}

// returnează coloana pozitiei care este la rand in coada, dacă ea exista
// in caz contrar returneaza -1
int top_col() {
return queue_size > 0 ? queue_col[queue_left] : -1;
}

// elimina pozitia care este la rand in coada
// returneaza 1 daca operatia a reusit, 0 in caz de eroare
int pop() {
if (queue_size == 0) // testam cazul de eroare
return 0;

queue_left = (queue_left + 1) % MAX_N; // daca avem elemente in coada, il eliminam pe primul, mutand cursorul mai in dreapta
--queue_size;
return 1;
}
</syntaxhighlight>

Având coada implementată, putem trece la scrierea algoritmului. Vom nota în matricea inițială cu <tt>0</tt> spațiile libere și cu <tt>-1</tt> obstacolele. Vom marca punctul de start cu valoarea <tt>1</tt> și la fiecare pas vom marca vecinii poziției curente incrementând valoarea acesteia. La final, distanța până la punctul de final va fi egală cu valoarea din matrice, din care vom scădea <tt>1</tt> (pentru că am început marcarea de la valoarea <tt>1</tt>).

<syntaxhighlight>
push(startLine, startCol); // adaugam punctul de start in coada
mat[startLine][startCol] = 1; // marcam "distanta" pana la el ca fiind 1

do {
// luam pozitia din coada si distanta pana la ea
line = top_line();
col = top_col();
dist = mat[line][col];

pop(); // scoatem pozitia din coada

for (i = 0; i < 4; ++i) { // parcurgem toti vecinii
newLine = line + dLine[i];
newCol = col + dCol[i];

if (mat[newLine][newCol] == 0) { // daca nu l-am procesat
push(newLine, newCol); // il adaugam in coada
mat[newLine][newCol] = dist + 1; // actualizam distanta pana la el
}
}
} while (queue_size > 0 && (line != stopLine || col != stopCol)); // ne oprim cand nu mai avem elemente in coada sau cand am ajuns la destinatie

printf("Distanta este %d\n", mat[stopLine][stopCol] - 1);
</syntaxhighlight>

==== Detalii implementare ====

* Algoritmul se poate extinde ușor de la 4 vecini la 8 vecini
* Vom folosi aceleași tehnici ca și la Flood Fill:
** Bordarea matricelor pentru a scăpa de testul de ieșire din matrice
** Vectorii de direcție pentru a genera ușor vecinii
* Observați că am oprit bucla în momentul în care punctul pe care îl căutam a fost deja procesat. În cazul de față, bucla poate fi oprită chiar mai devreme (în momentul în care punctul de final este adăugat în coadă). Gândiți-vă cum și de ce!
* Putem modifica algoritmul pentru a calcula distanța minimă către mai multe puncte de final, marcând în matrice care sunt aceste puncte de final. De exemplu, le putem marca în cazul de față cu -2.
* Putem modifica algoritmul să permită plecarea din mai multe puncte simultan. Singura modificare necesară este adăugarea tuturor punctelor inițiale la început în coadă.

=== Complexitate ===

Complexitate timp: O(<tt>M * N</tt>), parcurgând cel mult o dată fiecare element

Complexitate spatiu: O(<tt>M * N</tt>), pentru matricea de distanțe

'''Atenție''' Este posibil să avem nevoie să reținem mai multe informații pentru fiecare poziție (distanța calculată până acum, dacă a mai fost sau nu vizitată poziția, dacă este punct de final, etc.). Sunt cazuri în care putem reține toate informațiile acestea într-o singură matrice, jonglând cu biții numerelor acesteia (primul bit ne spune dacă poziția a fost vizitată, al doilea ne spune dacă este punct de final, ... restul biților țin valoarea distanței). Recomand astfel de practici pentru micșorarea memoriei folosite!

= Temă =

[http://varena.ro/problema/alee alee - varena] 
[https://infoarena.ro/problema/muzeu muzeu - infoarena] 
[https://www.infoarena.ro/problema/traseu3 traseu3 - infoarena] 
[http://varena.ro/problema/insule insule - varena] 
[https://infoarena.ro/problema/cifre4 cifre4 - infoarena]

Clasa a IX-a lecția 17 - 29 feb 2020

2020-02-29T07:33:08Z

Teodor: /* Aplicații */

= Clasament teme lecțiile 1 - 16 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/9a93252412e5f7bcdfe99639c0533708/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/241f0f76f10d91e815402d4a9ea88399/vectori_sortari.html Sortari] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/06c260dd2cf26cadf9bf88be998dc6b6/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/08a54cac8043a383cff2ca5ba837993c/cautare_binara.html Cautare binara] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/bdf146f8f7bdbd3811cc1c10688fd82f/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/6c8953cadbcaac4d669f53998ba05d1e/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/1eebc8685813357f611239e41b5f8d74/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/e3689bb68fe73478de5861088cadfc65/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e5983b771939d54f3c7525c/484359dbaad5a264bc6923af7361d0a5/oji.html Probleme OJI]

= Lecție =

== Sortări (partea II) ==

=== Recapitulare rapidă ===

În [http://algopedia.ro/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_5_-_16_nov_2019 Lecția 5] am vorbit despre mai multe tipuri de sortări, complexitățile și utilizarea lor:
* Sortarea prin selecție
** Timp <tt>O(N2)</tt>
** Spațiu suplimentar <tt>O(1)</tt>
* Sortarea prin vectori de frecvență
** Timp <tt>O(N + MAX_VAL)</tt>
** Spațiu suplimentar <tt>O(MAX_VAL)</tt>
* Sortarea STL
** Timp <tt>O(N * logN)</tt>
** Spațiu suplimentar <tt>O(1)</tt>

V-am recomandat ca în condiții de concurs să folosiți sortarea prin vectori de frecvență dacă limitele problemei permite, iar în caz contrar să folosiți funcția sort.

=== Funcția de comparare ===

Sortările despre care am vorbit până acum, în complexitate fie <tt>O(N2)</tt>, fie <tt>O(N * logN)</tt> fac parte din categoria sortărilor prin comparare. Acestea funcționează comparând elementele între ele două câte două în funcție de un anumit criteriu, sau altfel spus, o metodă / funcție de comparare.

La sortările deja învățațe scrise de noi (sortarea prin selecție), avem control asupra implementării acestora și putem schimba ușor metoda de comparare. În majoritatea cazurilor, este suficient să schimbăm un singur semn: <tt><, <=, >, >=</tt>.

Ce se întâmplă în cazul sortării din STL? În mod implicit, funcția sort ne ordonează elementele în ordine crescătoare. Dar putem să îi schimbăm metoda de comparare astfel:

<syntaxhighlight>
// Returneaza true daca primul argument trebuie sa fie la stanga celui de-al doilea
bool cmp(int a, int b) {
if (a < b) // Daca primul argument este mai mic decat cel de-al doilea
return true; // Atunci el trebuie sa fie la stanga
return false;
}

sort(v, v + n, cmp);
</syntaxhighlight>

Funcția scrisă mai sus este chiar funcția implicită, pentru că va sorta elementele vectorului în ordine crescătoare. Ce trebuie să facem dacă vrem ca apelul funcției <tt>sort</tt> să ordoneze elementele descrescător? Schimbăm semnul în <tt>></tt>.

=== Sortare obiecte cu vectori tip permutare ===

Este posibil să avem nevoie să sortăm și obiecte mai complexe, nu doar numere întregi sau reale. Să luăm următorul exemplu:

'''Exercițiu''' Se citește un număr <tt>N</tt> și apoi <tt>N</tt> intervale închise, reprezentate prin capătul stânga, respectiv capătul dreapta al acestora. Să se ordoneze aceste intervale crescător după capătul din stânga, iar în caz de egalitate crescător după capătul din dreapta.

Putem reține capetele din stânga ale intervalelor într-un vector <tt>X</tt>, iar capetele din dreapta într-un vector <tt>Y</tt>. Avem nevoie să ordonăm cei doi vectori în "paralel". O metodă eficientă pentru a face asta este să ne folosim de un vector auxiliar de dimensiune <tt>N</tt>, pe care când îl parcurgem de la stânga la dreapta, să parcurgem pozițiile intervalelor în ordinea lor sortată. Altfel spus, vectorul nou creat este o permutare a pozițiilor din cei doi vectori. Exemplu:

* <tt>| 0 | 1 | 2 | 3 | 4 | 5 |</tt> <tt>(P)</tt>
* <tt>| 5 | 3 | 6 | 3 | 2 | 1 |</tt> <tt>(X)</tt>
* <tt>| 6 | 5 | 8 | 4 | 7 | 3 |</tt> <tt>(Y)</tt>

Inițial, vetorul <tt>P</tt> este permutarea identică, intervalele noastre fiind încă nesortate. În timpul sortării, vom compara elementele prin vectorul <tt>P</tt>: <tt>X[P[i]]</tt> cu <tt>X[P[j]]</tt> și <tt>Y[P[i]]</tt> cu <tt>Y[P[j]]</tt>, și vom interschimba elementele <tt>P[i]</tt> și <tt>P[j]</tt> la nevoie. Altfel spus, în loc să interschimbăm între ele intervalele efective, interschimbăm pozițiile acestora.

Cum scriem acest lucru folosind funcția sort?

<syntaxhighlight>
bool cmp(int a, int b) { // a si b sunt pozitii, vom compara x[a] cu x[b] si y[a] cu y[b]
if (x[a] < x[b]) // Daca capatul din stanga este mai mic
return true; // Intervalul de pe pozitia a trebuie sa fie in stanga celui de pe pozitia b
if (x[a] > x[b]) // Daca capatul din stanga este mai mare
return false;
if (y[a] < y[b]) // Daca capetele din stanga sunt egale si capatul din dreapta este mai mic
return true;
return false;
}

for (i = 0; i < n; ++i)
p[i] = i;
sort(p, p + n, cmp);
</syntaxhighlight>

== Creare tip nou de date (struct) ==

Pe lângă tipurile de date de bază oferite de limbaj <tt>(bool, char, short, int, long long, float, double)</tt> ne putem crea o structură de date a noastră. Pentru simplitate, vom folosi exemplul anterior și vom crea o structură de date care să rețină un interval.

<syntaxhighlight>#include <stdio.h>

// Structura Interval, contine doi intregi a si b
struct Interval {
int a, b;
};

int main() {
Interval itv;
itv.a = 3;
itv.b = 5;

printf("Intervalul este: [%d, %d]", itv.a, itv.b);

return 0;
}
</syntaxhighlight>

Am creat o structură <tt>Interval</tt> care conține doi întregi <tt>a</tt> și <tt>b</tt>, accesibili prin intermediul operatorului "<tt>.</tt>". Această structură poate fi folosită în program la fel ca orice alt tip de date cu care suntem deja obișnuiți.

=== Sortare intervale ===

Vrem acum să ordonăm intervalele reținute în structura creată, așa cum am făcut și în varianta anterioară.

<syntaxhighlight>
bool cmp(Interval i1, Interval i2) {
if (i1.a < i2.a)
return true;
if (i1.a > i2.a)
return false;
if (i1.b < i2.b)
return true;
return false;
}

Interval v[100];
int n;

sort(v, v + n, cmp);
</syntaxhighlight>

== Aplicații ==

[https://infoarena.ro/runda/concurs_9_17 Concurs virtual]

= Temă =

[https://www.infoarena.ro/problema/reactivi reactivi - infoarena] 
[https://www.infoarena.ro/problema/int int - infoarena] 
[https://www.infoarena.ro/problema/z z - infoarena]

Clasa a IX-a lecția 16 - 22 feb 2020

2020-02-22T20:42:33Z

Teodor: /* Pe categorii */

= Clasament teme lecțiile 1 - 15 =

=== Pe categorii ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/8b66a2132445b5314f63e3bc7af34325/divizori.html Divizori / Primalitate / Ciur] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/358d91ebaa53e920dc4ebf26e7941255/vectori_sortari.html Sortari] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/173c7f01b3814d2000ad238d8f74ba6d/matrici.html Matrici] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/e2c3470fbacad152d628b96a24269102/cautare_binara.html Cautare binara] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/a930102abfe7366ad03e480b29a7233d/stiva.html Stivă] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/b5aa09c69278cd8e9287fdf845e4cac6/recursivitate.html Recursivitate] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/f1970032d58d5993d4ec39e195f4ffbd/generale.html Generale]

=== Concursuri ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/1db9dbcab8260b3a485de9c2048de8ee/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e514c2d4fad621eb5775620/63c5d4b5f3269c9a9892172b66a24366/oji.html Probleme OJI]

= Lecție =

== Recursivitate ==

Recursivitatea este o tehnică utilă pe care o putem folosi în multe cazuri. În general, vrem să spargem o problemă mai complicată în mai multe probleme mai simple, la care putem răspunde rapid, fără prea mult efort.

O funcție recursivă este o funcție care se apelează pe ea însăși. Pentru a o scrie, trebuie să avem în vedere următoarele:

* Formula recurentă bine stabilită.
* Cazurile simple pentru care știm deja să rezolvăm problema.
* Considerând că funcția ne furnizează deja rezultatul dorit pentru cazurile "mai mici", cum ne folosim de rezultatul acestora pentru a răspunde corect la cazul curent.

== Exemple ==

=== Factorial ===

Calcul n! Ne vom folosi de definiția recursivă: <math>n! = \begin{cases} 1, & \mbox{dacă } n = 1 \\ n \cdot (n - 1)!, & \mbox{dacă } n > 1. \end{cases}</math>

<syntaxhighlight>int fact(int n) {
if (n == 1)
return 1;
return n * fact(n - 1);
}</syntaxhighlight>

==== Explicație ====

Funcția trebuie să ne calculeze <tt>n!</tt>. Un caz simplu la care știm să răspundem este: <tt>1! = 1</tt>. Pentru toate celelalte cazuri, ne vom baza pe faptul că funcția va returna răspunsul corect pentru <tt>n - 1</tt> și anume <tt>(n - 1)!</tt>, rezultat pe care îl vom lua și îl vom înmulți cu <tt>n</tt> pentru a obține <tt>n!</tt>.

=== Suma cifrelor unui număr ===

Problema este și pe varena: [http://varena.ro/problema/sumacfnr sumacfnr].

<syntaxhighlight>int sumcf(int n) {
if (n < 10)
return n;
return n % 10 + sumcf(n / 10);
}</syntaxhighlight>

==== Explicație ====

Cazul simplu la care știm să răspundem este acela în care numărul nostru este format dintr-o singură cifră, suma cifrelor unui astfel de număr fiind chiar numărul. Pentru celelalte numere, suma cifrelor lor este egală cu ultima cifră plus suma cifrelor numărului din care ștergem ultima cifră.

=== Scrierea numerelor în ordinea inversă citirii ===

Se citește de la tastatură un număr <tt>N</tt> și un șir de <tt>N</tt> numere naturale. Să se scrie numerele în ordinea inversă citirii:

<syntaxhighlight>#include <stdio.h>

void afisare(int n) { // n reprezintă numarul de valori ramase de citit
if (n == 0) // daca nu mai avem nimic de citit, intrerupem functia.
return;

int x;
scanf("%d", &x); // citim o valoare
afisare(n - 1); // trecem mai departe pentru a citi restul valorilor
printf("%d ", x); // afisam valoarea la intoarcerea din apelurile recursive
}

int main() {
int n;
scanf("%d", &n);
afisare(n); // initial, mai avem de citit n valori

return 0;
}</syntaxhighlight>

=== Descompunerea în baza 2 ===

<syntaxhighlight>void baza2(int n) {
if (n <= 1) { // daca n este 0 sau 1
printf("%d", n); // descompunerea lui in baza 2 este chiar n
return;
}

baza2(n / 2);
printf("%d", n % 2);
}</syntaxhighlight>

O altă variantă de a scrie această funcție:

<syntaxhighlight>void baza2(int n) {
if (n > 1)
baza2(n / 2);
printf("%d", n % 2);
}</syntaxhighlight>

== Top-Down vs Bottom-Up ==

Am discutat despre cele două metode de implementare ale funcțiilor recursive și diferențele între acestea. O sursă în care sunt explicate foarte fain conceptele și în care găsiți multe exemple: [http://algopedia.ro/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_7_-_24_oct_2019#Recursie_Top-Down IQAcademy].

== Aplicații ==

[http://varena.ro/problema/sumacfnr varena - sumacfnr] 
[http://varena.ro/problema/sumadiv varena - sumadiv] 
[http://varena.ro/problema/nset varena - nset]

= Temă =

==== Recursivitate ====

[http://varena.ro/problema/sumacfnr varena - sumacfnr] 
[http://varena.ro/problema/sumadiv varena - sumadiv] 
[http://varena.ro/problema/nset varena - nset] 
[http://varena.ro/problema/invector varena - invector] 
[http://varena.ro/problema/maxrec varena - maxrec] 
[http://varena.ro/problema/primrec varena - primrec] 
[http://varena.ro/problema/factorizare varena - factorizare] 
[http://varena.ro/problema/fibonacci varena - fibonacci]

==== OJI ====
[https://infoarena.ro/problema/pic infoarena - pic]

Clasa a IX-a lecția 14 - 8 feb 2020

2020-02-08T07:52:05Z

Teodor: /* Clasament teme lecțiile 1 - 13 */

= Clasament teme lecțiile 1 - 13 =

== Old School ==

=== Clasamente avansați ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e3dc96357713373087c7542/2a1b6f01e2d4f1f0dabfcc2dfb5f42b9/avansati_iarena.html Avansați Infoarena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e3dc96357713373087c7542/a0c42afee99bfe033a388a25a8248be5/avansati_varena.html Avansați Varena]

=== Clasamente începători ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e3dc96357713373087c7542/d5704cf3e3f696638dc0048fa3754044/incepatori_varena.html Începători Varena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e3dc96357713373087c7542/8e2d4726afb78e993bc1863b642a7a18/incepatori_iarena.html Începători Infoarena]

== New School ==

[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e3dc96357713373087c7542/2471018ae98d94ef789736f81af557e7/osi.html Probleme OȘI] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e3dc96357713373087c7542/99ddb10b43c2637b880bcec032e42487/oji.html Probleme OJI]

To be continued: clasamente pe categorii (divizori/numere prime, vectori frecventa/caracteristici, sortari, cautare binara, caractere, baze de numeratie/operatii pe biti, etc.)

= Lecție =

== Funcții în limbajul C ==

Am discutat despre funcții folosind ca sursă principală lecția de la IQAcademy: [http://algopedia.ro/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_37_-_29_mai_2019 Funcții în limbajul C]

== Adăugiri în limbajul C++ ==

=== Modificarea parametrilor cu efect la ieșirea din funcție ===

Cum majoritatea dintre voi folosiți deja elemente de C++ în cod, este util să știți că C++ permite trimiterea variabilelor către funcții prin referință:

==== Exemplu: functia swap ====
<syntaxhighlight>#include <stdio.h>

void swap( int &pa, int &pb ) {
int aux;

aux = pa;
pa = pb;
pb = aux;
}

int main() {
int a, b;

a = 100;
b = 200;
swap( a, b );
printf( "a=%d b=%d\n", a, b );

return 0;
}</syntaxhighlight>

După cum se poate observa, referințele permit accesarea directă a variabilelor înauntrul funcției, nemaifiind nevoie de utilizarea operatorului *(pointer).

== Aplicații ==

V-am pregătit un [https://infoarena.ro/runda/concurs_9_avansati_2 Concurs Virtual].

Pentru cei care au lucrat deja problemele acestea, o listă de probleme pe care le vom discuta și în lecțiile următoare:

[https://infoarena.ro/problema/defrag infoarena - defrag] 
[https://infoarena.ro/problema/betasah infoarena - betasah] 
[https://infoarena.ro/problema/elicop infoarena - elicop]

= Temă =

[http://varena.ro/problema/tinta varena - țintă] 
[https://infoarena.ro/problema/cifre5 infoarena - cifre5] 
[https://infoarena.ro/problema/placare infoarena - placare] (Greuță) 
[https://infoarena.ro/problema/triang infoarena - triang] (Grea)

== În plus pentru începători ==

Ca temă adițională aveți următoarele probleme, ca aplicații la divizori, descompunere în factori primi și ciurul lui Eratostene:

[https://infoarena.ro/problema/cufar infoarena - cufar] 
[https://infoarena.ro/problema/divmul infoarena - divmul]

Soluțiile problemelor pot fi găsite [http://algopedia.ro/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_3_-_26_oct_2019 aici]. Problema cufăr este explicată detaliat [http://algopedia.ro/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_4_-_2_nov_2019 aici].

Clasa a IX-a lecția 13 - 1 feb 2020

2020-01-31T19:46:54Z

Teodor: /* Clasament teme lecțiile 1 - 12 */

= Clasament teme lecțiile 1 - 12 =

[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e348323966e3a4a367ec268/b0c63433d7eada937e4578da32060cfd/olimpiada_scoala.html Probleme Olimpiada pe Școală]

=== Clasamente avansați ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e348323966e3a4a367ec268/5f97cc3353c37dad64686e96e2583213/avansati_iarena.html Avansați Infoarena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e348323966e3a4a367ec268/75147de11035811b36abccb72186561b/avansati_varena.html Avansați Varena]

=== Clasamente începători ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e348323966e3a4a367ec268/151df26db6d8f2418166f3ca3793e3ec/incepatori_varena.html Începători Varena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e348323966e3a4a367ec268/f448e7885ae3f400862f136bfdcc666c/incepatori_iarena.html Începători Infoarena]

= Lecție =

== Matrice ==
Sursă: [http://algopedia.ro/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_9_-_15_nov_2018 IQAcademy]

Matricele sunt asemănătoare cu vectorii, dar cu două dimensiuni.

=== Declarare matrice ===
Matricele se declară similar cu vectorii, însă cu o dimensiune în plus:
<syntaxhighlight>int a[100][500];</syntaxhighlight>
Primul număr, <tt>100</tt> în cazul nostru, reprezintă numărul de linii al matricei <tt>a</tt>. Al doilea număr, <tt>500</tt> în exemplul de mai sus, reprezintă numărul de coloane al matricei <tt>a</tt>, sau numărul de elemente al fiecărei linii. O matrice poate fi privită ca un vector de vectori. În exemplul de mai sus <tt>a</tt> poate fi privită ca un vector de <tt>100</tt> de elemente. Fiecare element al acestui vector este, la rândul lui, un alt vector, de <tt>500</tt> de elemente. Numărul total de elemente al matricei <tt>a</tt> este <tt>100</tt> x <tt>500</tt>, adică <tt>50000</tt> de elemente întregi.

=== Citire matrice ===
Cum citim o matrice? Asemănător cu un vector, vom citi mai întîi numărul de linii și numărul de coloane, apoi elementele. Elementele se citesc, în general, de-a lungul liniilor, fiecare linie fiind citită ca un vector:
<syntaxhighlight>...
fscanf(fin, "%d%d", &m, &n);
for (i = 0; i < m; ++i)
for (j = 0; j < n; ++j)
fscanf(fin, "%d", &a[i][j]);
</syntaxhighlight>

=== Scriere matrice ===
Scrierea este asemănătoare cu citirea, cu mențiunea să avem grijă să tipărim un <tt>'\n'</tt> la finalul fiecărei linii:
<syntaxhighlight>...
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j)
fprintf(fout, "%d ", a[i][j]);
fprintf(fout, "\n");
}</syntaxhighlight>

=== Căutare element în matrice ===
<syntaxhighlight>i = j = 0;
while ((i < m) && (a[i][j] != e)) { // cat timp nu am trecut de ultima linie si numarul pe care suntem nu este cel cautat
j++; // trecem pe urmatoarea coloana
if (j >= n) { // daca am trecut de ultima coloana
i++; // trecem pe urmatoarea linie
j = 0; // resetam coloana pe zero
}
}</syntaxhighlight>

=== Transpunere matrice ===
Se dă o matrice pătrată, să se modifice astfel încît în final elementele ei să fie oglindite față de diagonala principală. Diagonala principală e cea care începe în colțul din stînga-sus și se termină în colțul din dreapta-jos. Această operațiune se mai numește si ''transpunere''.
<syntaxhighlight>for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ ) {
aux = a[i][j];
a[i][j] = a[j][i];
a[j][i] = aux;
}</syntaxhighlight>

Aceeași problemă pentru diagonala secundară. Diagonala secundară e cea care începe în colțul din dreapta-sus și se termină în colțul din stînga-jos
<syntaxhighlight>for ( i = 0; i < (n - 1); i++ )
for ( j = 0; j < (n - i); j++ ) {
aux = a[i][j];
a[i][j] = a[n - 1 - j][n - 1 - i];
a[n - 1 - j][n - 1 - i] = aux;
}</syntaxhighlight>

== Aplicații ==

[http://varena.ro/problema/matrix varena - matrix] 
[http://varena.ro/problema/diagonal varena - diagonal] 
[http://varena.ro/problema/zoomx2 varena - zoomx2] 
[http://varena.ro/problema/cautare varena - cautare]

== Pentru cei începători ==

Am reluat construirea unui vector cu numere prime utilizând ciurul lui Eratostene și am dat ca exemplu de utilitate descompunerea rapidă în factori primi a multor numere.

= Temă =

[http://varena.ro/problema/matrix varena - matrix] 
[http://varena.ro/problema/diagonal varena - diagonal] 
[http://varena.ro/problema/zoomx2 varena - zoomx2] 
[http://varena.ro/problema/cautare varena - cautare] 

[https://infoarena.ro/problema/cri infoarena - cri] (Bonus)

== În plus pentru începători ==

[https://infoarena.ro/problema/maxd infoarena - maxd] 
[https://infoarena.ro/problema/vase infoarena - vase] (Opțional)

Clasa a IX-a lecția 12 - 25 ian 2020

2020-01-27T18:35:28Z

Teodor: /* Lecție */

= Clasament teme lecțiile 1 - 11 =

=== Clasamente avansați ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e2b41852d62105314237301/831651748e8ebfd6bbea1f3e5865ba1a/avansati_iarena.html Avansați Infoarena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e2b41852d62105314237301/1cb780be242a1f5a0fa96d0ab9963087/avansati_varena.html Avansați Varena]

=== Clasamente începători ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e2b41852d62105314237301/3bc8fdd13b8b478ad893245cb6faa2c5/incepatori_varena.html Începători Varena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e2b41852d62105314237301/ab81f4deed02ba00ede4bf0b03c58086/incepatori_iarena.html Începători Infoarena]

= Lecție =

== Olimpiada pe scoală ==

Am extras toate problemele date la olimpiada pe școală de pe varena. [https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e2b41852d62105314237301/9657f10447173fde7a2c3c2f4a0e8f0b/index.html Click aici!]

În această lecție, vom lucra și vom discuta aceste probleme. Printre voi sunt și elevi care au lucrat majoritatea problemelor de aici (Andrei Croitoru, Sebastian Marcu, Rareș Ciociea). Cei în această situație veți lucra din problemele rămase restante la teme (probleme nelucrate sau probleme la care nu ați obținut punctaj maxim). Voi discuta problemele acestea separat cu voi.

== Concurs ==

V-am pregătit un concurs virtual care conține probleme date la olimpiada pe școală, extrase în același mod. [http://varena.ro/runda/pregatire_9_scoala Click aici!]

Este un concurs virtual, fără evaluare publică. Scopul este să simulăm condițiile de olimpiadă, deci nu trimiteți surse în arhiva de probleme ca să vedeți ce punctaj ați obținut!

== Recuperare cu cei începători ==

Am făcut un rezumat al primelor lecții pentru cei începători, cu accent pe lecțiile cu divizori, descompuneri în factori primi și ciurul lui Eratostene. Planul este ca să ajungeți să lucrați din temele date celor avansați. Pentru asta e nevoie de un efort mai mare din partea voastră în lecțiile care urmează.

= Temă =

Lucrați în continuare problemele date la olimpiada pe școală, din [https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e2b41852d62105314237301/9657f10447173fde7a2c3c2f4a0e8f0b/index.html această listă].

Lucrați de asemenea problemele rămase restante.

Cerc clasa a 9-a, anul 2019-2020

2020-01-25T13:46:56Z

Teodor: /* Elevii cercului de informatică clasa a IXa și prezența la curs */

== Elevii cercului de informatică clasa a IXa și prezența la curs ==
{| class="wikitable" style="float:left;"
! Nr.
|-
|01
|-
|02
|-
|03
|-
|04
|-
|05
|-
|06
|-
|07
|-
|08
|-
|09
|-
|10
|-
|11
|-
|12
|-
|13
|-
|14
|-
|15
|-
|16
|-
|17
|-
|18
|-
|19
|-
|20
|-
|21
|-
|22
|-
|23
|-
|24
|-
|25
|-
|26
|-
|27
|-
|28
|-
|29
|-
|30
|}

{| class="wikitable" style="float:left;"
! Nume !! L01 !! L02 !! L03 !! L04 !! L05 !! L06 !! L08 !! L09 !! L10 !! L11 !! L12
|-
| Dinu Dunăreanu || P || P || P || P || P || P || P || P || P || P ||
|-
| Vladuțu Cristian Vlad || P || P || P || P || || || || P || || ||
|-
| Andrei Bem || P || P || P || || || P || P || P || P || P || P
|-
| Rares Ciociea || P || P || P || || || P || P || P || P || P ||
|-
| Andrei Croitoru || P || P || P || P || || P || P || P || P || || P
|-
| Radu Negovan || P || P || || || || || || || || ||
|-
| Rareș Niță || P || P || P || P || || P || P || P || P || P ||
|-
| Elena Curecheriu || || P || P || || || || || || || ||
|-
| Ilinca Venescu || || P || || || || || || || || ||
|-
| Luca Cirimpei || || P || || P || P || || || || || P ||
|-
| Mihai Zegheru || || P || P || P || P || || P || P || || P || P
|-
| Antonia - Teodora Dinu || || P || P || P || P || || P || P || || ||
|-
| Teodora Nae || || P || P || P || P || P || P || P || P || || P
|-
| Ciprian Cristescu || || P || || P || P || || || P || || ||
|-
| Andrei Trache || || P || || || || || P || P || P || ||
|-
| Alexandru Andrei Tudor || || P || P || || || || || || || ||
|-
| Matei Nicărel || || P || P || || || || || || || ||
|-
| Ștefan Ghenescu || || P || P || || || || || || || ||
|-
| Alexia Ecaterinca Cârstea || || P || P || || || || || || || ||
|-
| Victor Vasiliu || || P || || || || || || || || ||
|-
| Sebastian Marcu || || P || P || || P || || P || P || || P || P
|-
| Cosmin Moldoveanu || || P || || || || || || || || ||
|-
| Cristina Mitu || || P || || P || || || || P || P || P ||
|-
| Alexandra Dinu || || P || P || || P || P || P || P || P || || P
|-
| Dragoș Ștefan Lupu || || P || P || P || P || P || P || P || || || P
|-
| Popa Petru || || || P || || || || || || || ||
|-
| Beznes Mircea || || || P || || || || || || || ||
|-
| Albu Victor || || || P || || || || P || P || || ||
|-
| Anica - Popa Vlad - Ioan || || || P || P || P || || P || P || P || || P
|-
| Rotaru Elena Alexia || || || P || || || || || || || P ||
|}
<div style="clear:both;">
''Log de schimbări'':
</div>

Clasa a IX-a lecția 11 - 18 ian 2020

2020-01-18T07:43:52Z

Teodor: /* Varianta 1 */

= Clasament teme lecțiile 1 - 10 =

=== Clasamente avansați ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e221029a026f56e01a234b5/f36671b2ce0e16f85f85fae22987dd3d/avansati_iarena.html Avansați Infoarena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e221029a026f56e01a234b5/7973065d100a42d71cfb315282ef3744/avansati_varena.html Avansați Varena]

=== Clasamente începători ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e221029a026f56e01a234b5/b9f9cd3e086d5f79be886e3b2fcb31f3/incepatori_varena.html Începători Varena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e221029a026f56e01a234b5/d46279cd90291aaf7150730862777849/incepatori_iarena.html Începători Infoarena]

= Lecție =

== Căutare binară ==

=== Varianta 1 ===

'''Sursa''': [http://algopedia.ro/wiki/index.php/Clasa_a_VI-a_lec%C8%9Bia_4_-_11_oct_2018 IQAcademy]

Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector. Căutarea clasică într-un vector de ''n'' elemente are o complexitate de ''O(n)''. Putem micșora această complexitate dacă vectorul este ordonat.

Să ne folosim de o analogie: cum căutam un cuvînt în dicționar? Dicționarul are circa 60000 de cuvinte. Dacă am căuta la rînd, liniar, ne-ar lua zile să-l găsim. Și atunci deschidem dicționarul undeva, să spunem la mijloc. Ne uităm la ce literă sîntem, să spunem 'm'. Dacă noi căutăm 'gorilă', știm că 'g' < 'm', deci vom căuta la stînga, eliminînd jumate din dicționar. Vom continua la fel, deschidem undeva la jumate în jumatea rămasă și vedem iarăși la ce literă sîntem. Atunci cînd ajungem la litera 'g' vom continua cu a doua literă. În acest fel vom găsi cuvîntul rapid, probabil în jumate de minut, în loc de zile.

Aceasta este metoda căutării binare. Dacă vectorul nostru este ordonat, putem căuta mai întîi la jumate. Dacă elementul din vector este mai mic decît elementul căutat înseamnă că trebuie să ne uităm în jumătatea dreaptă, altfel ne uităm în cea stîngă. Apoi, în vectorul rămas, vom repeta algoritmul. La fiecare pas vom înjumătăți numărul de numere rămase. Ne oprim atunci cînd subvectorul rămas are fix un element. Dacă este elementul căutat, returnăm poziția sa, altfel el nu există. Iată o implementare posibilă:

<syntaxhighlight>stinga = 0;
dreapta = n;
while ( dreapta - stinga > 1 ) {
mijloc = (stinga + dreapta) / 2;
if ( v[mijloc] > e )
dreapta = mijloc;
else
stinga = mijloc;
}
if ( e == v[stinga] ) {
// ... găsit, procesare aici ...
}</syntaxhighlight>

'''Observație importantă''': ''stinga'' este prima poziție in vectorul căutat, iar ''dreapta'' este prima poziție în afara vectorului căutat.

Ce complexitate are căutarea binară? Să observăm că la fiecare iterație a buclei <code>while</code> diferența dintre ''dreapta'' și ''stinga'' se reduce la jumate. Ne vom opri atunci cînd ea devine 1. Bucla se va executa, deci, de cîte ori putem împărți diferența la doi, deci ''O(log n)'' unde ''n'' este numărul de elemente pe care se face căutarea.

Varianta de program de mai sus găsește ultima apariție a lui ''e''. Ea poate fi adaptată să găsească prima apariție, gîndiți-vă cum. De asemenea, căutarea binară poate fi adaptată să găsească poziția la care s-ar putea insera un element ''e'' în vector.

'''Atenție'''! Căutarea binară este faimoasă pentru ușurința cu care o puteți greși. Pentru a vă asigura că nu veți avea greșeli la implementare respectați următoarele reguli:

# Intervalul de căutare să fie '''închis''' la un capăt și '''deschis''' la celălalt, iar testul de oprire să fie ca diferența dintre capete să fie strict mai mare ca unu. Dacă respectați această convenție evitați bug-urile de final de căutare cînd indicii rămîn pe loc și o condiție incorectă in while poate să ducă la o buclă infinită.
# Comparația cu elementul să fie totdeauna de tip '''strict''' (mai mic sau mai mare, nu mai mic sau egal).
# Cînd comparația este adevărată se va muta în mijloc capătul '''deschis''' al intervalului.

=== Varianta 2 ===

O altă variantă a acestui algoritm se folosește de faptul că orice număr poate fi scris ca sumă de puteri ale lui 2 (având în vedere descompunerea în baza 2). Mai precis, orice poziție din vector poate fi scrisă ca sumă de puteri ale lui 2. Pentru un vector v de n elemente, algoritmul funcționează astfel:

1. Găsește cea mai mare putere a lui 2 mai mică sau egală cu n. O notăm cu ''step''.
2. Setează poziția curentă de căutare la stânga vectorului, adică -1. O notăm cu ''pos''.
3. Testăm elementul v[pos + step]:
3.1. Dacă este mai mare decât elementul căutat, ne deplasam cu poziția curentă: <code>pos += step</code>.
3.2. Dacă este mai mic decât elementul căutat, nu vrem să ne deplasăm pentru ca am trece de el.
4. Înjumătățim step: <code>step /= 2</code>
5. Ne întoarcem la pasul 3, oprindu-ne când step devine 0.

O metodă de implementare:

<syntaxhighlight>
...
int pos = -1, step = 1;

// Calculam cea mai mare putere a lui 2, mai mica sau egala decat n
while (step * 2 <= n)
step *= 2;

while (step > 0) {
if (pos + step < n && v[pos + step] <= e)
pos += step;
step /= 2;
}

if (pos != -1 && v[pos] == e) {
// gasit!
}
</syntaxhighlight>

'''Atenție''' La fiecare pas, trebuie să ne asigurăm că nu ieșim din limitele vectorului!
'''Atenție''' La final, trebuie să ne asigurăm atât că pos nu a rămas la poziția inițială de -1, cât și că elementul de pe poziția pos este cel căutat.

Această variantă de implementare ne va întoarce tot ultima apariție a lui e. Gândiți-vă ce trebuie schimbat pentru a întoarce prima poziție.

'''Observație''' Nu este neapărat necesar să calculăm cea mai mare putere a lui 2 mai mică sau egală decât n. Putem seta o valoare implicită mai mare decât maximul lui n. Exemplu:

<syntaxhighlight>
...
int pos = -1, step = 1 << 20; // 2^20, in cazul in care n nu depaseste ~1 milion
...
</syntaxhighlight>

== Aplicații ==

Sunt multe aplicații care se folosesc de această tehnică. Vom discuta aici câteva, după care vă veți apuca să le lucrați. Sunteți liberi să folosiți orice variantă a algoritmului, atât timp cât vă asigurați că o înțelegeți bine.

=== Căutare binară pe un vector ===

[http://varena.ro/problema/cautbin varena - cautbin] 
Am descris mai sus cum se poate folosi căutarea binară pentru a căuta un număr într-un vector ordonat. Aceasta este o problemă clasică pe care veți învăța să folosiți diverse moduri de a căuta binar.

=== Căutare binară pe o funcție ===

[https://infoarena.ro/problema/fact infoarena - fact] 
Căutarea unui element într-un vector nu este singura întrebuințare a căutarii binare. Putem folosi acest algoritm pentru a afla în ce punct are o funcție (matematică sau... "informatică") o anumită valoare. Evident, funcția trebuie să monotonă. Să luăm de exemplu funcția:

* f(x) = numărul de zero-uri în care se termină ''x!''

Funcția este crescătoare, deci dacă dorim să găsim cel mai mic număr natural pentru care ''f(x)'' are ''e'' zerouri, putem folosi căutarea binară. Este mult mai rapid decăt parcurgem toate numerele de la stânga la dreapta începând cu 1, să calculăm valoarea lui ''f(x)'' pentru fiecare în parte și să ne oprim când dăm de o valoare egală cu ''e''.

'''Observație''' Nu trebuie să generăm toate valorile funcției înainte, nu trebuie să le știm pe toate. Ne interesează doar valorile în punctele prin care trecem folosind căutarea binară.

=== Căutare binară a răspunsului ===

[https://infoarena.ro/problema/transport infoarena - transport]

Sunt multe probleme în care ni se cere să găsim valoarea minimă / maximă care respectă o anumită proprietate. Să notăm astfel:
* f(x) = 0, dacă x nu respectă proprietatea
* f(x) = 1, dacă x respectă proprietatea

Dacă funcția noastră este monotonă, ea va arăta ceva de genul următor:

<tt>| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |</tt> 
<tt>| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |</tt>

În acest moment, este evident că putem aplica o căutare binară pe ea, vom verifica la fiecare pas valoarea funcției în poziția la care suntem în căutare și vom decide dacă ne vom deplasa la stânga sau la dreapta. Altfel spus, la fiecare pas vom verifica dacă valoarea la care am ajuns respectă sau nu proprietatea problemei.

= Temă =

=== Începători ===
[http://varena.ro/problema/cautbin varena - cautbin] 
[https://infoarena.ro/problema/fact infoarena - fact]

=== Avansați ===
[http://varena.ro/problema/cautbin varena - cautbin] 
[https://infoarena.ro/problema/fact infoarena - fact] 
[https://infoarena.ro/problema/transport infoarena - transport] 
[https://infoarena.ro/problema/triang infoarena - triang] 
[https://infoarena.ro/problema/loto infoarena - loto] 
[https://infoarena.ro/problema/gfact infoarena - gfact]

Clasa a IX-a lecția 10 - 21 dec 2019

2020-01-17T19:52:58Z

Teodor: /* Clasamente avansați */

= Clasament teme lecțiile 1 - 9 =

=== Clasamente avansați ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5df3f6560cc1cb6840af0df8/0a92eba81f4b1ad733b57d3b553a1f91/avansati_iarena.html Avansați Infoarena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e1e107e984133682ed4db32/9173edbf3848b1032e15d4df3f65b073/avansati_varena.html Avansați Varena]

=== Clasamente începători ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e1e107e984133682ed4db32/f74cdc8209f2b079010a5bb04311d974/incepatori_varena.html Începători Varena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5e1e107e984133682ed4db32/ed8a70e6ed8faf13f2445c60c71cc403/incepatori_iarena.html Începători Infoarena]

= Concurs =

Am creat două concursuri la care veți participa de acasă. După concurs, voi adăuga problemele date în clasamentul temelor.

== Cuvânt înainte ==

Scopul concursurilor nu este să luați 100 puncte cu orice preț. Pe durata concursului, tratați problemele cu seriozitate și rezolvați-le fără ajutor din surse externe (și aici mă refer în principal la problemele care au soluțiile oficiale deja publicate prin diverse locuri).

'''Atenție!''' Concursurile nu au evaluare publică. Asta înseamnă că nu veți vedea punctajele finale în timpul acestora. Nu trișați trimițând surse către arhiva de probleme pentru a vedea rezultatele în timpul concursului.

=== Concurs începători ===

[http://varena.ro/runda/concurs_9_incepatori2 Concurs Începători]

=== Concurs avansați ===

[https://www.infoarena.ro/runda/concurs_9_avansati Concurs Avansați]

= Temă =

Continuați să lucrați temele lăsate din toate lecțiile trecute.

=== Pentru cei începători ===

După vacanță vom continua materia într-un ritm mai alert. Rugămintea este să lucrați problemele rămase restante în teme!

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

2019-12-15T18:57:52Z

Teodor: /* Interclasare vectori */

= Clasament teme lecțiile 1 - 8 =

=== Clasamente avansați ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5df3f6560cc1cb6840af0df8/0a92eba81f4b1ad733b57d3b553a1f91/avansati_iarena.html Avansați Infoarena] 
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5df3f6560cc1cb6840af0df8/4c152f3acfc15f0136727ef69070bbee/avansati_varena.html Avansați Varena]

=== Clasamente începători ===
[https://trello-attachments.s3.amazonaws.com/5deba567f350423ace9e52ec/5df3f6560cc1cb6840af0df8/4dc240514a122340e931fc1c74e73c0c/incepatori_varena.html Începători Varena]

= Lecție =

== Element Majoritar ==

Cei avansați au avut ca temă problema [https://infoarena.ro/problema/livada Livada], problemă în care era necesară găsirea elementului majoritar dintr-un șir de numere. Elementul majoritar dintr-un șir de <tt>N</tt> numere este acela care apare de cel puțin <tt>[N / 2] + 1</tt> 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: [https://www.infoarena.ro/problema-majoritatii-votului 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.

<syntaxhighlight>
#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);
}
</syntaxhighlight>

== 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

<syntaxhighlight>
#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;
}
</syntaxhighlight>

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

== Exponențiere rapidă ==

Calculați <tt>an</tt> î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ă <tt>n</tt> este par, atunci <tt>an = a2*n/2 = (a2)n/2</tt>
*Dacă <tt>n</tt> este impar, atunci <tt>n-1</tt> este par și avem <tt>an = a * an-1 = a * a2*(n-1)/2 = a * (a2)(n-1)/2 = a * (a2)n/2</tt>

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

<syntaxhighlight>
#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;
}</syntaxhighlight>

== 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 <tt>i1</tt>, <tt>i2</tt> și <tt>i3</tt> care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:

<syntaxhighlight>// 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;</syntaxhighlight>

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 ===

[https://infoarena.ro/problema/elmaj infoarena - elmaj] 
[http://varena.ro/problema/decbin varena - decbin] 
[http://varena.ro/problema/abc1 varena - abc1] 
[http://varena.ro/problema/portofel 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!

[https://infoarena.ro/problema/cifre5 infoarena - cifre5] 
[https://infoarena.ro/problema/cern infoarena - cern] 
[https://infoarena.ro/problema/cmmmc infoarena - cmmmc]

=== Începători ===

[https://infoarena.ro/problema/elmaj infoarena - elmaj] 
[https://infoarena.ro/problema/gsr infoarena - gsr] 
[http://varena.ro/problema/decbin varena - decbin] (greuță) 
[http://varena.ro/problema/puteri2 varena - puteri2] 
[http://varena.ro/problema/impletire varena - impletire] (greuță) 
[http://varena.ro/problema/portofel varena - portofel] (greuță)

Clasa a IX-a lecția 7 - 30 nov 2019

2019-12-07T13:17:22Z

Teodor: /* Începători */

= Lecție =

Din păcate nu am putut ține cercul de această dată, așa că vă las de lucru câteva probleme, aplicații la ce am făcut până acum la cerc.

== Avansați ==

Până data viitoare, lucrați:

[http://varena.ro/problema/roata Roata] 
[http://varena.ro/problema/clepsidru Clepsidru] 
[https://codeforces.com/problemset/problem/1248/B Grow The Tree] 
[https://codeforces.com/problemset/problem/1257/C Dominated Subarray] 
[https://codeforces.com/problemset/problem/1257/D Yet Another Monster Killing Problem] (bonus)

La următorul cerc (7 decembrie) vom trece mai departe cu materia.

== Începători ==

Temele de data trecută, pentru familiarizarea cu vectorii!

Citit: [http://algopedia.ro/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_2_-_19_oct_2019 Lecția 2] 
Implementat: [http://varena.ro/problema/numere1 Numere1]

Citit: [http://algopedia.ro/wiki/index.php/Clasa_a_IX-a_lec%C8%9Bia_3_-_26_oct_2019 Lecția 3] 
Implementat: [http://varena.ro/problema/prime Prime]

Clasa a IX-a lecția 6 - 23 nov 2019

2019-11-23T10:36:42Z

Teodor: /* Temă începători */

= Concurs =

Am creat două concursuri:

* [http://varena.ro/runda/concurs_9_incepatori Concurs începători]
* [http://varena.ro/runda/concurs_9_avansati Concurs avansați]

== Concurs începători ==

Recomand ca înainte de începerea concursului să urmăriți acest [http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_12_-_28_oct_2014#Citirea_unei_secven.C8.9Be ghid], care vă exemplifică lucrul cu secvențe.

= Temă =

Vă rămân ca temă problemele pe care nu le-ați terminat în timpul concursului. Pe lângă acestea:

== Temă începători ==

Citiți lecția cu [http://algopedia.ro/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_21_-_13_ian_2015#Declararea_vectorilor vectori] și familiarizați-vă cu ei. Lucrați problemele:

[http://varena.ro/problema/cfdist cfdist] 
[http://varena.ro/problema/minnr minnr] 
[http://varena.ro/problema/culori culori] 
[http://varena.ro/problema/compus compus]

== Temă avansați ==

[http://varena.ro/problema/lanterna Lanternă]

Clasa a IX-a lecția 5 - 9 nov 2019

2019-11-08T20:46:47Z

Teodor: /* Probleme */

= Lecție =

== Cuvânt înainte ==

Am observat mai multe cazuri de elevi care nu își fac temele. Dacă nu vă faceți temele și nu lucrați, nu veți progresa la acest cerc. Profitați de faptul că aveți în fața voastră un om cu puțin mai multă experiență decât voi în programare care este disponibil să vă ajute să vă dezvoltați în acest domeniu. Nu vă ies problemele? Aveți nevoie de ajutor? Aveți adresa mea de Slack, scrieți-mi, profitați de mine și de disponibilitatea mea.

Cei care au teme restante, vreau să le văd făcute până data viitoare. Din nou: Nu vă ies? Nici o problemă, sunteți aici să învățați lucrând și greșind iar eu sunt aici să vă ajut.

== Descărcare teste ==

Această secțiune este în principal pentru cei începători. Să zicem că nu luați 100 puncte pe o problemă și deși ați încercat să vă dați multe teste, nu reușiți să vă dați seama ce este greșit. Pe lângă varianta de a îmi scrie și de a îmi cere ajutorul, sunt câteva probleme la care aveți acces direct la teste. Vedeți pe ce test vă dă rezultat greșit, luați fișierele <tt>.in</tt> și <tt>.ok</tt> de la acel test și comparați rezultatul cu al vostru.

'''Important''' 
Este important să nu abuzați de asta. Învățați să vă dați teste singuri, este o abilitate importantă pe care trebuie să o dezvoltați!

== Problemă încălzire ==
Se dau două numere <tt>N</tt> și <tt>K</tt>. Să se afișeze exponentul lui <tt>K</tt> din descompunerea în factori primi ai lui <tt>N!</tt>.

'''Soluție''' 
Avem:
* <tt>N! = 1 * 2 * 3 * ... * K * (K + 1) * ... * (2 * K) * ... * N</tt>

Din produsul de mai sus, singurele numere care influențează exponentul lui <tt>K</tt> sunt multiplii de <tt>K</tt>. Mai mult de atât:
* Fiecare multiplu de <tt>K</tt> influențează exponentul cu <tt>1</tt>. În total avem <tt>N / K</tt> multiplii de <tt>K</tt>.
* Fiecare multiplu de <tt>K2</tt> influențează exponentul cu încă <tt>1</tt> factor față de multiplii de <tt>K</tt>. În total avem <tt>N / K2</tt> multiplii de <tt>K2</tt>.
* ...

Deci, rezultatul problemei este:
* <tt>N / K + N / K2 + N / K3 + ...</tt>

O metodă simplă și elegantă de a scrie acest lucru:

<syntaxhighlight>
...
exponent = 0;
while (n >= k) {
exponent += n / k;
n /= k;
}

printf("%d\n", exponent);
</syntaxhighlight>

La temă veți avea o problemă care se folosește de această tehnică.

== Vectori caracteristici ==

Vectorii caracteristici sunt folosiți pentru a marca dacă un număr apare sau nu într-o anumită entitate (secvență de numere, mulțime, etc.) sau dacă un număr are sau nu o anumită proprietate (dacă este prim, de exemplu). După cum le spune și numele, ei sunt folosiți pentru a reține dacă un număr are sau nu o anumită caracteristică. Am folosit o variantă a vectorilor caracteristici la implementarea ciurului lui Eratostene. Astăzi îi vom aplica în mai multe probleme.

De exemplu, dacă am un șir de numere: <tt>2, 7, 5, 1, 2, 6, 7</tt> și vreau să știu care din numerele de la <tt>1</tt> la <tt>10</tt> se găsesc în această mulțime, pot construi un vector caracteristic care va arăta așa: 
<tt>| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |</tt> 
<tt>| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |</tt>

== Vectori de frecvență ==

Vectorii de frecvență sunt folosiți pentru a marca numărul de apariții ale unui număr într-o anumită entitate. Vectorul de frecvență pentru exemplul anterior ar arăta astfel: 
<tt>| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |</tt> 
<tt>| 0 | 1 | '''2''' | 0 | 0 | 1 | 1 | '''2''' | 0 | 0 | 0 |</tt>

Se observă că <tt>2</tt> și <tt>7</tt> apar de două ori.

== Sortare vector ==

Vectorii pot fi sortați prin mai multe modalități, de multe dintre acestea ați auzit și voi și din câte am înțeles, pe unele știți să le implementați deja. O să încep prin a prezenta o sortare în complexitate <tt>O(N2)</tt>.

=== Sortare prin selecție ===

Acest algoritm de sortare se bazează pe faptul că la fiecare pas vom selecta minimul / maximul din vector și îl vom pune în poziția corespunzătoare: primul / ultimul element din șir.

<syntaxhighlight>// 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;
}</syntaxhighlight>

Complexitatea algoritmului este <tt>O(N2)</tt>. Diferența dintre acest algoritm și cel mai "popular" algoritm de sortare în aceeași complexitate (bubble-sort) este constanta cu care se înmulțeste numărul de pași în practică. Chiar dacă în teorie au aceeași complexitate, algoritmul de sortare prin selecție performează mai bine în practică.

=== Sortare în complexitate <tt>O(N*logN)</tt> ===

Vom vorbi despre algoritmii de sortare Merge Sort și Quick Sort mai târziu în acest curs.

=== Sortare prin vectori de frecvență ===

Vectorii de frecvență sunt minunați când trebuie să sortăm un vector cu multe elemente ale cărui elemente se află într-un interval de lungime mică. De exemplu, dacă elementele vectorului pot lua valori din intervalul <tt>[1, 100], [1, 1000], [9000, 10000], etc.</tt> Evident, trebuie să ținem cont și de dimensiunea vectorului.

Complexitatea de timp a algoritmului este <tt>O(N + V)</tt>, unde <tt>N</tt> este numărul de elemente din vector iar <tt>V</tt> este lungimea intervalului din care elementele fac parte. Spre deosebire de sortarea prin selecție, acest algoritm are și o complexitate adițională de memorie egală cu <tt>O(V)</tt>.

Este indicat să folosim acest algoritm când avem suficientă memorie la dispoziție și când <tt>N + V < N2</tt> (respectiv <tt>N + V < N * logN</tt>, în cazul în care folosim un algoritm de complexitate optimă). Un exemplu de implementare:

Se dă un vector <tt>V</tt> cu <tt>N</tt> elemente. Se știe că elementele vectorului sunt din intervalul <tt>[0, 100]</tt>, iar <tt>1 <= N <= 1000000</tt>. Să se afișeze elementele vectorului în ordine crescătoare.

<syntaxhighlight>
#include <stdio.h>

int v[1000000], freq[101];

int main() {
int n, i, j;
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &v[i]);
++freq[v[i]]; // contorizez o aparitie a lui v[i]
}

for (i = 0; i <= 100; ++i) // parcurg tot intervalul
for (j = 0; j < freq[i]; ++j) // afisez numarul din interval de cate ori apare
printf("%d ", i);

return 0;
}
</syntaxhighlight>

=== Sortare STL ===

În C++, există o librărie de algoritmi care are câțiva algoritmi generici gata implementați. Aceasta se numește <code><algorithm></code> și conține o funcție de sortare în complexitate optimă <tt>O(N logN)</tt>, care se folosește astfel:

<syntaxhighlight>
#include <stdio.h>
#include <algorithm> // includem libraria algorithm

// trebuie inclus pentru a recunoaste functiile din librarie
// mai multe despre namespace la un search pe google
using namespace std;

int v[1000000];

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

// sortez vectorul incepand cu pozitia 0 inclusiv, pana la pozitia n exclusiv.
sort(v, v + n); // sau: sort(v + 0, v + n);

for (i = 0; i < n; ++i)
printf("%d ", v[i]);

return 0;
}
</syntaxhighlight>

==== Important ====

Acesta este un algoritm eficient și vă recomand să îl folosiți la olimpiadă de oricâte ori aveți nevoie de o sortare în complexitate <tt>O(N logN)</tt>. '''De reținut că sunt totuși cazuri în care algoritmul de sortare prin vectori de frecvență este mai eficient!'''

Pe lângă olimpiadă am pretenția de la voi să știți să și implementați algoritmii de sortare predați aici, nu doar să îi folosiți pe cei gata implementați. Sunteți aici să învățați programare de-a binelea, nu doar să învățați să folosiți câteva funcții care vă sunt puse la dispoziție de limbaj.

== Probleme ==
http://varena.ro/problema/subsecventa
http://varena.ro/problema/nrtri
http://varena.ro/problema/cool
http://varena.ro/problema/cooler
https://infoarena.ro/problema/livada
http://varena.ro/problema/ploaie

= Temă =
[http://varena.ro/problema/factk Factk]

Clasa a IX-a lecția 1 - 19 oct 2019

2019-10-12T16:03:46Z

Teodor: Created page with "=== Problemă fun / interviu #2 === Aveți dreptul la următoarele operații: * Declarare variabilă (e.g. <code>int a;</code>) * Decrementare variabilă (e.g. <code>--a;</cod..."

=== Problemă fun / interviu #2 ===
Aveți dreptul la următoarele operații:
* Declarare variabilă (e.g. <code>int a;</code>)
* Decrementare variabilă (e.g. <code>--a;</code>)
* Cât timp expresie (e.g. <code>while (--a)</code>)

Să se implementeze <code>a = b</code>.

'''Soluție''' Așa cum v-am promis, soluția problemei:
<syntaxhighlight>
int a, b, c;
while (--c); // c = 0;
while (--b) --c; // c = -b;
while (--a); // a = 0;
while (--c) --a; // a = -c = -(-b) = b;
</syntaxhighlight>

File:Laturi-triunghi-2.gif

2019-10-06T12:25:32Z

Teodor: Teodor uploaded a new version of File:Laturi-triunghi-2.gif

Clasa a IX-a lectia 1 - 12 oct 2019

2019-10-06T12:16:12Z

Teodor: /* Laturile unui triunghi */

= Introducere =
== Prezentarea instructorului ==
Numele meu este Teodor Plop și voi susține acest curs de informatică. Sunt un fost elev al liceului Tudor Vianu, sunt pasionat de programare, grafică și jocuri pe calculator iar de mai bine de 5 ani de zile lucrez ca programator în industria jocurilor din România.

== Prezentarea cercului ==
Cercul are ca scop dezvoltarea gândirii algoritmice și logice, punerea bazelor informaticii și aprofundarea ei la cel mai înalt nivel, incluzând evident și materia de olimpiadă. Pentru a da o șansă și celor care nu au avut tangență cu informatica pânâ în această clasă, voi incepe informatica de la zero, având câteva lecții de introducere. Țin să îi asigur pe cei care au deja experiență în ale informaticii că au ce învăța de la acest curs și că dificultatea acestuia le va atinge așteptările.

=== Structura cercului ===
Vom avea ~3 lecții de introducere în algoritmică, în care vom rezolva probleme folosind scheme logice. Apoi, vom susține un test de selecție în urma căruia se va forma grupa alături de care vom continua cercul, care va conține în mod ideal maxim 15 elevi. Nivelul de performanță al cercului este unul înalt și este imposibil să atingem acest nivel având un număr mare de studenți.
Dupa testul de selectie vom intra in limbajul C si in materia propriu-zisa.

=== Reguli ===
Cercul este opțional. Eu vă promit că am sa dedic timp și efort în pregătirea voastră. Deci, mă aștept să văd implicare și efort și din partea voastră. Veniți la acest cerc doar dacă vreți să învățați ceva în plus, ceva nou, ceva ce vă place suficient de mult încât sa fiți serioși și dedicați. Nu vă ține nimeni cu forța aici și singurul lucru pe care îl obtineți dacă veniți contra voinței proprii este timp pierdut.

Acestea fiind spuse, regulile cercului:
* Prezența
** Prezența este obligatorie
* Seriozitate, implicare & dorința de a învăța
** Tratați cercul cu seriozitate
** Aveți o atitudine pozitivă (Pot și '''vreau''' să fac asta!)
** Temele sunt obligatorii

=== Grup de discuții ===
Am creat un grup de Slack la care înscrierea este obligatorie pentru cei care vin la cercul de informatică, și opțională pentru ceilalți. Vom folosi grupul în două scopuri:
* Pentru a face anunțuri oficiale.
* Pentru a vă corecta temele și a vă oferi sfaturi individual.
Veți primi invitații pe adresele voastre de mail.

= Lecție =
== Algoritmi ==
=== Definiție ===
Algoritm = set de instrucțiuni sau reguli care, pornind cu un set de date inițiale, rezolvă o clasă de probleme folosind operații precise, executate mecanic, fără intervenția creativă a omului.

=== Exemple ===
Rețete de bucate, instrucțiuni asamblare IKEA, ...

=== Proprietăți ===
# '''Precizie''' - Sau neambiguitate. Fiecare pas trebuie să fie neambiguu și executabil fără intervenție creativă.
# '''Generalitate''' - Să rezolve o clasă de probleme, nu doar o problemă în particular.
# '''Finitudine''' - Algoritmul trebuie să se termine în timp finit. Din punct de vedere practic trebuie să se termine într-un timp rezonabil.
# '''Corectitudine''' - Rezultatul final trebuie să fie corect pentru toate datele de intrare.

== Scheme logice ==
Schemele logice sunt un mod de descriere a algoritmilor (un alt mod este pseudocodul). Ele conțin următoarele blocuri:

<gallery widths=76px>
File:flow-assign.gif|'''Bloc de calcul'''
File:flow-io.gif|'''Bloc de citire sau scriere'''
File:flow-decision.gif|'''Bloc de decizie'''
File:flow-terminator.gif|'''Bloc terminator'''
</gallery>

=== Bloc terminator ===
Singurul rol al acestui bloc este de a marca începutul și sfârșitul algoritmului. Iată cele două blocuri pe care le vom folosi:

* [[Image:Flow-terminator-example-01.gif]] este locul unde începe schema logică.
* [[Image:Flow-terminator-example-02.gif]] este locul unde se termină schema logică.

=== Bloc de citire/scriere ===
Aceste blocuri controlează fluxul de date către și dinspre algoritmul nostru.
* '''Citire''' = furnizăm algoritmului setul de date inițial de care are nevoie pentru a rezolva problema.
* '''Scriere''' = algoritmul ne întoarce rezultatele.

Exemple:
* [[Image:sl-citire-x.gif]] citește o valoare și o depozitează în <code>x</code>. 'C' vine de la 'citește'.
* [[Image:sl-citire-x-y.gif]] citește două valori, una ce va fi depozitată în <code>x</code> iar a doua în <code>y</code>.
* [[Image:sl-scriere-y.gif]] scrie valoarea stocată în <code>y</code>. 'S' vine de la 'scrie'.

=== Bloc de calcul ===
Așa cum sugerează și numele, aceste blocuri sunt folosite pentru a calcula expresii. De obicei conțin calcule matematice. Exemple:

* [[Image:Flow-assign-example.gif]] calculează expresia <code>2 + 3</code> și stochează rezultatul (în acest caz <code>5</code>) în <code>x</code>.
* [[Image:Flow-assign-example-02.gif]] ia vechea valoare a lui x <code>x</code>, îi adună <code>1</code> și stochează rezultatul în variabila <code>x</code>, suprascriind vechea valoare. Dacă <code>x</code> era <code>5</code> inițial, valoarea finală va fi <code>6</code>, după execuția acestui bloc.

=== Bloc de decizie ===
Un bloc de decizie este folosit în momentul în care vrem să acționăm diferit în funcție de o anumită expresie. Dacă expresia este adevărată execuția algoritmului continuă pe ramura din dreapta. Dacă expresia este falsă execuția continuă cu ramura din stînga.
Putem considera că acest bloc "pune o întrebare". Dacă răspunsul întrebării este pozitiv, algoritmul se continuă cu ramura din dreapta. Dacă răspunsul este negativ, cu ramura din stânga.

* [[Image:sl-test-x-10.gif]] testează dacă <code>x</code> este mai mic ca zece, atunci cînd se ajunge în acest punct al algoritmului. Dacă <code>x</code> este mai mic ca zece continuăm cu blocurile de pe ramura dreaptă. Dacă <code>x</code> este mai mare ca zece, sau egal cu zece, continuăm cu ramura din stînga.
* [[Image:Flow-decision-example-02.gif]] testează dacă valoarea lui <code>x</code> este mai mare sau egală cu valoarea lui <code>y</code> plus <code>3</code>. În acest caz continuăm pe ramura din dreapta. Dacă nu, continuăm pe ramura din stânga.

=== Exemplu: distanța până la Stormwind ===
Orașul Stormwind se află pe autostrada A1 la kilometrul 60. Se știe că noi ne aflăm pe autostradă la kilometrul k (k citit). La ce distanță de Stormwind ne aflăm? Să construim o schemă logică care o calculează (vezi figura de mai jos).

Pentru a executa o schemă logică pornim de la blocul de '''START''' si urmăm săgețile. Primul pas este să citim <code>k</code>, kilometrul la care ne aflăm pe autostradă. Apoi vom testa dacă am depășit Stormwind, adică dacă am trecut de kilometrul 60. Dacă <code>k</code> este mai mare decît 60 o vom lua pe ramura din dreapta, numită și ramura <code>DA</code>, unde vom calcula distanța <code>d</code> ca fiind valoarea <code>k - 60</code>. Dacă <code>k</code> este mai mic sau egal cu 60 vom urma ramura din stînga (ramura <code>NU</code>) unde vom calcula distanța ca fiind <code>60 - k</code>. Indiferent ce ramură am urmat vom ajunge în final la conectorul cerculeț. În acest moment <code>d</code> conține valoarea corectă a distanței. Tot ce mai avem de făcut este să o afișăm, după care ne oprim la blocul '''STOP'''.

[[Image:stormwind.gif|frame|none|Distanța până la Stormwind]]

== Programarea structurată ==
Programarea structurată este un mod de a scrie scheme logice care îmbunătățește claritatea, citibilitatea, calitatea și ușurința modificării ulterioare. Denumirea vine de la ''Programarea cu structuri''. Mai exact, programarea structurată ne limitează modul în care putem folosi și îmbina blocurile. Ele pot fi aranjate în trei feluri distincte, conform unor modele numite structuri. În continuare vom studia două dintre aceste structuri.
=== Structura liniară ===
Se mai numește și structură de calcul. Ea constă dintr-o înșiruire de blocuri de calcul și blocuri de citire/scriere.
[[Image:sl-structura-liniara.gif|frame|none|Structura liniară]]

=== Structura alternativă ===
Structura alternativă este compusă dintr-un bloc de decizie, două ramuri de execuție, ''DA'' și ''NU'', care se reunesc la final.
[[Image:sl-structura-alternativa.gif|frame|none|Structura alternativă]]

== Operatori ==
Vom enumera principalii operatori pe care îi vom folosi în scheme logice.

=== Operatori aritmetici ===
Operatorii aritmetici pe care îi putem folosi în blocurile de calcul sunt:
{| class="wikitable"
!Operator
!Semnificație
!Exemplu
|-
| <tt>+</tt>
| Adunarea a două numere
| <tt>x ← a + b</tt>
|-
| <tt>-</tt>
| Scăderea a două numere
| <tt>y ← y - 10</tt>
|-
| <tt>*</tt>
| Înmulțirea a două numere
| <tt>x ← a * 10</tt>
|-
| <tt>/</tt>
| Împărțirea întreagă a două numere (cîtul împărțirii)
| <tt>x ← 14 / 3</tt> (<tt>x</tt> primește valoarea 4)
|-
| <tt>%</tt>
| Împărțirea întreagă a două numere (restul împărțirii)
| <tt>x ← 14 % 3</tt> (<tt>x</tt> primește valoarea 2)
|-
| <tt>( )</tt>
| Paranteze: schimbul ordinii operațiilor
| <tt>x ← 2 * (10 - (3 + 4))</tt> (<tt>x</tt> primește valoarea 6)
|-
| <tt> __ √</tt>
| Radical: partea întreagă a operațiunii radical
| <tt>     __ x ← √10</tt> (<tt>x</tt> primește valoarea 3)
|}
=== Operatori de comparație și logici ===
Operatori de comparație și logici: <tt>= ≠ < ≤ > ≥ și sau</tt>

== Probleme ==

=== Strângeri de mînă ===
Avem <tt>n</tt> oameni care dau mâna fiecare cu fiecare o singură dată. În total sunt <tt>k</tt> strângeri de mână. Să se scrie o schemă logică care citește <tt>k</tt> (numărul de strângeri de mînă), apoi calculează și afișează <tt>n</tt> (numărul de oameni). [[Image:sl-stringeri-de-mina.gif|frame|none|n oameni dau mâna. Sunt k strângeri de mână. Dându-se k să se calculeze n.]]

=== Testul de divizibilitate ===
Testul de divizibilitate <tt>n</tt> cu <tt>k</tt>, discuție cele două metode, prima folosind operatorul <tt>%</tt>, a doua folosind operatorul <tt>/</tt>.

{|
| [[Image:sl-n-div-k-var-1.gif|frame|none|n divizibil cu k, varianta 1]]
| [[Image:sl-n-div-k-var-2.gif|frame|none|n divizibil cu k, varianta 2]]
|}

=== Extragerea ultimei cifre ===
Să se afișeze ultima cifră a unui număr n, folosind operatorul '%', respectiv restul împărțirii la 10. Am demonstrat că restul împărțirii la 10 este ultima cifră a unui număr.
[[Image:sl-ultima-cifra.gif|frame|none|Ultima cifră a lui n]]

=== Extragerea primei cifre ===
Se citește n, un număr natural strict mai mic decît 100. Să se afișeze prima cifră a lui n. [[Image:prima-cifra.gif|frame|none|Prima cifră a lui n, n < 100]]

=== Laturile unui triunghi ===
Se citesc trei numere, a, b și c. Să se spună dacă pot fi laturile unui triunghi.

{|
| [[Image:laturi-triunghi.gif|frame|none|a, b, c pot fi laturile unui triunghi? varianta 1]]
| [[Image:laturi-triunghi-2.gif|frame|right|a, b, c pot fi laturile unui triunghi? varianta 2]]
|}

= Tema =

Scrieți temele pe foi si aduceți-le semnate data viitoare. Vă voi returna tema corectată. Încercați să vă gândiți singuri la răspunsuri, apoi, dacă nu găsiți rezolvarea căutați pe google și abia apoi, dacă nu reușiți, întrebați părinții sau prietenii. Scopul principal al temelor este să învățați să aplicați ce lucrăm la curs, nu să impresionați instructorul sau colegii.

* Se dă un număr n între zero și 999 inclusiv. Să se afișeze cifrele lui în ordine inversă.
* Să se spună dacă un număr n are ultimele două cifre consecutive, în ordine crescătoare. Exemple: 312, 4523 au cifrele ultimele doua cifre consecutive in ordine crescatoare; 215, 4321 și 7 nu au.
* Se dau 3 numere. Să se afișeze maximul dintre ele.
* Ecuația de gradul 1: se dau a și b astfel încât a * x = b. Să se determine x pe baza valorilor a și b. Am discutat cele trei cazuri:
** când a este diferit de zero x este b : a.
** când a este zero și b este diferit de zero x nu există.
** când a este zero și b este zero x poate avea orice valoare.
* Să se spună dacă n copii se pot așeza în formă de pătrat plin. Exemple:
** Nouă copii se pot așeza în formă de pătrat astfel: [[Image:copii-9-in-patrat.gif|frame|none|Nouă copii așezați în formă de pătrat]]
** 14 copii nu se pot așeza în formă de pătrat: [[Image:copii-14-in-patrat.gif|frame|none|14 copii]]