RSS

Category Archives: C2_4 Tehnici si metode de programare

Greedy. Functii recursive. Divide et Impera. Backtraking.

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

 

Stiva

Definitie

Stiva este o structura de date, cu valori de acelasi tip, in care adaugarea (operatia PUSH) si extragerea de elemente (operatia POP) se realizeaza la varf.

Corelare

Cu termenul STIVA ne-am mai intalnit la expresia “stiva de lemne”, insa imaginea sugerata este una lipsita de ordine. Un cuvant care explica mai bine structura stivei, este cuvantul TEANC. Apare clar ideea ca elementele se suprapun unul altuia, in ordine si adaugarea si extragerea se realizeaza la varf.

Similar, putem vorbi de o stiva de tricouri. Stapana casei pune tricourile noi in varful teancului iar noi ne servim, de asemenea, din varf.

Un exemplu de folosire a ideii de stiva este construirea oglinditului unui numar natural. Fie n un numar natural. Sa se creeze numarul n2, numarul oglinda al lui n. (n=1972=> n2=2791). Ideea este de a lua cate o cifra de la sfarsitul lui n (POP) si a o adauga la sfarsitul lui n2 (PUSH). Observam ca atat n , cat si n2, se comporta ca si stive.

n2=0;

do {cif=n%10; //elementul din varful stivei N

    n2=n2*10+cif; // PUSH in N2

   n=n/10; //POP din N

} while (n!=0)  //verific daca stiva  N este vida

cout<<n2;

Implementare

Din punct de vedere al implementarii, pentru reprezentarea in memorie a unei stive, putem folosi vectorul.

Declararea unei stive vide:

int stiva[100], ns=0;   //ns=numarul de elemente din stiva; initial stiva este vida

Operatia PUSH: cresc numarul de elemente; folosesc prima pozitie neocupata;

ns++;cin>>stiva[ns];

Operatia POP: daca exista elemente in stiva, elimin elementul din varf (practic  nu sterg elementul, ci doar il ignor)

if (ns>0) ns–;

Concluzie

La o stiva operatiile de adaugare (PUSH) si extragere (POP) se realizeaza la varf. In literatura de specialitate gasiti afirmatia ca o stiva este de tip LIFO (last input, first output = ultimul venit este primul plecat; … asemanator cu  politica de angajare a unei firme/institutii )

 

 

Tags:

Metoda Greedy – problema rucsacului

#include <fstream>
using namespace std;

ifstream fin (“date.in”);
ofstream fout(“date.out”);

int main ()
{//declarare
int pret[10], vol[10],i,n,sac,vfurt=0,aux, sch;
//citire
fin>>sac;
fin>>n;
for(i=0;i<n;i++)
fin>>vol[i]>>pret[i];
//GREEDY
//faza 1: hotul ordoneaza obiectele descrescator, dupa raportul pret/volum
do{
sch=0;
for(i=0;i<n-1;i++)
it (pret[i]/vol[i]<pret[i+1]/vol[i+1])
{sch=1;
aux=pret[i];pret[i]=pret[i+1];pret[i+1]=aux;
aux=vol[i];vol[i]=vol[i+1];vol[i+1]=aux;
}
} while (sch);
//faza 2: hotul pune obiectele in sac
for(i=0;i<n && sac>0;i++)
if (sac>=vol[i])
{sac=sac-vol[i];
vfurt=vfurt+pret[i];
}
//afisare
fout<<endl<<“In sac a ramas “<<sac<<” spatiu.”<<endl<<“Valoarea furtului este “<<vfurt;
return 1;
}

 

Metoda Greedy – problema salariului

#include <fstream>
using namespace std;

ifstream fin(“date.in”);
ofstream fout(“date.out”);

int main ()
{//declarari
int salar, b[10], i,n,c[10], nrmon=0, csalar, sol=0;
//citire
fin>>salar;csalar=salar;
fin>>n;
for(i=0;i<n;i++)
fin>>b[i];
//greedy
for(i=0;i<n;i++)
{c[i]=salar/b[i];
nrmon=nrmon+c[i];
salar=salar%b[i];
};
//afisare
fout<<endl<<csalar<<” ? “;
for(i=0;i<n;i++)
{if (i!=0) fout<<“+”;
fout<<c[i]<<“*”<<b[i];
sol=sol+c[i]*b[i];
}
fout<<“=”<<sol<<endl<<“Nr. de mon folosite:”<<nrmon;
if (salar==0) fout<<endl<<“Salariul a fost achitat integral.”;
else fout<<endl<<“Salariul NU a fost achitat integral.”;
return 1;
}

 
 
%d bloggers like this: