Clasa a VI-a lecția 1 - 20 sep 2018

From Algopedia
Jump to: navigation, search

Anunțuri

Bun venit la IQ Academy,în noul an școlar.

  • Avem elevi noi. Suntem mai mulți. Trebuie să fiți mai liniștiți.
  • Listă de prezență, pentru a ști la care din grupe vin elevii noi (reminder to self).
  • Toată lumea trebuie să fie inscrisă pe clubul curioșilor. Aveți instrucțiuni de înscriere aici: Instrucțiuni înscriere Clubul curioșilor. Recomand ca măcar unul din părinți sau alt adult să fie inscris pe această listă.
  • Toată lumea, dar mai ales noii veniți, trebuie să citească și să își insușească capitolul reguli ale cercului de informatică. Citiți cu atenție mai ales ultima parte, reguli de programare în limbajul C
  • Alte părți importante din reguli: prezența este foarte importantă, nu chiuliți și anunțați-mă cînd apare o problemă și nu puteți veni. De asemenea temele sunt obligatorii, nu neapărat să luați 100p, dar să vă gîndiți la ele și să incercați să le rezolvați. Atenție, absențele și temele neîncercate sunt motive pentru retragerea selecției la IQ Academy.
  • Temele trebuie făcute de voi și numai de voi. Precum unii din voi știu deja am un al șaselea simț care îmi spune cînd veniți cu teme la care ați fost ajutați. Nu mi-l puneți la încercare :-)

Lecție

Complexitatea algoritmilor

Ne dorim să comparăm doi algoritmi: care este mai eficient? Pentru aceasta am putea să implementăm ambii algoritmi în C și să comparăm timpii de execuție ai celor două programe. Însă aici încep să apară probleme:

  • Implementările pot să difere, în funcție de programator
  • Calculatoarele pe care se execută programele pot să difere
  • Pe ce date de intrare să facem comparațiile?

Problema pare destul de complicată. De aceea informaticienii au inventat această notație numită O mare și notată O(). Ea are următoarea idee:

Idee: Vom estima numărul de pași elementari ai algoritmului atunci cînd datele de la intrare sînt foarte mari.

Numărul de pași elementari ai acelui algoritm nu depinde de eficiența implementării lui și nici de calculatorul pe care va fi executat. Nu ne preocupă comportamentul unui algoritm atunci cînd datele de intrare sînt mici, cînd probabil și timpul de execuție va fi mic, de aceea estimăm numărul de pași pentru date de intrare mari, acolo unde putem compara cu adevărat doi algoritmi.

Exemplul 1

Cifra k Rezolvare
Calculați cifra k a unui număr n,
numărînd cifrele de la dreapta la stînga.
while ( k > 1 ) {
  n = n / 10;
  k--;
}
cf = n % 10;

Complexitate: numărul de pași elementari
este proporțional cu numărul de cifre
parcurse, k, deci complexitatea este O(k)

Exemplul 2

Afișați descompunerea în factori primi a numărului n. Exemplu: 1176 = 23 x 31 x 72.

Ideea rezolvării constă în existenţa unui singur factor prim mai mare decât radicalul numărului. O implementare posibilă:

#include <stdio.h>

int main() {
  int n, div, exp;

  scanf("%d", &n);
  div = 2; //Incepem cautarea factorilor primi de la primul numar prim
  while ( div * div <= n ) { //Cautam factorii primi pana la radicalul lui n
    exp = 0;
    while ( n % div == 0 ) {
      n /= div;
      exp++;
    }
    if (exp > 0)
      printf("%d^%d\n", div, exp);
    div++;
  }
  // daca n mai contine un factor, el este un numar prim la puterea unu
  if ( n > 1 )
    printf( "%d^1\n", n );

  return 0;
}

Complexitate: bucla exterioară se poate executa de maxim {\sqrt  {n}} ori. Este drept că în interior mai avem o buclă, dar dacă ea se execută de mai multe ori numărul de operații total scade, nu crește. încercați să vă dați seama de ce. Drept care cel mai defavorabil caz este cel în care numărul n este prim, iar bucla interioară nu se execută niciodată. În acest caz numărul de pași elementari este proporțional cu {\sqrt  {n}}, deci complexitatea va fi O({\sqrt  {n}}).

Alte exemple de număr de pași și complexitățile lor

Deoarece ne interesează proporționalitatea numărului de pași cu datele de intrare, notația O() ignoră constantele multiplicative și aditive. Să vedem niște exemple:

  • 1 pas = complexitate O(1)
  • 25 de pași = complexitate O(1), deoarece putem ignora constanta 25
  • n pași = complexitate O(n), deoarece putem ignora constanta 3
  • n+8 pași = complexitate O(n), deoarece putem ignora constantele 3 și 8

Exemple de complexități pentru algoritmi cunoscuți

Să estimăm complexitațile cîtorva algoritmi cunoscuți:

  • Adunarea a două numere: O(1)
  • Împărțirea a două numere: O(1)
  • Calculul sumei lui Gauss pînă la n: O(1)
  • Calculul sumei lui Gauss pînă la n prin forță brută: O(n)
  • Ridicare la putere ab: O(b)
  • Sortare prin selecție a n numere: O(n2)

Comparația algoritmilor

Care algoritm este mai bun, unul de complexitate O(n) sau unul de complexitate O({\sqrt  {n}})? Pentru orice valori ale lui n știm că {\sqrt  {n}} ≤ n. Algoritmul de complexitate O({\sqrt  {n}}) se va executa mai rapid, chiar dacă pașii lui elementari durează mai mult. De ce? Deoarece atunci cînd n crește, n pași rapizi vor dura mai mult decît O({\sqrt  {n}}) pași lenți. Matematic spunem că există un n dincolo de care c1·{\sqrt  {n}} < c2·n, oricum am alege c1 și c2.

Vom compara în mod similar oricare alți algoritmi. Vom vedea mai multe pe măsură ce vom discuta despre algoritmi.

Considerente practice

Din nefericire la concursuri de programare nu este suficient sa estimăm complexitatea unui algoritm. Știm foarte bine că acolo ni se cere încadrarea într-un anumit timp de execuție. Cum procedăm în acest caz?

Un calculator are un procesor de o anume frecvență, de obicei în jurul a 1-2 GHz. Ce înseamnă acest lucru? 1GHz = de un miliard de ori pe secundă, deci el poate executa circa unul sau două miliarde de operații elementare într-o secundă. Trebuie să avem grijă, deoarece operațiile elementare ale unui algoritm se traduc, de obicei, în mai multe operații elementare ale unui calculator. De aceea trebuie să luăm un număr conservator de operații pe secundă pe care le poate executa un calculator. În general vom considera că ne putem baza pe cîteva sute de milioane de operații pe secundă, cu anumite excepții, de care vom vorbi mai jos.

Cum estimăm dacă un algoritm se va încadra în timp?

  1. Estimăm complexitatea algoritmului. Să presupunem că ea este O(n2).
  2. Înlocuim valorile de intrare cu cele maxime. Să presupunem că n < 10000, vom avea deci valoarea n2 = 100 milioane.
  3. Comparăm cu timpul de execuție al problemei. Să presupunem că el este o secundă. În acest caz algoritmul nostru se va încadra în timp, deoarece calculatorul poate executa cîteva sute de milioane de operații. Dacă însă timpul este de 0.1s, riscăm să depășim timpul, deoarece nu ne putem baza decît pe cîteva zeci de milioane de operații în timpul alocat.

Sunt toate operațiile C aproximativ egale ca timp de execuție? Precum bănuiți, nu. De exemplu calculatorul poate sa calculeze sute de milioane de adunări pe secundă, dar doar zeci de milioane de împărțiri. Acest lucru ne complică estimarea timpului de execuție. Iată lista operațiilor "scumpe. Le vom exprima în echivalentul numărului de adunări.

  • + - *: o adunare
  • / % (împărțire și modulo): circa 30 de adunări
  • împărțiri la 2 și modulo 2: o adunare (excepție de la regula împărțirilor oarecare)
  • sqrt() (radical): sute de adunări
  • ridicare la putere (pow), logaritm: sute de adunări

Concluzii:

  • Este bine să evităm împărțirile nenecesare, în număr mare
  • Atunci cînd avem multe împărțiri numărul de operații pe secundă trebuie împărțit la 30, iar în cazul radicalului la 500, poate chiar 1000.

Recapitulare cunoștințe informatică

Rezolvați următoarele exerciții. Pentru fiecare exercițiu rezolvat calculați complexitatea timpului de execuție.

Secvență monotonă

Spuneți dacă o secvență de numere este monotonă. O secvență este monotonă dacă numerele ei sînt fie în ordine crescătoare fie în ordine descrescătoare. Nu aveți voie să folosiți vectori.

#include <stdio.h>

int main() {
  int n, a, b, i, cresc, monoton;
  scanf( "%d%d%d", &n, &a, &b ); // n si primele doua numere
  i = 2;
  // Ignoram toate elemente egale de la inceput, pt a stabili monotonia sirului
  while (i < n && a == b) {
    scanf("%d", &b);
    i++;
  }
  // Daca sirul este crescator, monoton = 1; Altfel, monoton = -1.
  cresc = monoton = (a < b) ? 1 : -1;
  // Cat timp nu am terminat si este pastrata monotonia initiala
  while (i < n && monoton == cresc) {
      a = b;
      scanf("%d", &b);
      if (a < b)
        cresc = 1;
      else if (a > b)
        cresc = -1;
      i++;
  }
  if (monoton == cresc)
    printf("DA");
  else
    printf("NU");

  return 0;
}

Ce complexitate are această soluție? Deoarece bucla while se poate executa de maxim n ori complexitatea acestei soluții este liniară, egală cu numărul de elemente ale secvenţei: O(n).

Paranteze

Dată o secvență de 0 și 1, unde 0 înseamnă paranteză deschisă '(', iar 1 înseamnă paranteză închisă ')', spuneți dacă secvența reprezintă o expresie corectă de paranteze și dacă da calculați numărul maxim de paranteze una într-alta. Exemplu: 0 1 0 0 1 0 1 1 este corectă și are factorul de imbricare de 2, pe cînd secvența 0 0 0 1 1 1 0 este incorectă. Nu aveți voie să folosiți vectori.

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 închise

Dacă ambele condiții se îndeplinesc expresia e corectă. Prima condiție trebuie îndeplinită pentru fiecare poziție de rupere.

Pentru a rezolva problema vom folosi un contor de paranteze deschise care nu au fost închise. Cînd la intrare avem o paranteză deschisă adunăm unu la acel contor, cînd avem o paranteză închisă scădem unu. Pentru ca expresia să fie corectă trebuie ca contorul să nu scadă sub zero, iar la final el sa fie exact zero.

#include <stdio.h>

int main() {
  int n, a, i, nrdesc, max;

  scanf("%d", &n);
  max = nrdesc = i = 0;
  while ( i < n && nrdesc >= 0 ) {
    scanf( "%d", &a );
    if ( a == 0 ) {
      nrdesc++;
      if ( nrdesc > max )
        max = nrdesc;
    } else
      nrdesc--;
    i++;
  }
  if ( nrdesc == 0 )
    printf("Expresie corecta, factor de imbricare %d", max);
  else
    printf("Expresie incorecta");

  return 0;
}

Ce complexitate are acest algoritm? Deoarece bucla while se execută de maxim n ori vom avea complexitatea O(n).

Una din temele pentru acasă este cum generalizăm? Avem paranteze rotunde și acolade, aceeași cerință.

Numere cu două cifre

Spuneți dacă numărul n este format din exact două cifre repetate de oricâte ori. 23223 și 900990 sînt astfel de numere, pe cînd 593 și 44002 nu. Nu aveți voie să folosiți vectori.

Iată o metodă de rezolvare: eliminăm ultima cifra a numărului, c1, iar apoi continuăm să eliminăm ultima cifră cîtă vreme este egală cu c1. Apoi eliminăm iarăși ultima cifră, c2, iar apoi continuăm să eliminăm ultima cifră cîtă vreme este egală cu c1 sau c2. Iată soluția bazată pe această idee:

#include <stdio.h>

int main() {
  int n, c1, c2;

  scanf("%d", &n);
  c1 = n % 10; // retinem ultima cifra din numar in c1
  n = n / 10;  // si o eliminam din n
  // eliminam toate aparitiile lui c1 din coada numarului
  while ( n > 0 && n % 10 == c1 )
    n = n / 10;
  if (n == 0)
    printf("NU"); // Daca numarul nu mai are alte cifre, afisam NU
  else {
    c2 = n % 10; // retinem urmatoarea cifra din numar in c2
    n = n / 10;
    // eliminam toate aparitiile lui c1 si c2 din coada numarului
    while ( n > 0 && (n % 10 == c1 || n % 10 == c2) )
      n = n / 10;

    if ( n == 0 ) // daca numarul a avut exact doua cifre, acum va fi zero
      printf("DA");
    else
      printf("NU");
  }

  return 0;
}

Ce complexitate are acest algoritm? E destul de clar că ea este proporțională cu numărul de cifre ale lui n, adică O(nr. cifre n). Dar care este relația dintre n și numărul lui de cifre? Să denumim numărul de cifre cu k. Atunci știm ca 10k-1n<10k, sau, altfel spus, n este egal, foarte aproximativ, cu 10k.

Definiție: dacă n=ak, spunem că k este O(log n).

Log este inversul puterii și va fi studiat ca operație în clasa a 10a.

Deci, complexitatea algoritmului nostru este O(log n). Ce trebuie să reținem de aici? Că numărul de cifre al unui număr n este O(log n) cînd vorbim de complexitatea algoritmilor.

Putere

Calculați an în mod cît mai eficient (a și n numere naturale). Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic. Ideea din spatele acestei rezolvări este următoarea:

  • Dacă n este par, atunci an = a2*n/2 = (a2)n/2
  • Dacă n este impar, atunci n-1 este par și avem an = a * an-1 = a * a2*(n-1)/2 = a * (a2)(n-1)/2 = a * (a2)n/2

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile cînd n este impar vom acumula valoarea curentă a lui a la produsul calculat.

Iată soluția bazată pe această idee:

#include <stdio.h>

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

  scanf( "%d%d", &a, &n );
  p = 1;
  while ( n > 0 ) {
    if (n % 2 == 1)
      p = p * a;
    a = a * a;
    n = n / 2;
  }
  printf( "%d", p );

  return 0;
}

Ce complexitate are acest algoritm? De cîte ori se va executa bucla while? La fiecare pas al buclei n se împarte la doi. De cîte ori putem împărți un număr n la doi, înainte ca el să devină zero? Să considerăm cel mai mic k astfel încît n≤2k. Este destul de clar că bucla noastră while se va executa de k ori, deci complexitatea algoritmului este O(k). Dar, precum am menționat la exercițiul anterior, dacă avem k astfel încît 2k=n, atunci k=O(log n), deci complexitatea acestei soluţii va fi logaritmică, O(log n). Ce înseamnă acest lucru? Că timpul necesar calculului este proporţional cu un număr k, unde k este exponentul lui 2 astfel încît n≤2k.

Generalități

Să ne aducem aminte următoarele lucruri, căci vom avea nevoie de ele la temă:

  • Declararea vectorilor cu inițializare.
  • Dimensiunile diverselor tipuri: în code::blocks int are 4 octeți, long long are 8 octeți.
  • Numerele maxime stocabile pe int și pe long long (circa 2 miliarde, respectiv circa 10^18)
  • Cîți ani bisecți între anul a și anul b, interval închis [a, b]. Ne folosim de o metodă interesantă, în care calculăm anii bisecți de la zero pînă la a-1, apoi, în mod similar, de la zero pînă la b. Acest lucru este mult mai simplu decît calculul direct. Apoi scădem cele două numere pentru a calcula rezultatul. La temă vi se va cere să calculați numărul de zile între două date. Folosiți aceeași metodă, altfel veți avea mari probleme. Unii dintre voi ați rezolvat deja problema, în mod neelegant, drept care și programul vostru este foarte lung. Un program elegant va avea sub 40 de linii.

Tema

Aveți ca temă două probleme din trecut, pe care mulți dintre voi nu le-au rezolvat de 100p. De asemenea aveți o generalizare a problemei paranteze, a cărei rezolvare este destul de grea. Vă rog să vă gîndiți singuri la ea.

  • Întîi rezolvați elegant subproblema: cîți ani bisecți sînt între anul a și anul b, interval închis [a, b].
  • Apoi tema la vianuarena: Tema 1: să se rezolve următoarele probleme (program C trimis la vianuarena):
  • Opțional: gîndiți-vă cum s-ar rezolva această problemă de la codechef: http://www.codechef.com/BTCD2012/problems/DOORS

Rezolvări aici [1]