Difference between revisions of "Clasa a IX-a lecția 5 - 9 nov 2019"

From Algopedia
Jump to: navigation, search
(Probleme)
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
= Lecție =
 
= 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'''<br>
 +
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 ==
 
== Problemă încălzire ==
[http://varena.ro/problema/factk Factk]
+
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'''<br>
 +
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>K<sup>2</sup></tt> influențează exponentul cu încă <tt>1</tt> factor față de multiplii de <tt>K</tt>. În total avem <tt>N / K<sup>2</sup></tt> multiplii de <tt>K<sup>2</sup></tt>.
 +
* ...
 +
 
 +
Deci, rezultatul problemei este:
 +
* <tt>N / K + N / K<sup>2</sup> + N / K<sup>3</sup> + ...</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:<br>
 +
<tt>| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |</tt><br>
 +
<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:<br>
 +
<tt>| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |</tt><br>
 +
<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(N<sup>2</sup>)</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(N<sup>2</sup>)</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 < N<sup>2</sup></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 ====
  
== Vectori caracteristici / de frecvență ==
+
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!'''
  
== Sortare folosind vectori de frecvență ==
+
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 ==
 
== Probleme ==
 +
http://varena.ro/problema/subsecventa
 
http://varena.ro/problema/nrtri
 
http://varena.ro/problema/nrtri
 
http://varena.ro/problema/cool
 
http://varena.ro/problema/cool
 
http://varena.ro/problema/cooler
 
http://varena.ro/problema/cooler
 
https://infoarena.ro/problema/livada
 
https://infoarena.ro/problema/livada
 +
http://varena.ro/problema/ploaie
 +
 +
= Temă =
 +
[http://varena.ro/problema/factk Factk]

Latest revision as of 20:46, 8 November 2019

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 .in și .ok 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 N și K. Să se afișeze exponentul lui K din descompunerea în factori primi ai lui N!.

Soluție
Avem:

  • N! = 1 * 2 * 3 * ... * K * (K + 1) * ... * (2 * K) * ... * N

Din produsul de mai sus, singurele numere care influențează exponentul lui K sunt multiplii de K. Mai mult de atât:

  • Fiecare multiplu de K influențează exponentul cu 1. În total avem N / K multiplii de K.
  • Fiecare multiplu de K2 influențează exponentul cu încă 1 factor față de multiplii de K. În total avem N / K2 multiplii de K2.
  • ...

Deci, rezultatul problemei este:

  • N / K + N / K2 + N / K3 + ...

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

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

printf("%d\n", exponent);

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: 2, 7, 5, 1, 2, 6, 7 și vreau să știu care din numerele de la 1 la 10 se găsesc în această mulțime, pot construi un vector caracteristic care va arăta așa:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |

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:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 1 | 2 | 0 | 0 | 1 | 1 | 2 | 0 | 0 | 0 |

Se observă că 2 și 7 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 O(N2).

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.

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

Complexitatea algoritmului este O(N2). 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 O(N*logN)

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 [1, 100], [1, 1000], [9000, 10000], etc. Evident, trebuie să ținem cont și de dimensiunea vectorului.

Complexitatea de timp a algoritmului este O(N + V), unde N este numărul de elemente din vector iar V 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 O(V).

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

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

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

Sortare STL

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

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

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 O(N logN). 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ă

Factk