Clasa a V-a lecția 43 - 04 iun 2013

Tema - verificare

Discuție despre făcutul temelor în ultima clipă: mulți din elevii buni au obiceiul să-și facă tema în ultima clipă. Nu e bine deoarece:

• Dacă le faceți noaptea tîrziu sînteți obosiți.
• Le faceți cu stresul "dacă nu termin"; stresul vă face să nu dați randament.
• În ultima clipă vă va fi greu, dacă nu imposibil să găsiți soluția la probleme grele.

Sugestie: citiți tema cu atenție, din vreme, să spunem de joi. Simplul fapt că știți ce aveți de rezolvat vă va ajuta, chiar dacă, în final, veți face tema tot în ultima clipă. Mintea voastră lucrează în fundal, chiar dacă nu vă dați seama.

Discuție despre problemele Rotk (rotație multiplă vector fără a face rotații repetate cu unu) și Portofel (asemănătoare cu interclasarea vectorilor).

Felicitari celor care au rezolvat corect problema Rotk: Matei Deleanu, Alexandru Păcurar, Vlad Ulmeanu, Radu Priboi, Andrei Coman, Robert Popovici. Cei ce au încercat cu rotaţie cu un elemente, v-am spus că nu se va încadra în timp. Problema se rezolvă folosind un singur vector de 200 000 de elemente. Numai pentru atît avem spațiu. Așezăm elementele celor doi vectori unele după altele în acest vector, apoi aplicăm rotațiile de la 0 la n1-1 și de la n1 la n1+n2.

Felicitări celor care au rezolvat corect problema Portofel: Radu Priboi, Alex Păcurar, Robert Popovici.

O rezolvare la portofel, bazată pe interclasarea vectorilor sortaţi aici: [1]

Lecție

Exerciții cu vectori (continuare)

Sortarea prin selecție (select sort)

Se dă un vector de n elemente. Să se sorteze prin metoda selecției. Prin sortare înțelegem ordonare crescătoare a elementelor vectorului. Metoda selecției este următoarea: vom găsi maximul din vector, împreună cu poziția sa. Apoi vom interschimba maximul cu ultimul element din vector. Astfel ne vom asigura că ultimul element este chiar cel corect în vectorul ordonat. Ne-a rămas astfel un vector cu n-1 elemente, care trebuie sortat. Vom proceda la fel: vom găsi maximul în subvectorul de n-1 elemente, precum și poziția lui, și-l vom muta la coadă, rezultînd un vector de n-2 elemente. Continuăm procedura pînă ce vectorul este sortat.

Iată o exemplificare grafică:

9 2 8 3 6 5 3 9 6 | 6 2 8 3 6 5 3 9 | 9 6 2 8 3 6 5 3 | 9 9 6 2 3 3 6 5 | 8 9 9 5 2 3 3 6 | 6 8 9 9 5 2 3 3 | 6 6 8 9 9 3 2 3 | 5 6 6 8 9 9 3 2 | 3 5 6 6 8 9 9 2 | 3 3 5 6 6 8 9 9 | 2 3 3 5 6 6 8 9 9

Iată programul:

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

Vă recomand folosirea algoritmului de sortare prin selecție și nu a sortării cu bule, deoarece face mai puține operații. În practică el este de cinci pînă la zece ori mai rapid. Desigur, și mai rapidă este sortarea prin vectori de frecvență, numită și sortare prin numărare, atunci cînd ea poate fi aplicată (numerele sînt foarte mici).

Tipuri de date simple

Precum ştim, calculatorul reprezintă toate valorile, fie ele numere sau caractere, ca biţi, sau valori zero şi unu. Vom explora mai jos cîteva din tipurile simple de date, fără pretenţia de a trata exhaustiv subiectul. 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.

Tipul char

Este cel mai mic întreg. El ocupă 8 biţi, numiţi şi un octet (un octet are opt biţi). Care este intervalul de numere care se pot reprezenta pe 8 cifre binare? El este de la 0 la 2⁸-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 short

Este întregul următor ca mărime. El ocupă 16 biţi, sau 2 octeţi (pe alte arhitecturi poate să varieze). Intervalul de numere ar trebui să fie între 0 şi 2¹⁶-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 int

Este următorul întreg ca mărime. El ocupă 32 de biţi, sau 4 octeţi (pe alte arhitecturi poate să varieze). Intervalul de numere ar trebui să fie între 0 şi 2³²-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 long

Are aceeaşi mărime ca şi tipul int, drept care nu îl folosim. Şi atunci de ce există? Pentru ca pe alte arhitecturi poate fi mai mare ca int.

Tipul long long

Este dublu faţă de tipul int. El ocupă 64 de biţi, sau 8 octeţi (pe alte arhitecturi poate să varieze). Intervalul de numere ar trebui să fie între 0 şi 2⁶⁴-1, dar pentru că avem şi numere negative intervalul devine -2⁶³..2⁶³-1. Dacă aproximăm 2¹⁰ cu 10³ aceasta înseamnă cu aproximaţie 8 cu 18 zero după el. Pentru a-l citi sau tipări vom folosi descriptorul %lld.

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.

Tabel de descriptori citire/scriere

Să recapitulăm care sînt descriptorii de citire/scriere pentru fiecare din tipurile învățate mai sus.

Tip variabilă	Format folosit (litere)
char	%d sau %c
short	%hd
int	%d
long long	%lld
double	%lf

Temă

Rezolvați următoarele probleme:

• Prime rezolvată de 100p folosind tipul long long (strict pentru variabilele pentru care este nevoie!)
• Încă o problemă ce va fi afişată aici. Actualizare: nu mai aveți încă o problemă :) Bucurați-vă!