Clasa a VI-a lecția 2 - 27 sep 2018

From Algopedia
Jump to navigationJump to search

Anunț

Pentru copiii noi:

  • Lecțiile sînt disponibile pe site-ul algopedia.ro
  • Programele se trimit la vianuarena doar în cadrul concursului temă, nu la arhivă. A trimite la arhivă înseamnă a pescui, un mod de a trișa și a cîștiga mai multe puncte. Vreau să văd rapid numărul de trimiteri la o problemă, nu pescuiți vă rog.

Comentarii

  • Unii din voi nu ați rezolvat problema monotonă de 100p, deși aveați rezolvarea în lecția de pe algopedia. Ori sînteți extrem de corecți, ori extrem de neatenți.
  • Unii din voi nu au încercat ultimele două probleme. Primele două erau de anul trecut, ultimele două erau propriu zis tema. Anul acesta mă voi uita cu atenție la seriozitatea cu care tratați temele.
  • Problemele nu sînt facultative. Nici o problemă nu este atît de grea încît să nu luați deloc puncte. Vreau să văd că încercați.

Tema - rezolvări

Rezolvări aici [1]

Lecție - continuare recapitulare

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2018-09-27-clasa-6-lectie-info-02-720p.mp4</html5media>

Interclasare vectori (array merge)

Dați doi vectori ordonați crescător construiți un al treilea vector ordonat crescător cu elementele din primii 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.

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

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.

Pentru a coda această metodă vă sfătuiesc pe cei ce nu ați luat 100p la problema portofel să o refaceți. Interclasarea apare din cînd în cînd la concursuri în diverse forme.

Ștergere element din vector

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 instrucțiunea 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 ) { // dacă am găsit elementul, îl eliminăm
  for ( j = i + 1; j < n; j++ )
    v[j-1] = v[j];
  n--;
}

Întrebare: putem elimina instrucțiunea if ( i < n )?

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.

Exemplu: să se ordoneze n numere cu valori între 0 și 100.

Input Output
8

3 2 9 6 3 2 9 6

2 2 3 3 6 6 9 9

Rezolvare: vom folosi sortarea bazată pe vector de frecvență (counting sort). Construim vectorul de frecvență al numerelor de la intrare, apoi îl parcurgem afișînd pozițiile cu valori nenule de cîte ori arată acea valoare. Ca noutate vom folosi o constantă pentru valoarea maximă a unui element, adică 100. Iată programul:

// ordonare crescatoare a n numere cu valori intre 0 si 100
#include <stdio.h>

#define VAL_MAX 100

int v[VAL_MAX + 1];

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

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

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

  return 0;
}

Avantajul folosirii constantei VAL_MAX este că, dacă ulterior enunțul problemei se schimbă, valoarea maximă devenind 200 sau alt număr, vom modifica doar VAL_MAX, într-un singur loc în program.

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.

Input Output
+ 12 191 203
* 12 11 132
% 20 8 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ă.

Ce complexitate are instrucțiunea switch? Ea este echivalentul a n instrucțiuni if una într-alta, unde n este numărul de cazuri din switch. Pe cazul cel mai rău acele n instrucțiuni if pot testa n-1 condiții, nu-i așa? Deci am fi tentați să spunem că instrucțiunea switch are complexitate O(n), ca și echivalentul său în if. Ei bine, nu este așa. Instrucțiunea switch este compilată de compilator cu tabele de salturi. Ea va selecta ramura corectă în O(1).

Iată un motiv pentru a folosi această instrucțiune ce era mai greu de explicat anul trecut: ea este și mai eficientă algoritmic.

Citire până la final de fișier

Pentru problema numărare aveți nevoie să citiți șirul de la intrare până la final și nu până la \n. Acest lucru se face astfel:

În loc de:

while ( ch != '\n' ) {
    ....
    ch = fgetc( fin );
}

veți scrie:

while ( ch != EOF ) {
    ....
    ch = fgetc( fin );
}

Tema

Tema 2: să se rezolve următoarele probleme (program C trimis la vianuarena): (lista problemelor va fi afișată după ce începe tema)

Rezolvări aici [2]