RSS

Category Archives: C2. Programare

Aceasta sectiune urmareste programa scolara pentru obiectul Informatica (varianta C)

Vectori de frecventa

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.

 

 

 

 
2 Comments

Posted by on 13/01/2017 in C2_2 Limbajul C/C++

 

Tags:

Numere mari

sursa: http://ler.is.edu.ro/~cex_is/Informatica/pregatire.html

Numere mari

Necesitatea

In momentul cand unei variabile i se stabileste un tip intreg, limitam valorile pe care le poate avea variabila, la tipul folosit.

Name Description Size* Range*
Char Character or small integer. 1byte signed: -128 to 127
unsigned: 0 to 255
short int (short) Short Integer. 2bytes signed: -32768 to 32767
unsigned: 0 to 65535
int Integer. 4bytes signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295
long int (long) Long integer. 4bytes signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295

 

Ce facem insa daca avem nevoie de numere intregi mai mari decat tipurile existente?

Putem reprezenta numarul intreg ca un vector ce contine sirul de cifre ale numarului.

x=40375 Vectorul asociat va fi

5 7 3 0 4

 

Dupa cum observati, in vector, numarul este scris in ordine inversa, astfel incat sa putem efectua cu usurinta operatiile aritmetice.

Declararea tipului corespunzator unui numar mare poate fi:

Typedef int nrmare[1000];

Citirea unui numar mare.

Putem realiza citirea unui numar mare intr-un sir de caractere pe care il vom transforma in vector de cifre.

void citire(nrmare v, int n)

{int I; char sir[100];

fin.get(sir,100); n=strlen(sir); //sir de caractere

for (i=n-1; i>0;i–) v[n-i-1]=(int) (sir[i]-‘0’); //convertesc caracterul cifra in cifra… numerica

}

Afisarea unui numar mare

void afisare(nrmare v, int n)

{int i;

for(i=n-1;i>0;i–) cout<<v[i];

}

Adunarea a doua numere mari

Presupunem ca avem 2 vectori Asi B, reprezentand numere cu NA, respectiv NB cifre si calculam suma C, dintre A si B.Trebuie sa efectuam operatia de adunare, cifra cu cifra, avand grija de problema depasirii ordinului. De asemenea, trebuie avute in vedere situatiile:

  • Daca valorile nu au acelasi ordin va trebui sa completam numarul mai mic cu zerouri
  • Daca in urma adunarii obtinem depasire de ordin, va trebui sa mai adaugam o cifra la vectorul suma.

Void suma (nrmareA, nrmare B, nr mare C, int NA,int NB, int N)

{Int I, t;

If (NA<NB) {for(i=NA; i<nb; i++) A[i]=0; NA=NB;}

Else {for(i=NB; i<NB; i++) B[i]=0; NB=NA;}

N=NB;t=0;

For(i=0;i<N;i++) {t=A[i]+B[i]+t;C[i]=t %10; t=t/10;}

If(t>0) {N++;C[N-1]=t;}

}

Compararea a doua numere mari

Fie A (cu NA cifre) si B (cu NB cifre) doua numere mari. Vom realiza o functie care va stabili care dintre valorile A si B este mai mare. Functia va returna -1 daca A<B, 0 daca A=B si +1 daca A>B.

Intcompar(nrmare A, nrmare B, int NA, int NB)

{if (NA<NB) return -1; //B estemai mare

if (NB<NA) return +1; //A estemai mare

//suntempecazul NA=NB.

//Cautamceamaisemnificativadiferenta de cifre.

For(i=NA; i>=0 && A[i]==B[i]; i–);

If(i<=0) return 0 ; //numerelesuntidentice

If (A[i]<B[i]) return -1;

else return +1;

}

Diferenta a doua numere mari

Calculam diferenta D dintre A (cu NA cifre) si B  (cu NB cifre). Presupunem ca B este mai mic si are completate spatiile libere cu zerouri.

Void diferenta (nrmare A, nrmare B, nr mare &D, int NA, int NB, int&N)

{IntI,t=0;

For (i=0,i<NA; i++)

{D[i]=A[i]-B[i]+t;

If(D[i]<0) {D[i]=D[i]+10; t=-1;}

Else t=0;

}
while(i>=0 && D[i]==0) i–;

N=I+1;

}

Inmultirea cu un scalar

Fie un numar mare A (cu NA cifre) si un numar natural X. Trebuie sa realizam inmultirea numarului A cu X.

Void scalare(nrmare A, int NA, int X)

{intI,t;

t=0;

for(i=0;i<NA;i++) {t=A[i]*x+t; A[i]=t%10; t=t/10;}

//ramane sa completam cu cifrele lui t, in masura in care mai exista

While (t>0) {NA++; A[NA-1]=t%10; t=t/10;}

}

Inmultirea a doua numere mari

Fie A si B doua numere mari. Dorim sa realizam produsul P intre A si B. Practic este vorba de o inmultire succesiva a  numarului mare A cu salarul B[i]. De observat ca pozitia in care incepem sa completam P este tot i.

Void produs(nrmare A, nrmare B, nrmare P, int NA, int NB, int NP)

{int I, j, t;

For (i=0;i<NB;i++)

{//produsul intre A si scalarul B[i]

t=0;

for(j=0;j<NA;j++)

{t=t+A[j]*B[i]+p[i+j];

p[i+j]=t%10;

t=t/10;}

if (t>0) p[i+j]=t;

}

NP=NA+NB+1;

}

Impartirea a doua numere mari

Fie A (cu NA cifre) si B (cu NB cifre). Vrem sa realizam impartirea lui A la B. Folosim observatia conform careia impartirea este o scadere repetata.

 

Void impartire(nrmare&A, nrmare B, nrmare C, int&NA, int NB, int&NC)

{NrmareD;

IntNC,I,ND;

NC=0;ND=0;

For(i=0;i<900;i++) c[i]=0;

While (compar(A,B,NA,NB)>0)

{//fac diferenta si o memorez tot in A

Diferenta(A,B,D,NA,NB,ND);

For(i=0;i<ND;i++) A[i]=D[i];

//incrementez catul C

t=1;

For(i=0;t!=0;i++)

{t=t+c[i];

c[i]=t%10;

t=t/10;

}

NC=i+1;

}

Afisare(A,NA);

Afisare(C,NC);

}

 

Problemepropuse:

  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=438
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=74
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=258
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=432
  1. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=500
 
 

Strcpy, strchr, strstr

Strcpy (s1, s2);

Strcpy, pentru atribuire

Efectul acestei functii este ca la adresa din memorie asociata variabilei/stringului S1 se copie ceea ce sa gaseste la adresa asociata variabilei S2. Practic se copie stringul S2 caracter cu caracter, inclusiv marcatorul de sfarsit;

char s1[]="Anamaria", s2[]="Anne-Marie"; strcpy(s1,s2); cout<<s1;

S1 contine caracterele “Anne-Marie” si ‘/n’ la sfarsit.

Un exemplu de folosire ar putea fi:

char voc[10]; strcpy(voc,"aeiouAEIOU");

Strcpy, pentru stergere

Conform definitiei, de fapt se realizeaza o copiere de la o adresa la alta. Atunci, putem utiliza STRCPY pentru a sterge/modifica un string.

Stergerea primului caracter

strcpy(s,s+1);

Daca S ar contine cuvantul “Anamaria”, atunci cuvantul de la adresa S+1 ar fi “namaria”. Acesta va fi copiat incepand cu pozitia 0.

Stergerea ultimului caracter

Reamintim ca prima pozitie din string este 0 si ultima pozitie folosita este N-1 (astfel sunt N pozitii). Atunci, marcatorul de sfasit de cuvant se gaseste pe pozitia N. Stergerea ultimului caracter se face fie memorand marcatorul de sfarsit de string la poz N-1, fie copiind stringul de la adresa S+N la adresa S+N-1.

char s[]="Anamaria"; int N=strlen(s); strcpy(s+N-1,s+N); cout <<s;

sau

char s[]="Anamaria"; int N=strlen(s); s[N-1]=0; cout<<s; //sau s[N-1]=''/n";

Stergerea unui caracter oarecare, din pozitia i

In concordanta cu cele doua exemple anterioare, pentru a sterge elementul de la pozitia I, trebuie sa copiem la adresa S+I stringul care incepe in pozitia I+1.

strcpy(s+i,s+i+1);

Problema.

Fie S un sir de caractere in care sunt spatii inutile ( gen ”      Ana      are      mere    .     “).

  1. Sa se stearga spatiile inutile de la inceput
  2. Sa se stearga spatiile inutile de la sfarsit
  3. Sa se stearga spatiile inutile din interior

Rezolvarea pct 1.

while (s[0]==' ') strcpy(s,s+1); //cat timp primul caracter (s[0]) este spatiu, il sterg

Rezolvarea pct. 2

n=strlen(s); while (s[n-1]==' ') { strcpy(s+n-1, s+n); n--;} //odata cu stegerea ultimului spatiu, actualizez si N, numarul de caractere

O rezolvare a pct. 3

 

 

 

Siruri de caractere

Siruri de caractere (string-uri)

Cu sirurile de caractere ne-am intalnit inca de la intructiunea COUT, cand afisam mesaje de genul “Suma este”, “Valoarea cautata nu exista in sir” etc. Acestea sun exemple de constante sir de caractere. Termenul englezesc pentru sir de caractere este STRING. Daca lucram cu string-uri trebuie sa declaram utilizarea bibliotecii (colectie de functii specializate – amanunte despre aceste functii gasiti si la http://www.cplusplus.com/reference/cstring/ ) :

#include <cstring>

Declarare

char sir[50]; int I,n; //am declarat un string de maxim 50 de caractere

Practic, s-a declarat un vector de caractere.

Citirea unui string

Exista mai multe medode pentru citirea unui string:

  • cin.get(sir, 50); //in variabile SIR se citesc maxim 50 de caractere
  • cin.getline(sir,50); //analog, cu deosebirea ca este “consumat”  si ENTER-ul, acesta nefacand parte din sir
  • cin>>sir; //se memoreaza cuvantul de pana la primul separator – spatiu sau alt semn

Analoge sunt si cazurile pentru citirea din fisier

  • fin.get(sir, 50);
  • fin.getline(sir,50);
  • fin>>sir;

Se poate realiza si o initializare in momentul declararii

  • char vocale [ ] =”aeiou”; //nu s-a stabilit marimea cuvantului
  • char sir[7]=”Ana are mere”; //se memoreaza primele 7 caractere
Evident, exista si cuvantul vid (fara nici un caracter): char vid [] =””; //ghilimele fara nimic intre ele.

Afisarea unui string

cout<<sir;

 Ce se memoreaza de fapt?

Deoarece nu se stie exact cate caractere s-au introdus, imediat dupa ce stringul este memorat in variabila, dupa ultima pozitie este memorat caracter special (netiparibil) ‘/n’.El marcheaza sfarsitul oricarui sir de caractere.
char vocale [ ] ="aeiou";
Caracterele memorate in vocale sunt ‘a’, ‘e’, ‘i’,’o’, ‘u’ si ‘/n’.
Amintim ca sirul nostru de caractere sete un vector si incepe (asa cum cere standardul C) in pozitia 0. Practic vocale[0]=’a’, vocale[1]=’e’,vocale[2]=’i’,vocale[3]=’o’,vocale[4]=’u’ si vocale[5]=’/n’.

Parcurgerea string-ului

Pentru ca numarul de caractere nu este stabilit la citire, putem folosi o functie specifica pentru a determina lungimea string-ului, functia STRLEN (string length). Deoarece primul caracter din cele N se gaseste in pozitia 0, deducem ca ultimul se va gasi in pozitia N-1.
N=strlen(sir); for( I=0;i<N;i++) cout<<sir[I]<<endl; //prelucram sirul, caracter cu caracter

Probleme propuse

Fie o propozitie memorata intr-un sir de caractere SIR
  • cate cifre, litere mici, litere mari si semne speciale sunt in propozitie
  • de cate ori apare caracterul ‘ ‘ (spatiu).
  • Sa se afiseze sirul, dupa ce toate literele mici au fost transformate in litere mari (simularea functiei STRUPR – string upper)
  • Sa se afiseze sirul, dupa ce toate literele mari au fost transformate in litere mici (simularea functiei STRLWR – string lower)
  • Sa se afiseze sirul, dupa ce a fost oglindit (simularea functiei STRREV – string reverse)
 

Tipul caracter

Tipul caracter

Tipul caracter este definit ca fiind un tip intreg, pe 8 biti (adica 1 byte), cu valori de la -128 la 127 (256 de valori distincte).

Cele 256 de caractere existente au fost puse in relatie cu acest tip, fiecarui caracter asociindu-se in mod unic un numar din cele de mai sus. Aceasta asociere se numeste codul ASCII (American Standard Code for Information Interchange ). Caracterele cu coduri intre 0 si 127 formeaza setul de baza iar cele cu coduri de la -128 la -1 (practic de la 128 la 255) formeaza setul extins. Aceasta suprapunere intre multimile 128..255 si -128..-1 se datoreaza faptului ca orice tip de data este circular. Practic, 127+1= -128 si 128-1=127!!! etc.

Caracterele se pot compara intre ele pe baza codului lor asociat.

Declarare

char ch;

Putem lucra cu caracterul atat din punct de vedere al codului ASCII cat si al constantelor tip caracter ( ‘7’, ‘A’, ‘g’ , ‘+’, … ).

ch=65; ch='A';

Citirea

cin>>ch; //se citeste un caracter de la tastatura dar se memoreaza codul sau.

Afisarea

cout<<ch; //se preia din memorie valoarea numerica si se afiseaza caracterul cu codul respectiv

Ce cod are un caracter dat?

Pentru a raspunde la intrebare este nevoie sa facem o conversie de tip

int cod; char ch; cin>>ch; cod= (int) ch; cout<<cod;

Ce caracter ii corespunde unui cod dat?

int cod; char ch; cin>>cod; ch=cod; cout<<ch;

Sa afisam intregul cod ASCII.

int i;for(i=0;i<=255;i++) cout <<"caracterul "<<(char) i<< " are codul " <<i<< endl;

Dupa executarea acestei secvente se pot observa urmatoarele:

  • caracterele cifre au pastreaza ordinea naturala si au codurile : ‘0’=48, ‘1’=49, ‘2’=50,…,’9’=57.
  • caracterele LITERE MARI pastreaza ordinea din alfabet si au codurile: ‘A’=65, ‘B’=66, ‘C’=67, …,’Z’=90
  • caracterele litere mici pastreaza ordinea din alfabet si au codurile: ‘a’=97, ‘b’=98, ‘c’=99, …,’z’=122
Consecintele acestor observatii sunt:
  • daca am un caracter cifra, cum obtin valoarea cifrei? Ma folosesc de faptul ca ordina cifrelor se pastreaza.
  • char cif; int cifra; cin<<cif; cifra=cif-‘0’; cout<<cifra;
  • daca am o cifra, cum o transform in caracterul cifra corespunzator?
  • ch=cifra+’0′;
  • din punct de vedere al codului ASCII (dupa codul lor), LITERELE MARI sunt mai mici decat literele mici
  • intre oricare litera mica si LITERA MARE corespunzatoare este aceeasi diferenta: ‘a’-‘A’=’b’-‘B’=…=’z’-‘Z’=32
  • daca am o litera mica, cum obtin LITERA MARE corespunzatoare?
  • char lm, LM; LM=lm – (‘a’-‘A’);
  • daca am o LITERA MARE, cum obtin  litera mica corespunzatoare?
  • char lm, LM; lm=LM +(‘a’-‘A’);
 

Coada

Coada

Definitie

Coada este o structura la care adaugarea elementelor se realizeaza la sfarsit (PUSH) iar eliminarea unui element se realizeaza de la inceput.

OBS: conform definitiei se pate afirma ca o coada este de tip FIFO (first input, first output = primul venit, primul servit). Evident, modelul unui sir la un ghiseu este cea mai nimerita reprezentare pentru o coada.

Implementare 1

Ca si la stiva, putem folosi vectorul in reprezentarea unei cozi.

Declarare:

int C[100], sc;  //sc este sfarsitul cozii

Coada vida

sc=0; //nu exista nici un element in coada

PUSH – adaugarea unui element (la sfarsit)

sc++; cin>>c[sc]; //facem loc unui noi valori si citim valoarea dorita

POP – eliminarea primului element

Urmand modelul real (al unei cozi la un ghiseu), toate elementele, incepand cu pozitia a 2-a, vor fi mutate la stanga. Coada va avea acum un element in minus.

for(I=2;i<=sc;i++) c[I-1]=c[I];

sc–;

Practic, oricare operatie tip POP este de complexitate N (numarul de elemente din coada), ceea ce este destul de mult. O alternativa ar fi sa nu respectam modelul real, in care se muta cei care stau la rand, ci sa il punem pe functionar sa se miste cu biroul lui.

Avem nevoie de un indice IC care sa arate cine este persoana/elementul din fata functionarului.

Implementare 2

Declarare:

int C[100], sc, ic;  //sc este sfarsitul cozii; ic este inceputul cozii

Coada vida

Initial: sc=0; ic =0//nu exista nici un element in coada

Pe parcurs coada va fi vida cand ic>sc

PUSH – adaugarea unui element (la sfarsit)

if(sc==0) ic++; //marchez inceputul cozii
sc++; cin>>c[sc]; //facem loc unui noi valori si citim valoarea dorita

POP – eliminarea primului element

Eliminarea primului element se reduce la deplasarea inceputului cozii la dreapta.

if(ic<=sc) ic++;

Se observa ca operatia se rezolva intr-un pas, nu in N ca in cazul anterior

 

Ciurul lui Eratostene – sirul numerelor prime

Definitii

  • Un numar se numeste prim daca nu are alti divizori in afara de el si 1.
  • Un numar prim are 2 divizori.
  • Un numar neprim se numeste divizibil.

Problema 1. Sa se determine numerele prime pana la N.

Problema 2. Sa se determine primele N numere prime.

Evident exista si alte probleme ce necesita lucrul cu mai multe valori prime (descompunerea in factori primi, … ).

De aceasta problema, a determinarii primelor numere prime, s-a ocupat si Eratostene, cel care a dat si metoda care ii poarta numele: ciurul lui Eratostene. El a realizat o matrice 10*10 in care a marcat numerele pana la 100. Apoi a luat, pe rand, fiecare valoare (nemarcata) incepand cu 2 si a marcat (sters) multiplii ei. Au ramas nemarcate tocmai numerele prime pentru ca, asa cum spune definitia lor, nu au nici un divizor.

Din punct de vedere al optimizarii procesuli de calcul, putem determina mai usor sirul numerelor prime pana la N decat sa cercetam fiecare valoare in parte daca este prima sau nu.

METODA 1

Daca incercam implementarea algoritmul lui Eratostene (numerele prime pana la 100), rezolvam practic problema 1. Fiecare valoare C[I] din vector va avea valoarea 1 (daca I este prim), respectiv 0 daca I este divizibil.

int C[100], N, I, J;

cin>>N;

for(I=1;I<=N; I++) C[I] =1;

for (I=2;i<=N;I++)

    if(C[I] == 1) // I este prim => multiplii pana la N vor fi zero

         for(J=2;J*I <= N;J ++)  C[I*J] = 0;

//afisarea numerelor prime

for(I=1;I<=N; I++)

    if(C[I] ==1) cout <<I<< “este prim”<<endl;

Gratie vectorului generat, putem afirma intr-un singur pas daca o valoare X este numar prim sau nu: C[X]==1 ?

METODA 2

S-ar putea ca o problema sa doreasca numai numerele prime, ca in cazul descompunerii in factori primi sau a problemei 2.

O metoda de a construi un vector format numai din numere prime (evident in ordine crescatoare) ar putea fi urmatoarea. Algoritmul porneste de la observatia ca daca un numar nu are divizori printre numerele prime mai mici decat el, atunci este un numar prim.

int C[100], NC, I, J;

//2 este primul numar prim

C[1]=2; NC=1; cin >>N;

for(I=3; NC<N; I=I+2) //merg doar pe numere impare

{//caut divizori pentru I

for(J=1;J<=NC && I % C[J]!=0 ;J++);

if(J>NC) //nu s-a gasit divizor=> I este prim si il adaug la sfarsitul vectorului

{NC++; C[NC]=I;}

}

//ies cand NC==N

//afisez primele N numere prime

for(I=1;I<=N;I++) cout<<C[I]<<” “;

 
 

Tags:

 
%d bloggers like this: