Clasa a V-a lecția 24 - 1 feb 2018

From Algopedia
Jump to navigationJump to search

Anunțuri

  • Și în acest weekend vom organiza un concurs de pregătire pentru olimpiadă. El va fi sîmbătă la ora 10:30.
  • Lipsă de verificare a soluțiilor și pescuit la varena:
    • În continuare unii din voi folosesc mîna mea dreaptă, varena, drept verificator de soluții. Vă purtați cu leul ca și cum ar fi o pisicuță, îl jigniți. În loc să vă creați propriile teste voi folosiți varena pe post de compilator. Vă reamintesc că a trimite o sursă la varena este echivalent cu a îmi da mie acea sursă. Puneți-vă întrebarea, "i-aș da lui Frâncu sursa asta?". Daca răspunsul este "parcă nu chiar", atunci n-o trimiteți nici la varena!
    • Leul poate să muște și să se apere împotriva pescarilor înverșunați. Pot foarte ușor să instructez varena să ascundă rezultatele la concurs pînă la terminarea concursului. Nu mă siliți să iau astfel de măsuri, nu ar fi corect față de cei ce nu abuzează.
    • Cei ce mă îngrijorează prin pescuit excesiv sunt:
      • grupa de dimineață: Benescu, Cojocaru, Iordache, Mocanu, Petcu, Voicu.
      • grupa de după-amiază: Fares, Rebengiuc.

Tema - comentarii

  • La minnrk elegant era să vă opriți după afișarea a k cifre.
  • minnrk v-a fentat pe mulți, nu v-ați dat seama că un număr de 100 de cifre nu poate fi citit ca întreg.
  • Apoi v-ați prins că trebuie să citiți caractere pînă la spațiu, bravo, foarte bine!
  • Unii din voi încă scrieți foarte ciudat căutarea unui element într-un vector.
  • La felinare1 exista o rezolvare elegantă fără long long (era clar, nu, din moment ce nu am predat long long)
  • La felinare1 unii nu ați simplificat expresia matematica. Lene? Dacă nu vreți sa știți matematica puteți face multe altele, istorie, pictura, pian, dar nu informatică (posibil ca și acele domenii să ceară să știți ceva matematica, totuși).
  • La cifra2 exista și o soluție mai elegantă, bazată pe o observație matematică. Cei care au găsit acea soluție sunt:
    • grupa de dimineață: Lia Mihăilă.
    • grupa de după-amiază: Yusuf Fares, partial Mircea Rebengiuc.

Tema - rezolvări

Rezolvări aici [1]

Lecție

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

Tipuri de numere întregi

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: sistem de operare Windows, compilator gcc pe 32 biți î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 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 int

Tipul întreg cu care sîntem obișnuiți. 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 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 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 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 8 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.

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;
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 32 biţi. La fel, dacă atribuim o valoare de tip int unei variabile de tip char programul compilat va face o conversie de la 32 de biti la 8 biți.

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. Nu vom avea nici o problemă să atribuim o variabilă de tip char uneia de tip int, sau o variabilă de tip int uneia de tip long long.

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.

Tipul unei expresii

Dacă o expresie conține valori "amestecate", adică și de tip int și de tip long long, de ce tip va fi rezultatul calculat?

Regulă: fiecare operator va opera cu valoarea cea mai mare a operanzilor săi.

Ce înseamnă acest lucru? Fiecare operație aritmetică, fie ea adunare, scădere, înmulțire, etc, se va uita la cele două numere pe care le adună, sau scade, etc. Dacă unul este de tip int, iar al doilea de tip long long, atunci operația se va efectua pe tipul long long, deoarece este mai mare. Variabila de tip int va fi convertită la tipul long long.

Exemplul 1

int a;
long long x, y;
a = 100000000; // o suta de milioane
x = 200000000; // doua sute de milioane
y = a * x;     // calculul se va face pe long long, convertind variabila 'a' la long long
printf( "%lld", y );

Programul va afișa produsul, adică 2 cu 16 zerouri.

Atenție: depășirile sînt rele (în general). Cum ne asigurăm că nu vom avea o situație de depășire? Asigurîndu-ne că valoarea atribuită nu depășește valoarea maximă posibilă a variabilei în care atribuim.

Exemplul 2

int a;
long long x;
a = 200000000; // doua sute de milioane
x = a * a;
printf( "%lld", x );

Ce va afișa programul de mai sus? Ne-am aștepta să obținem răspunsul 40000000000000000, adică 4 urmat de 16 zerouri, nu? Ei bine, programul afișează -1090256896! De ce oare? Evident programul a generat o depășire de numere întregi, dar de ce? Doar am atribuit rezultatul înmulțirii unei variabile de tip long long, nu-i așa?

La momentul cînd se face calculul expresiei, valoarea de după egalul atribuirii, programul nu știe că urmează să atribuie rezultatul unei variabile de tip long long. El va aplica regula tipului unei expresii. Va observa că valorile înmulțite sînt de tip int și va face calculul pe int. De aceea apare depășirea. Valoarea depășită, incorectă, va fi cea care va fi atribuită variabilei x.

Cum scriem corect această secvență de program? Dacă înmulțirea conține măcar o valoare de tip long long ea se va evalua corect. Putem, deci, fie să declarăm variabila a ca long long, fie, mai elegant, să ne folosim chiar de variabila x, astfel:

int a;
long long x;
a = 200000000; // doua sute de milioane
x = a;
x = x * x;
printf( "%lld", x );

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ă Valori limită Format folosit (litere)
char -128 ... +127 %d dacă vrem să afișăm numărul întreg
%c dacă vrem să afișăm caracterul
int -2147483648 ... 2147483647
aproximativ două milarde (2 cu nouă zerouri)
%d
long long -9223372036854775808 ... 9223372036854775807
aproximativ 9·1018 (9 cu 18 zerouri)
%lld în GNU/Linux și varena.ro
%I64d în Windows

Temă

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

Rezolvări aici [2]