Vectori de frecventa

Utilizarea unui vector de frecventa este oportuna cand trebuie sortate (crescator/descrescator) valori din domenii inguste (litere, numere de cateva cifre:1,2,3,4).

Metoda presupune numararea (stabilirea frecventei) fiecarei valori in parte.

Studiu de caz:

Fişierul text NR.TXT conţine pe o singură linie, separate prin câte un singur spaţiu, cel mult 100 de numere naturale, fiecare număr având cel mult 4 cifre. Scrieţi un program C/C++ care citeşte numerele din fişierul NR.TXT şi afişează pe ecran, separate prin câte un spaţiu, în ordine descrescătoare, toate numerele din fişier care au cel mult 2 cifre. Dacă fişierul nu conţine astfel de numere se va afişa pe ecran mesajul NU EXISTA.

Varianta 1. Ordonare

int nv=0, vf[101],x;
//adaug in vector orice valoare care respecta conditiile
while (fin>>x) if (x<100) {nv++; v[nv]=x;} 

if (nv==0) fout>>"NU EXISTA";
else {sortare (v,nv;); afisare_desc (v,nv);}

Complexitatea algoritmului este data de sortare. Probabil cea mai buna varianta pe care o folosit este O(n^2). Daca toate cele 100 numere se califica, ajungem la o complexitate de 10000 de operatii.

Varianta 2. Vector de frecventa

int vf[100], x;
//marchez aparitia fiecarei valori de maxim 2 cifre
while (fin>>x) if (x<100) vf[x]++; 

for(x=99;x>=0;x--) //am in vedere valorile de la 99..0
for(k=1;k<=vf[x];k++) //de vf[x] ori , adica de numarul de aparitii a lui X ori
      fout<<x;  //afisez X

Presupunand ca sunt n valori (maxim 100), complexitatea algoritmului este 100+n=200 , adica O(n) operatii.

 

 

 

Instructiunea FOR

Exista trei instructiuni (structuri) repetitive folosite in toate limbajele:

• instructiunea repetitiva cu test initial CAT TIMP (WHILE) (se foloseste cand numarul de repetitii este nedefinit)
• instructiunea repetitiva cu test final REPETA-PANA CAND (DO WHILE sau REPEAT) (se foloseste cand numarul de repetitii este nedefinit)
• instructiunea repetitiva cu un numar cunoscut de pasi PENTRU (FOR) (se foloseste cand numarul de repetitii este cunoscut – un numar fix de ori.)

Sintaxa:

• FOR(initializare; test final; pasul urmator) instructiune;
• for (i=A; i<=B; i++) {secventa de repetat}
• for (i=1; i<=n; i++) {secventa de repetat}

Efect:

• pentru fiecare valoare a contorului i intre expresia initiala si expresia finala se executa instructiunea;

Exemplu: for (i=1; i<=n; i++) cout<<” Nu ma prinzi!”;

• pentru fiecare valoarea a variabilei i, de la 1 la N, se afiseaza ” Nu ma prinzi!”; de N ori
• daca secventa ce trebuie repetata contine mai multe instructiuni, acestea se vor grupa cu acolade

Observatii:

• instructiunea este “ceruta” daca descrierea algorimului spune “de la valoarea X la valoarea Y”, “pentru primele X valori”, “de X ori”, …

L11. Instructiunea WHILE

Exista trei instructiuni (structuri) repetitive folosite in toate limbajele:

• instructiunea repetitiva cu test initial CAT TIMP (WHILE) (se foloseste cand numarul de repetitii este nedefinit)
• instructiunea repetitiva cu test final REPETA-PANA CAND (DO WHILE sau REPEAT) (se foloseste cand numarul de repetitii este nedefinit)
• instructiunea repetitiva cu un numar cunoscut de pasi PENTRU (FOR) (se foloseste cand numarul de repetitii este cunoscut – un numar fix de ori.)

Instructiunea WHILE

Sintaxa :

• while (expL) instructiune;

Efect

1. Se evalueaza expresia logica
2. Daca valoarea expresiei logice este 1 (adevarata) se executa instructiunea si se revine la pasul 1
3. daca valoarea expresiei logice este zero (falsa) se continua cu instructiunea de dupa punct-virgula

Observatii:

• in esenta, cat timp valoarea expresiei logice este adevarata, se executa instructiunea
• daca valoarea expresiei logice este falsa de la inceput atunci instructiunea nu se mai executa
• daca WHILE trebuie sa repete mai mult de o instructiune, acestea se vor incadra intre acolade;
• instructiunea WHILE se mai numeste “repetitiva cu test initial” sau “conditionata anterior”, pentru ca intai verifica valoarea conditiei si apoi executa secventa ce trebuie repetata

Problema exemplu. Fie A si B doua valori naturale. Sa se simuleza impartirea cu rest a lui A la B (prin scaderi repetate) si sa se determine catul si restul impartirii.

#include <iostream.h>
void main()
{//declararea
int A, B, C=0;
//citirea
cin>>A>>B;
//prelucrarea
while(A>=B) {A=A-B; C++;};
//Afisarea rezultatelor
cout<<"catul este :"<<C<<endl;
cout<<"restul este : "<<A;
}

Explicatii. Cand impartim pe A la B cautam “de cate ori se cuprinde” B in A, altfel spus cate scaderi ale lui B din a se pot face.

Un tip e problema ce necesita folosirea instructiunii WHILE este prelucrarea unui sir de valori ce se incheie cu zero.

Ideea : Se citeste fiecare valoare si daca este nenula se prelucreaza; Acest pas se repeta pana citim valoarea zero. (Ex: 23, -4, 5, 12, 79, 0).

Codul corespunzator este:

cin>>x;
While (x!=0) { //prelucrez valoarea X citita;
               ..............................
               //citesc urmatoarea valoare din sir
               cin>>x;};

Probleme ce folosesc acest algoritm pot umari:

• numarul de valori din sir
• valoarea maxima/minima
• numarul de aparitii a unei valori K

L10. Instructiunea DO – WHILE

Exista trei instructiuni (structuri) repetitive folosite in toate limbajele:

• instructiunea repetitiva cu test initial CAT TIMP (WHILE) (se foloseste cand numarul de repetitii este nedefinit)
• instructiunea repetitiva cu test final REPETA-PANA CAND (DO WHILE sau REPEAT) (se foloseste cand numarul de repetitii este nedefinit)
• instructiunea repetitiva cu un numar cunoscut de pasi PENTRU (FOR) (se foloseste cand numarul de repetitii este cunoscut – un numar fix de ori.)

Instructiunea DO – WHILE

Sintaxa: do { instructiuni} while (conditie) ;

Efect:

1. se executa secventa de instructiuni
2. se evalueaza conditia
3. daca valoarea conditiei este adevarata se revine la pasul 1
4. daca valoarea conditiei este falsa se continua cu instructiunea de dupa punct si virgula

Observatii:

• do-while se mai numeste instructiune cu test final sau conditionata posterior
• observati ca intai se executa secventa de instructiuni (macar o data) si apoi se testeaza
• succesiunea de operatii este instructiune, test, instructiune, test, ….. test, instructiune, test.

Exemplu:

O problema la care putem folosi DO-WHILE este prelucrarea cifrelor unui numar natural/intreg. Cifrele vor fi prelucrate pe rand, de la sfarsitul numarului catre inceput, de fiecare data taind ultima cifra (deja prelucrata). Algoritmul se reia pana cand nu mai sunt cifre in numar, adica valoarea N ajunge la valoarea zero.

Sesizati ca orice numar are o ultima cifra, motiv pentru care intai prelucrez  si tai , si apoi verific daca mai sunt cifre de prelucrat.

Scheletul algoritmului ar fi:

cin>>n;
do { //prelucrarea ultimei cifre
      ..............;
      // tai ultima cifra
     n=n/10;
    } while (n!=0);

Observatii: puteti determina intai ultima cifra (int uc=n%10; )  si apoi sa prelucrati variabila uc

Probleme. fie N un numar natural.

1. Cate cifre are N?
2. Care este suma cifrelor lui N?
3. Care este cea mai mare cifra din numar? (valoarea maxima). Analog minima.
4. Sa se determine prima cifra a numarului N.
5. De cate ori apare o cifra data C, in numarul N?
6. Sa se genereze “oglinditul” numarului N. (daca N=1987 atunci oglinditul va fi 7891)
7. Folosind problema de mai sus, stabiliti daca numarul N este palindrom.

L9. Instructiunea IF

Instructiunea IF

Sintaxa: if (exp_logica) instrDA;  else instrNU;

Efect:

• se evalueaza valoarea expresie logice
• daca valoarea calculata este adevarata (nenula) se executa instructiunea instrDA si apoi instructiunea de dupa IF
• daca valoarea calculata a expresiei este nula se executa instructiunea instrNU (daca exista ramura ELSE) si apoi instructiunea de dupa IF

Exemplu:

• if (a%2==0) cout>>”valoarea este para”; else cout<<” valoarea este impara”;
• se verifica daca restul impartirii la 2 a variabilei A este zero
• daca DA se executa cout>>”valoarea este para”;
• daca NU se executa cout>>”valoarea este impara”;

Observatii:

• in C/C++ instructiunile, pe langa efectul lor, returneaza o valoare adevarat (1 – unu) daca se executa corect si fals (0 – zero) daca executia a fost eronata;
• secventa if (a=b) instr1; else instr2; va executa intotdeauna numai instr1 pentru ca atribuirea a=b se executa corect
• a nu se confunda a=b (lui a i se atribuie valoarea lui b) cu a==b (care verifica daca cele doua valori sunt egale)
• daca in loc pentru o valoare a conditiei testate algortimul impune executarea a mai mult de o instructiune, acestea se vor incadra intre acolade: if (conditie) { …instructiuni pe ramura DA} else {instructiuni pe ramura NU};

Probleme:

1. Fie N un numar natural. Sa se afiseze textul PAR sau IMPAR, functie de valoarea lui N.
2. Fie N un numar natural. Sa se afiseze  textul POZITIV,  NEGATIV sau ZERO dupa caz.
3. Fie A si B capetele unui interval. Sa se stabileasca daca o valoare X apartine intervalului [A,B].
4. Fie A si B doua valori intregi. Sa se afiseze A si B in ordine crescatoare.
5. Fie A si B doua valori intregi. Sa se calculeze X, solutia ecuatiei A*X+B=0.

Observatii:

1. Se verifica valoarea expresiei N%2==0
2. Se compara N cu 0 si se afiseaza dupa caz.
3. Daca A este mai mare decat B, valorile trebuie interschimbate.
4. –
5. Trebuie verificat daca A nu este zero, caz in care se afiseaza un mesaj si se iese fortat, cu RETURN.

L8. Atribuirea

Variabilele pot primi valori prin citire sau atribuire.

Atribuirea

Sintaxa: variabila=expresie;

Efect:

• se calculeaza valoarea expresiei
• aceasta valoare se scrie in variabila, peste vechea valoare, care se pierde

Exemple:

• A=0;
• B=5;
• A=B+6;
• A=B+A; (in A se va memora suma dintre A si B)
• un caz deosebit este incrementarea (cresterea cu 1 a valorii unei variabile)
  • a=a+1;
  • aceasta operatie se mai scrie a++; (++ este operator unar)
• operatia analoga, de scadere cu 1 a valorii unei variabile, se numeste decrementare:
  • a=a-1;
  • sau a–;
• citind diverse programe realizate in C/C++ puteti intalni si exprimari de genul:
  • a=a+ –b; cu semnificatia b–; a=a+b; (analog ++b)
  • a+=b; cu semnificatia a=a+b;
• … cum va place!

Probleme

1. Teodor is consuma jumatate din salariul sau pe facturi. Cititi salariul lui Teodor si afisati cu cat ramane Teodor.
2. Cititi de la tastatura distanta si timpul necesar unui tren pentru a parcurge respectiva distanta. Calculati viteza medie de deplasare.
3. Ana si Bogdan sunt colegi de banca. In pauza s-au gandit sa-si schimbe scaunele intre ei astfel incat , in orice moment, fiecare sa stea pe un scaun. Copiii astia chiar n-au treaba!!!

Observatii:

• la problema 1 pot apare urmatoarele dificultati:
  • daca salariul are valoare impara, rezultatul nu este real => float rez=(float) salar/2;
  • salariul este declarat int salar; si introduceti un salariu mai mare de 32767 rezultatele sunt imposibile; de ce? => variabilele de tip int nu pot depasi 32767; de aceea, valorile mai mari sunt trunchiate
• la problema 2, pe langa valori de bun simt, puteti incerca si impartirea la zero 🙂
• problema 3 face apel la o tehnica de lucru numita interschimbarea a doua valori;
  • una dintre variantele de rezolvare face apel la inca un scaun (variabila): int aux=a; a=b;b=aux;
  • exista si o varianta fara variabila auxiliara (pentru cazul in care vorbim de valori 🙂 ): a=a+b; b=a-b;a=a-b;

Sa privim inainte:

• din exemplele de mai sus este limpede ca variabilele/datele de intrare trebuiesc verificate inainte de a fi prelucrate
• de aceea, vom studia in continuare instructiunea IF

L7. Citirea. Afisarea

Programele in limbajul C folosesc instructiunile printf (pentru afisarea datelor) si scanf (pentru citirea datelor) ca operatii de intrare/iesire.

Pentru usurinta operatiilor de citire/afisare vom folosi instructiuni consacrate in C++: cin si cout.

Instructiunea CIN

Sintaxa: cin>>variabila1>>variabila2…;

Efect: se preiau de la tastatura (Console INput) valori pentru fiecare variabila din sir;

Cerinte : folosirea instructiunii necesita #include <iostream.h>

Exemplu:

• int A,B; cin>>A>>B;
• Pe rand, se introduc valori de la tastatura pentru variabilele intregi A si B.

Instructiunea COUT

Sintaxa: cout<<expresie1<<expresie2;

Efect: se afiseaza, pe rand, valorile expresiilor;

Cerinte: necesita, de asemenea, folosirea #include <iostream.h>

Exemple:

• cout<<“Rezultatul este”<<endl<< A<<‘+'<<B<<‘='<<A+B;
• s-au afisat :
  • constanta sir de caractere (text) “Rezultatul este”
  • constantele caracter ‘+’ si ‘=’
  • valorile variabilelor  A si B
  • valoarea expresiei A+B

L6. Structura unui program C/C++

In general, un program este un sir de instructiuni.  In C/C++ programul este o functie numita main.

Efectul instructiunillor din C/C++ este stabilit intr-un fisier numit stdio.h (h vine de la header). Acest fisier este incarcat implicit pentru a asigura buna functionare a programului. Daca dorim sa folosim instructiuni mai complexe (gen cin, cout) trebuie sa specificam si headerul care explica functionarea acestor instructiuni (iostream.h).

De asemenea, trebuie sa stabilim ce variabile folosim, pentru a le putea aloca spatiu si a le da valori. Spre deosebire de alte limbaje, in C/C++ declararea variabilelor folosite poate fi facuta si pe parcursul executiei programului.

Structura unui program C/C++ este urmatoarea

//acesta este un comentariu; el nu influenteaza programul
//declararea headerelor
#include <iostream>
using namespace std;
//declararea variabilelelor
....
//programul principal
int main()
{
// instructiunile programului
..........
return 0;} //aici se incheie programul

In exemplul urmator (citirea a doua valori si afisarea sumei lor) trebuie sa observati:

1. orice program are trei parti:
2. citirea datelor initiale si initializarea variabilelor necesare
3. prelucrarea datel;or (programul propriuzis)
4. afisarea rezultatelor

Puteti observa de asemenea:

• cum se declara o variabila
• cum se foloseste o constanta text (sir de caractere)
• cum se citeste o data
• cum se afiseaza un sir de caractere, constante, variabile si expresii
• cum putem schimba valoarea unei variabile

# include <iostream>
using namespace std;
int a,b,c;
int main()
{
//citirea datelor initiale; initializarea altor variabile;
cin>>a>>b;

//prelucrarea datelor
c=a+b;

//afisarea datelor
cout<<"afisarea rezultatului"<<endl;
cout<<a<<'+'<<b<<'='<<a+b;
cout<<"Suma calculata  este "<<c;
return 0;
}

Observatie

• instructiunea return permite intreruperea brusca a executiei unui program; puteti folosi aceasta instructiune daca , din diverse motive doriti intreruperea brusca a executiei unui program.

L5. Operatori. Expresii

Valorile variabilelor interactioneaza intre ele prin operatii. Simbolurile prin care reprezentam aceste operatii se numesc operatori. Combinatiile care apar in urma folosirii operatorilor si variabilelor/constantelor se numesc expresii.

Expresii

O expresie poate fi:

• o constanta/variabila
• o combinatie de tipul operator expresie (cazul operatorilor unari: – a)
• o combinatie de tipul expresie operator expresie (cazul operatorilor binari: a+b )

Operatori

Operatorii folositi in C/C++ sunt:

• operatori aritmetici: +,-,*, /, %
  • A/B reprezinta catul impartirii lui A la B
  • A%B reprezinta restul impartirii lui A la B
    • A%10 reprezinta ultima cifra a lui A
    • A%2 va avea valoarea zero daca A este par si 1 daca A este impar
• operatori relationali: <, <=, ==, !=, >=, >
  • majoritatea operatorilor relationali sunt intuitiv identici cu cei folositi in matematica; excepti fac == si !=
  • expr1 == expr2 verifica daca valoarea expresiei din stanga este aceeasi cu valoarea din dreapta
  • analog, expr1 != expr2 verifica daca valoarea expresiei din stanga este diferita de valoarea din dreapta
  • in toate cazurile raspunsul la intrebari (ex: A este mai mic decat B ) poate fi doar DA sau NU, adica ADEVARAT sau FALS; aceste raspunsuri se numesc valori logice (valori de adevar)
• operatori logici: si logic( && ) , sau logic ( | | ), negare ( ! )
  • evident raspunsurile la operatorii logici sunt tot valori logice (Adevarat sau Fals)
  • operatorul logic SI ( && )
    • Exemplul Alinei: Imi plac baietii atletici SI glumeti. Aceasta propozitie poate fi scrisa ca A && B (A =Imi plac baietii atletici si B = Imi plac baietii glumeti)
    • posibilitatile care apar sunt:
      • neatletic, posac=> nu imi place ; raspuns NU (FALS)
      • neatletic, glumet => nu imi place ; raspuns NU (FALS)
      • atletic, posac => nu imi place; raspuns NU (FALS)
      • atletic, glumet => imi place; raspuns DA (ADEVARAT)
    • observam ca raspunsul este DA (ADEVARAT) numai in cazul cand ambele proprietati sa indeplinesc ( si atletic si glumet); daca macar o proprietate nu se indeplineste raspunsul este NU (FALS)
  • operatorul logic SAU ( || )
    • Pentru ca Alina nu a gasit ce cauta, a schimbat regula. Exemplul Alinei: Imi plac baietii atletici SAU glumeti. Aceasta propozitie poate fi scrisa ca A || B (A =Imi plac baietii atletici si B = Imi plac baietii glumeti)
    • posibilitatile care apar sunt:
      • neatletic, posac=> nu imi place ; raspuns NU (FALS)
      • neatletic, glumet => imi place; raspuns DA (ADEVARAT)
      • atletic, posac => imi place; raspuns DA (ADEVARAT)
      • atletic, glumet => imi place; raspuns DA (ADEVARAT)
    • observam ca raspunsul este DA (ADEVARAT) daca macar una din proprietati este adevarata; daca nici una dintre proprietati nu se indeplineste raspunsul este NU (FALS)
  • operatorul logic de negare ( ! )
    • l-am folosit deja pentru != (ne-egalitate)
    • Exemplul Alinei: Nu iti place?; Aceasta propozitie poate fi scrisa ca !A.
    • posibilitatile care apar sunt:
      • Alinei ii place: ! (Adevarat) => FALS
      • Alinei nu ii place: ! (Fals) => ADEVARAT

Exemple:

• Cum scriem A apartine intervalului (- infinit, 7)
  • Raspuns: A<7
• Cum scriem A apartine intervalului [3, infinit)
  • Raspuns: A>=3
• Cum scriem A apartine intervalului  [3, 7)
  • Raspuns: (A>=3) && (A<7)
• Cum scriem ca A nu apartine intervalului [3, 7)
  • Raspuns 1: ! ( (A>=3) && (A<7) )
  • Raspuns 2: valoarea lui A trebuie sa fie inainte de 3 SAU dupa 7=> A<3 || A>=7

Din acest ultim exemplu observam ca raspunsurile sunt echivalente (pentru acelasi A, indiferent de valoarea lui, obtinem acelasi raspuns). ! ( (A>=3) && (A<7) ) echivalent cu A<3 || A>=7.

Echivalentele de acest tip au fost studiate de matematicianul De Morgan, care a spus ca:

• ! (A && B) = !A || !B
• ! (A || B) = !A && !B

Prioritatea operatorilor

Spre deosebire de matematica, in informatica, pentru scrierea expresiilor se folosesc doar paranteze rotunde. Pentru a evita folosirea excesiva a parantezelor rotunde trebuie sa stiti prioritatea operatorilor (ordinea operatiilor):

In ordinea scaderii importantei, operatorii sunt:

• ! (negare)
• *, /, %
• +, –
• <, <=, >=, >
• ==, !=
• &&
• ||

Exemplu: la expresia ! (A || B) = (!A) && (!B) nu sunt necesare parantezele din partea a 2-a deoarece oricum operatorul de negare se activeaza mai inainte de operatorul &&.

L4. Tipuri

Tipurile intregi

Tipurile intregi din C/C++ sunt: enum, short int,  int, unsigned int, long, unsigned long.

Pentru fiecare variabila se aloca (rezerva) un spatiu de memorie conform cu tipul ei. Acest lucru influenteaza domeniul de valori care se poate aloca variabilei:

• enum, short int, int:
  • spatiu: 16 biti
  • domeniu: -32768..32767
• unsigned int
  • spatiu: 16 biti
  • domeniu: 0..65535
• long
  • spatiu: 32 biti
  • domeniu:-2147483648 .. 2147483647
• unsigned long
  • spatiu: 32 biti
  • domeniu:0 .. 4294967295

Observatii:

• valorile UNSIGNED (eng: fara semn) sunt valori naturale, cu valori pozitive
• in sprijinul ideii de mai sus, ca tipul determina domeniul de valori, venim cu urmatoarea demonstratie:
  • presupunem ca avem o variabila A de tip int (pe 16 biti); aceasta inseamna ca valoarea maxima ce se poate memora este un sir de 15 pozitii binare cu 1 (primul bit memoreaza semnul); daca convertim aceasta valoare din baza 2 in baza 10 (puteti folosi aplicatia CALCULATOR din Windows) obtinem exact 32767
  • analog, pentru o variabila unsigned int (16 biti) putem memora 16 pozitii binare cu 1 (din cauza unsigned, nu mai avem semn – adica valori pozitive); sirul de 16 pozitii binare reprezinta valoarea 65535 din baza 10.

Tipurile reale

 

• float(32 biti):   3.4 * (10**-38) .. 3.4 * (10**+38)
• double(64 biti): 1.7 * (10**-308) .. 1.7 * (10**+308)
• long double(80 biti): 3.4 * (10**-4932) .. 1.1 * (10**+4932)

Tipul caracter

• char -127 .. 127 (pentru fiecare caracter este asociata, in mod unic, o valoare de la 0 la 127; aceasta asociere se numeste CODUL ASCII)