Clasa VII/VIII lecția 1 - 23 sep 2014

From Algopedia
Jump to navigationJump to search

Lecție

Complexitatea algoritmilor

Complexitate: ce înseamnă, cîte operații pe secundă execută un calculator, ce operații sînt "scumpe".

Iată un exemplu:

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: proporțional cu numărul de cifre al lui n, adică O(log n)

Alt exemplu: afișați descompunerea în factori primi a numărului n. Exemplu: 1176 = 23 x 31 x 72. Optimizarea descompunerii în factori primi. Complexitățile aferente.

Ideea rezolvării constă în existenţa unui singur factor prim mai mare decât radicalul numărului. O implementare a acestei probleme de complexitate O(sqrt(n)):

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

Recapitulare cunoștințe informatică

Rezolvați următoarele exerciții. Pentru fiecare exercițiu rezolvat calculați complexitatea timpului de execuție (numărul de operații efectuat de algoritm în funcție de datele de intrare).

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 tablouri (vectori sau matrice).

Iată o metodă de rezolvare: eliminăm ultima cifra, c1, a numărului, 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. Complexitatea este O(n). 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;
}

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. 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 2k=n.

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

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 tablouri (vectori sau matrice).

Complexitatea acestei soluții este liniară, egală cu numărul de elemente ale secvenţei: O(n).

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

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 tablouri (vectori sau matrice).

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.

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

Temă de gîndire pentru acasă: cum generalizăm? Avem paranteze rotunde, pătrate și acolade, aceeași cerință.

Interclasare vectori (merge)

Dați doi vectori sortați crescător construiți un al treilea vector sortat care să conțină toate elementele din cei doi vectori. Sînt 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. Nu aveți voie să folosiți funcții de sortare din biblioteca C sau Pascal.

Am mai discutat despre această problemă anul trecut. 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 sînt 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 i1, i2 și i3 care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:

// 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 sigur vid, posibil amindoi
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++;
}
n = n1 + n2;

Ștergere element

Dat un vector v și un element e să se elimine din vector prima apariție a elementului e, în caz că acesta apare în vector. Exemplu: v = 5 9 2 7 9 3 5 7 4 si e = 9, la final v = 5 2 7 9 3 5 7 4

Soluție incorectă

O soluție foarte populară este să căutăm elementul în vector și, în momentul cînd îl găsim să-l ștergem:

for ( i = 0; i < n; i++ )
  if ( v[i] == e ) {
    for ( j = i + 1; j < n; j++ )
      v[j-1] = v[j];
    i = n;
  }

Aceasta este o soluție urîtă deoarece:

  • folosește for pentru un ciclu cu număr necunoscut de pași
  • modifică variabila de ciclu, i
  • nu folosește "cărămizile" învățate deja și anume căutarea unui element în vector și ștergerea unui element din vector

Soluție corectă

Ștergerea unui element din vector se face astfel:

  • Vom avea două etape: căutare element în vector + eliminarea propriu zisă.
  • În final numărul de elemente n se micșorează cu unu.

Iată implementarea corectă:

i = 0;
while ( i < n && v[i] != e )
  i++;
if ( i < n ) {
  n--;
  for ( ; i < n; i++ )
    v[i] = v[i+1];
}

Recapitulare reguli de programare

Găsiți aici capitolul complet de reguli de programare: reguli de programare în limbajul C

Iată ce spune el:

  • Variabilele simple nu se inițializează la declarare. Ele se inițializează cît mai aproape de secțiunea de program care le folosește. Cu alte cuvinte orice variabilă se inițializează cît mai jos posibil. De ce? Pentru citibilitatea codului. Imaginați-vă că la linia 300 vedem o instrucțiune a = a + y;. Ne punem întrebarea cu ce valoare a fost inițializată a. Imaginați-vă că trebuie să mergem cîteva pagini în sus pentru a constata că variabila a fost inițializată la declarare int a = 1;
  • Vectorii încep de la 0, nu de la 1. Este o regulă importantă, nu o preferință personală. Avantaje: cînd folosim modulo, vectori caracteristici, etc.
  • Reguli de indentare, exemple:
    • Indentarea se face la două sau la patru spații. Două sînt suficiente pentru citibilitate. Atenție: setați code::blocks să nu folosească caractere TAB.
    • Acolada deschisă se pune pe același rînd cu instrucțiunea precedentă.
    • Acolada închisă se pune pe rîndul următor aliniată sub instrucțiunea de care aparține.
    • Dacă după else urmează un if atunci if-ul se pune imediat după else pe aceeași linie, iar corpul de instrucțiuni aparținînd lui else se indentează cu două spații, nu cu patru. Astfel, în cazul unor instrucțiuni de genul if ... else if ... else if ... se evită migrarea codului către dreapta prin indentări inutile.
  • Fără break/continue/return/goto în interiorul buclelor. Ele distrug programarea structurată și, implicit, zeci de ani de experiență ai omenirii.
  • Folosim for pentru bucle cu număr cunoscut de pași, while în celelalte cazuri. Aceasta este o regulă de programare ordonată, care face codul mai citibil.
  • Nu avem voie să modificăm variabila de buclă for. Dacă este un ciclu cu număr cunoscut de pași nu avem de ce să modificăm variabila.
  • Cînd eliminăm un element din vector scădem lungimea lui (n--). În felul acesta n continuă să arate numărul de elemente din vector.
  • Nu aveți voie să aveți warnings, vă pot fi fatale: declaraţi int main() si folosiţi return 0 la final. Eliminați orice alte warnings deoarece majoritatea sînt o problemă reală. Unele concursuri compilează sursa cu opriri la warnings (adică tratează warning-urile ca erori). Unele warnings se referă la variabile neinițializate sau la număr diferit de "%d" versus variabile citite, in fscanf, deci sînt importante. Puteți seta Code::Blocks să afișeze toate warnings. Este obligatoriu să faceți acest lucru.
  • Comentați codul cînd e ceva complicat, de exemplu o formulă. Scrieți ideea algoritmului, dacă nu e ceva trivial. Nu trebuie să umpleți de comentarii, dar minimal. Mă ajutați mult în corectarea temei.
  • Denumiți variabilele mai clar. Nu lungi, dar să aibă semnificație: prod, sum, nrcf, etc.
  • Nu abuzați stegulețele. Exemplu unde nu sînt necesare break sau stegulețe: căutarea unui element e în vectorul v:
    i = 0;
    while ( (i < n) && (v[i] != e) )
      i++;
  • Nu folosiți funcții gen sort și qsort. Aveți nevoie de dispensă specială ☺

Constante in C

Constante în C: #define. Atunci cînd o constantă apare des în program este bine să îi dăm un nume cu #define. În felul acesta programul devine mai citibil, iar în cazul unei modificări ulterioare a constantei putem modifica într-un singur loc. Un mod special de a folosi constantele este la debug: cît timp facem corecții la program putem defini o constantă care să "activeze" instrucțiuni de tipărire de debug:

#define D 1
...
if ( D )
  printf( "x=%d   y=%d   a=%d\n", x, y, a )
...

La final, cînd considerăm că programul este corect tot ce avem de făcut este să modificăm constanta D în zero:

#define D 0

Observați folosirea lui 0 și 1 ca valori adevărat, respectiv fals.

Instrucțiunea switch

Precum ştim instrucţiunea if implementează structura alternativă. Uneori avem nevoie de decizii multiple, de exemplu cînd vrem să ştim dacă o variabilă are valoarea 1, 2 sau 3. În aceste cazuri putem folosi o combinaţie de instrucţiuni if:

if ( n == 1 ) {
  cod pentru cazul 1;
} else if ( n == 2 ) {
  cod pentru cazul 2;
} else if ( n == 3 ) {
  cod pentru cazul 3;
}

Deoarece situaţiile cînd vrem să executăm diverse acţiuni în funcţie de valoarea unei variabile limbajul C se oferă instrucţiunea switch a cărei formă este:

switch ( n ) {
case constantă1:
  cod de executat dacă n este egal cu constantă1;
  break;
case constantă2:
  cod de executat dacă n este egal cu constantă2;
  break;
  .
  .
  . 
default:
   cod de executat dacă n nu este egal cu nici una din constante;
}

Exemplu: se citesc pe aceeaşi linie, în ordine, un caracter şi apoi două numere întregi, toate separate printr-un spaţiu. Dacă caracterul este una din operaţiile +, -, * sau / să se afişeze rezultatul acelei operaţii pe cele două numere. În caz contrar să se afişeze cuvîntul eroare.

Rezolvare:

#include <stdio.h>

int main() {
  int a, b;
  char ch;

  ch = fgetc( stdin );
  scanf( "%d%d", &a, &b );
  switch ( ch ) {
  case '+':
    printf( "%d\n", a + b );
    break;
  case '-':
    printf( "%d\n", a - b );
    break;
  case '*':
    printf( "%d\n", a * b );
    break;
  case '/':
    printf( "%d\n", a / b );
    break;
  default:
    printf( "eroare\n" );
  }
  return 0;
}

De menţionat că nu este obligatoriu să avem o variabilă testată în switch, putem avea o expresie, cu condiţia ca ea să aibă o valoare întreagă, nu reală.

Generalități

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

  • Declararea vectorilor cu inițializare.
  • Dimensiunile diverselor tipuri: în code::blocks int are 4 octeți, long long are 8 octeți.
  • Estimarea numărului care încape pe un număr dat de biți folosind formula 210 ≈ 103

Tema

Soluții aici [1]

Doors

There are N doors of a palace, all of which are operated by a set of buttons. One day, Alice, who is just 8 years old, gets access to these buttons. Having recently learnt the multiplication tables, she decides to press buttons in a particular order. First, she presses all the buttons that are multiples of 1. Next, she presses all buttons that are multiples of 2, then 3 and so on until N; after which she leaves.

Each press of button toggles the state of the door, i.e. a door that is open will be closed by the button press and opened if closed initially.

Given that all doors were closed initially, give the number of doors that are open after she leaves.

Input

The input contains several lines. First line contains the number 't', which represents the number of test cases that follow. This is followed by 't' lines of numbers which represent 'N'. 0 < t < 1000000 0 < N < 100000000

Output

For each input, output the number of doors that are open at the end.

Example

Input:

4
4
10
16
27

Output:

2
3
4
5

Time Limit: 3 sec