Clasa a V-a lecția 41 - 17 mai 2018

From Algopedia
Jump to navigationJump to search

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-05-17-lectie-info-41-720p.mp4</html5media>

Operații elementare pe vectori - continuare

Interclasare vectori (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.

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;

O idee similară se folosește și la problema portofel, pe care o aveți ca temă.

Tipuri de date simple - continuare

Precum am discutat într-o lecție anterioară, calculatorul reprezintă toate valorile, fie ele numere sau caractere, ca biţi, sau valori zero şi unu. Tot într-o lecție anterioară am descris cîteva din tipurile simple de date. Vom vorbi acum despre toate tipurile simple de date din limbajul C. Pentru simplitate vom discuta despre un tip concret de calculator, şi anume cel pe care lucrăm zi de zi: procesor pe 32 de biţi, sistem de operare Windows, compilator gcc în mediul de programare CodeBlocks.

Unități de măsură a memoriei calculatorului

Cea mai mică unitate de măsură a memoriei este bitul. Un bit (în engleză la fel, bit) poate avea doar două valori: zero sau unu. Cu toate acestea nu putem avea variabile de tip bit. Biții se grupează cîte opt, formînd un octet (în engleză byte). Octetul este cea mai mică unitate de memorie accesabilă direct: putem avea variabile care ocupă un octet. În mod uzual, cînd vorbim de memorie ocupată în calculator, memoria disponibilă, sau memoria totală a unui calculator, ea va fi măsurată în octeți, sau bytes.

Vom folosi și multiplii octetului, atunci cînd vom măsura cantități foarte mari de memorie. În informatică folosim drept multipli puterile lui doi, nu cele ale lui zece. Deoarece 210=1024 este aproximativ egal cu o mie, vom avea multipli din 1024 în 1024, astfel:

  • 1 kilobyte (1 KB sau kilooctet) este 1024 bytes (octeți)
  • 1 megabyte (1 MB) este 1024 KB = 1 048 576 bytes ≈ 1 milion bytes
  • 1 gigabyte (1 GB) este 1024 MB = 1 073 741 824 bytes ≅ 1 miliard bytes
  • 1 terabyte (1 TB) este 1024 GB = 1 099 511 627 776 bytes ≅ o mie de miliarde de bytes
  • 1 petabyte (1 PB) este 1024 TB = 1 125 899 906 842 624 bytes ≅ un milion de miliarde de bytes
  • 1 exabyte (1 EB) este 1024 PB = 1 152 921 504 606 846 976 bytes ≅ un miliard de miliarde de bytes

Tipul char

Este cel mai mic întreg. El ocupă 8 biţi, adică un byte. Care este intervalul de numere care se pot reprezenta pe 8 cifre binare? El este de la 0 la 28-1, adică 0..255, cu totul 256 de valori. Dar deoarece avem şi numere negative intervalul se translatează cu 128, ceea ce înseamnă că un char este un număr întreg din intervalul -128..127.

În acelaşi timp ştim că el este un tip dual, poate fi văzut atît ca întreg pe 8 biţi cît şi ca caracter. Dacă vrem să îl tipărim vom folosi %d dacă vrem să afişăm valoarea lui întreagă, respectiv %c pentru caracter (dar modul preferat de tipărire este cu fputc).

Tipul unsigned char

Este similar cu tipul char. El ocupă tot 8 biţi, adică un byte. Deoarece el nu are numere negative vom avea numere de la 0 la 28-1, adică 0..255, cu totul 256 de valori. Dacă vrem să îl tipărim vom folosi %u dacă vrem să afişăm valoarea lui întreagă, respectiv %c pentru caracter (dar modul preferat de tipărire este cu fputc).

Tipul short

Este întregul următor ca mărime. El ocupă 16 biţi, sau 2 octeţi. Intervalul de numere ar trebui să fie între 0 şi 216-1, adică 0..65535, dar pentru că avem şi numere negative intervalul devine 32768..32767. Pentru a-l citi sau tipări vom folosi descriptorul %hd.

Tipul unsigned short

Are aceeași mărime ca și tipul short. El ocupă 16 biţi, sau 2 octeţi. Intervalul de numere ar este între 0 şi 216-1, adică 0..65535. Pentru a-l citi sau tipări vom folosi descriptorul %hu.

Tipul int

Este următorul întreg ca mărime. El ocupă 32 de biţi, sau 4 octeţi. Intervalul de numere ar trebui să fie între 0 şi 232-1, adică între 0 şi ceva mai mult de patru miliarde, dar pentru că avem şi numere negative intervalul devine -2 miliarde..2 miliarde. Pentru a-l citi sau tipări vom folosi descriptorul %d.

Tipul unsigned int

Are aceeași mărime ca și tipul int. El ocupă 32 de biţi, sau 4 octeţi. Intervalul de numere este între 0 şi 232-1, adică între 0 şi ceva mai mult de patru miliarde. Pentru a-l citi sau tipări vom folosi descriptorul %u.

Tipurile long și unsigned long

Au aceeaşi mărime ca şi tipul int, drept care nu le folosim. Şi atunci de ce există? Pentru că pe alte arhitecturi poate fi mai mari ca int.

Tipul long long

Este dublu faţă de tipul int. El ocupă 64 de biţi, sau 8 octeţi. Intervalul de numere ar trebui să fie între 0 şi 264-1, dar pentru că avem şi numere negative intervalul devine -263..263-1. Dacă aproximăm 210 cu 103 aceasta înseamnă cu aproximaţie 9 cu 18 zero după el. Pentru a-l citi sau tipări vom folosi descriptorul %lld.

Atenție! Windows nu respectă standardul C! De aceea, dacă folosiți Code::Blocks în Windows va trebui să folosiți %I64d în loc de %lld. Deoarece varena.ro folosește GNU/Linux voi va trebui să schimbați %I64d în %lld, atunci cînd trimiteți un program spre evaluare.

Atenție! La olimpiadă veți lucra în Windows, deci veți folosi %I64d, nefiind nevoie să schimbați nimic în program.

Tipul unsigned long long

Are aceeași mărime ca și tipul long long. El ocupă 64 de biţi, sau 8 octeţi. Intervalul de numere este între 0 şi 264-1. Dacă aproximăm 210 cu 103 aceasta înseamnă cu aproximaţie 18 cu 18 zero după el. Pentru a-l citi sau tipări vom folosi descriptorul %llu.

Atenție! Windows nu respectă standardul C! De aceea, dacă folosiți Code::Blocks în Windows va trebui să folosiți %I64u în loc de %llu. Deoarece varena.ro folosește GNU/Linux voi va trebui să schimbați %I64u în %llu, atunci cînd trimiteți un program spre evaluare.

Atenție! La olimpiadă veți lucra în Windows, deci veți folosi %I64u, nefiind nevoie să schimbați nimic în program.

Tipul float

Este un tip de variabile care memorează o valoare reală. Vine de la floating point, care înseamnă virgulă mobilă, deoarece reprezentarea lui implică mutarea virgulei prin înmulţiri sau împărţiri la doi. Nu-l vom folosi. Vom folosi în loc tipul double, care are precizie mai bună.

Tipul double

Este un tip de variabile care memorează o valoare reală. Pentru a-l citi sau tipări vom folosi %lf. Pentru a afişa un număr real cu 3 cifre întregi şi 5 zecimale îl vom afişa cu %3.5. Nu vom intra în detalii asupra reprezentării, dar trebuie să reţineţi că tipul double are erori. Numerele nu se reprezintă exact decît foarte rar. 0.9 va fi în realitate 0.8999999999999999. De aceea el nu trebuie folosit decît atunci cînd nu se poate altfel. Ceea ce pentru clasele 5-8 înseamnă aproape niciodată.

Depăşire

Ce se întîmplă atunci cînd depăşim valoarea maximă a unui întreg? Vom învăţa pe un exemplu. Ce va afişa programul următor?

char c = 127; // valoarea maxima a unui caracter
c++;
printf( "%d", c )

Răspunsul este -128! Pentru a înţelege de ce vom face următoarea observaţie: valorile unui întreg sînt circulare. Ce înseamnă aceasta? Că după cea mai mare valoare posibilă urmează, în cerc, cea mai mică valoare posibilă. Cu alte cuvinte după 127 urmează -128. Nu voi explica de ce se întîmplă acest lucru, dar voi menţiona că este mulţumită reprezentării numerelor întregi în calculator în complement faţă de 2. În mod similar, dacă vom scădea unu dintr-un caracter care conţine valoarea -128 vom obţine valoarea 127.

Acelaşi lucru se întîmplă şi pe întregi (int). Dacă în calculele noastre vom depăşi cea mai mare valoare reprezentabilă, aproximativ două miliarde, vom obţine valori negative. În concluzie trebuie să fim foarte atenţi la depăşiri, deoarece calculatorul nu va da nici o eroare, ci pur şi simplu o va lua de la capăt. Vom obţine valori aberante şi programul nostru va afişa numere ciudate.

Cum ne ferim de depăşiri? Folosind tipul întreg potrivit cu valorile maxime de care avem nevoie în program. Calculăm aceste valori din limitele impuse în problemă. Dar de ce nu putem să folosim întotdeauna cel mai mare întreg, tipul long long? Din mai multe motive:

  • Lipsă de memorie: un vector de long long ocupă dublu faţă de un vector de int şi de opt ori mai mult faţă de un vector de char! S-ar putea să nu ne ajungă memoria! Multe probleme dau memorie la limită exact în ideea ca voi să vă calculaţi cît mai bine necesarul.
  • Risipă: în viaţă este bine să fim economi (în ciuda a ceea ce ne învaţă consumerismul aşa zisei economii de piaţă). De ce să folosim mai multă memorie decît este nevoie? Nu toate programele se execută pe un calculator, care are multă memorie. Multe programe se execută pe circuite izolate, gen cipuri electronice din încărcătorul de mobil, sau în prăjitorul de pîine. Acele sisteme nu au multă memorie la dispoziţie.
  • Timp: operaţiile cu long long sînt mai lente decît cele cu int. De asemenea, din cauza unui mecanism care se numeşte cache, dacă ocupăm mai multă memorie programul se încetineşte.

Conversii

Atunci cînd atribuim o valoare de tip char unei variabile de tip int programul face automat o conversie de la 8 biţi la 16 biţi. La fel şi dacă atribuim o valoare de tip int unei variabile de tip char.

Conversie de întregi de la mic la mare

În acest caz totul funcţionează aşa cum ne-am aştepta, deoarece orice valoare mică este inclusă în intervalul de valori mai mari.

Conversie de întregi de la mare la mic

În acest caz există posibilitatea de depăşire. Drept pentru care este normal ca şi conversia să urmeze regulile depăşirilor. Ne putem închipui că la valoarea mare putem ajunge pornind de la ultima valoarea mică şi adunînd unu. Exemplu: ce valoare va afişa programul următor?

char c;
int i;
i = 128;
c = i;
printf( "%d", c );

Valoarea afişată va fi -128, deoarece 128 = 127 + 1; 127 fiind cea mai mare valoare caracter, următoarea valoare va fi -128. Din acelaşi motiv 129 se va converti la -127, 130 la -126... 383 la 127 şi 384 din nou la -128.

Conversie de la întreg la double

În acest caz nu avem probleme, decît în cazul cînd convertim de la long long, o valoare foarte mare. Nu voi detalia aici, dar conversiile de la char, short şi int la double sînt fără probleme.

Conversie de la double la întreg

În acest caz conversia se va face renunţînd la partea zecimală a numărului real şi apoi aplicînd regulile de conversie între tipurile întregi.

Tipul unei expresii

Am mai discutat despre tipul expresiilor. Orice operator va executa operația sa în tipul cel mai mare dintre operanzii săi. De exemplu o operație de adunare între int și long long se va face pe tipul long long prin conversia operandului int la long long. În cazul în care unul din operanzi este un tip întreg, oricare ar fi el, iar celălalt operand este de tip double, operația se va face pe tipul double prin conversia operandului întreg la double.

Tabel de descriptori citire/scriere

Să recapitulăm care sînt descriptorii de citire/scriere folosiți de scanf() și printf() pentru fiecare din tipurile învățate mai sus.

Tip variabilă Bytes Valori limită Format folosit (litere)
char 1 -128 ... 127 %d dacă vrem să afișăm numărul întreg
%c dacă vrem să afișăm caracterul
unsigned char 1 0 ... 255 %u dacă vrem să afișăm numărul întreg
%c dacă vrem să afișăm caracterul
short 2 -32768 ... 32767 %hd
unsigned short 2 0 ... 65535 %hu
int 4 -2147483648 ... 2147483647
aproximativ două milarde (2 cu nouă zerouri)
%d
unsigned int 4 0 ... 4294967295
aproximativ patru milarde (4 cu nouă zerouri)
%u
long long 8 -9223372036854775808 ... 9223372036854775807
aproximativ 9·1018 (9 cu 18 zerouri)
%lld în GNU/Linux și varena.ro
%I64d în Windows
unsigned long long 8 0 ... 18446744073709551615
aproximativ 18·1018 (18 cu 18 zerouri)
%llu în GNU/Linux și varena.ro
%I64u în Windows
double 8 valorile minime și maxime nu au aceeași relevanță,
dar erorile de reprezentare cresc cu mărimea numărului
%lf

Temă

Tema 41: să se rezolve următoarele probleme (program C trimis la vianuarena):

  • portofel dată la concursul Marele Premiu (PACO) 2013, clasa a 5a
  • împletire dată la olimpiada pe școală Tudor Vianu 2018, clasa a 9a

Rezolvări aici [1]