Proiect la informatica

21
Made by Catalin &Raul Proiect la informatica

description

Proiect la informatica. Made by Catalin &Raul. Cuprins. Siruri de caractere TIPURI DE DATE DEFINITE DE UTILIZATOR Recursivitate/subprograme Divide et impera Liste liniare Grile Probleme. Siruri de caractere. - PowerPoint PPT Presentation

Transcript of Proiect la informatica

Page 1: Proiect la informatica

Made by Catalin &Raul

Proiect la informatica

Page 2: Proiect la informatica

Cuprins

• Siruri de caractere• TIPURI DE DATE • DEFINITE DE UTILIZATOR

• Recursivitate/subprograme• Divide et impera• Liste liniare• Grile• Probleme

Page 3: Proiect la informatica

Siruri de caractere

• O constanta de tip sir de caractere de declara intre doua caractere “. In memoria interna, o constanta de acest tip este retinuta sub forma unui vector de caractere. Fiecare componenta a sirului (incepand cu cea de indice 0) retine codul ASCII al caracterului pe care il memoreaza. Conventia este ca ultimul octet sa retina 0 (codul caracterului nul). Caracterul nul este memorat automat. Trebuie rezervate lungimea_sirului+1 caractere char (+1 pentru caracterul nul).

• Limbajul C/C++ permite initializarea unui tablou de caractere printr-o constanta sir, care include automat caracterul null.

• Exemplu :• char vect[11]=”calculator”;• char vect[]=”calculator”; (compilatorul face calculul numarului de octeti necesari)• char vect[100]=”calculator”; (s-au rezervat mai multi octeti decat era necesar)• • Sirurile de caractere sunt de fapt tablouri de caractere, care au ca ultim element un

terminator de sir, caracterul null.

Page 4: Proiect la informatica

FUNCTII PENTRU OPERATII CU SIRURI DE CARACTERE

• • Functiile pentru operatii cu siruri se gasesc in header-ul <string.h>.• Ø Functia strlen

int strlen(nume_sir); – returneaza lungimea efectiva a unui sir (fara a numara terminatorul de sir)

• Ø Functia strcpy strcpy(sir_destinatie,sir_sursa); – copiaza sirul sir_ sursa in sir_destinatie (se simuleaza atribuirea a=b).

ATENTIE!! Nu este permisa atribuirea intre doua siruri de caractere folosind operatorul =. Atribuirea se face folosind functia strcpy.

• Ø Functia strcat strcat(dest,sursa); – adauga sirului dest sirul sursa. Sirul sursa ramane nemodificat. Operatia se numeste concatenare si nu este comutativa.

• Ø Functia strncat strncat(dest,sursa,nr); – adauga dest primele nr caractere din sirul sursa. Sirul sursa ramane nemodificat.

• Ø Functia strchr strchr(sir,c); – are rolul de a cauta caracterul c in sirul sir. Cautarea se face de la stanga la dreapta, iar functia intoarce adresa subsirului care incepe cu prima aparitie a caracterului c. Daca nu este gasit caracterul, functia returneaza 0. Diferenta dintre adresa sirului initial si cea a subsirului returnat reprezinta chiar pozitia caracterului cautat in sirul dat.

• Ø Functia strrchr strrchr(sir,c); – are acelasi rol cu strchr, cu deosebirea ca returneaza adresa ultimei aparitii a caracterului (cautarea se face de la dreapta spre stanga; r = right)

• Ø Functia strcmp int strcmp(sir1,sir2); – are rolul de a compara doua siruri de caractere. Valoarea returnata este <0 (daca sir1<sir2), =0 (daca sir1=sir2) si >0 (daca sir1>sir2). Functia strcmp face distinctie intre literele mari si cele mici ale alfabetului.Obs: Functia strcmp returneaza diferenta dintre codurile ASCII ale primelor caractere care nu coincid

• Ø Functia stricmp int stricmp(sir1,sir2); – are acelasi rol cu strcmp, cu deosebirea ca nu face distinctie intre literele mari si cele mici ale alfabetului (i = ignore)

• Ø Functia strstr strstr(sir1,sir2); – are rolul de a identifica daca sirul sir2 este subsir al sirului sir1. Daca este, functia returneaza adresa de inceput a subsirului sir2 in sirul sir1, altfel returneaza adresa 0. In cazul in care sir2 apare de mai multe ori in sir1, se returneaza adresa de inceput a primei aparitii. Cautarea se face de la stanga la dreapta

• Ø Functia strtok strtok(sir1,sir2); – are rolul de a separa sirul sir1 in mai multe siruri (cuvinte) separate intre ele prin unul sau mai multe caractere cu rol de separator. Sirul sir2 este alcatuit din unul sau mai multe caractere cu rol de separator.Functia strtok actioneaza in felul urmator:

• o Primul apel trebuie sa fie de forma strtok(sir1,sir2); Functia intoarce adresa primului caracter al primei entitati. Dupa prima entitate, separatorul este inlocuit automat prin caracterul nul.

• o Urmatoarele apeluri sunt de forma strtok(NULL,sir2); De fiecare data, functia intoarce adresa de inceput a urmatoarei entitati, adaugand automat dupa ea caracterul nul.

• o Cand sirul nu mai contine entitati, functia returneaza adresa nula.

Page 5: Proiect la informatica

• Se citesc de la tastatura 2 siruri de caractere. Sa se compare cele doua siruri.• #include<iostream.h>

#include<string.h>

char s1[100],s2[100];

void main()

{ int x;

x=stricmp(s1,s2);

if(x>0) cout<<"Primul sir este mai mare ";

else if(x==0) cout<<"Siruri sunt egale";

else cout<<"Al doilea sir este mai mare decat primul "; }

Sir de caractere

Page 6: Proiect la informatica

Sir de caractere• Se citeste un sir de caractere care nu contine caractere albe.Sa se

verifice daca sirul este alcatuit exclusiv din caractere numerice.

• #include<iostream.h>#include<string.h>void main(){char cuvant[100],cifre[]="0123456789";cout<<"cuvant:";cin>>cuvant;if(strspn(cuvant,cifre)==strlen(cuvant)) cout<<"numeric";else cout<<"nenumeric";}

Page 7: Proiect la informatica

TIPURI DE DATE DEFINITE DE UTILIZATOR

• Limbajele de programare de nivel înalt oferã utilizatorului facilit ãþi de a • prelucra atât datele singulare (izolate), cât ºi pe cele grupate (tablourile).

Datele predefinite ºi• tablourile nu sunt însã suficiente. Informaþia prelucratã în programe este

organizatã, în• general în ansambluri de date, de diferite tipuri. Pentru a putea descrie aceste

ansambluri• (structuri) de date, limbajele de programare de nivel înalt permit

programatorului sã-ºi• defineascã propriile tipuri de date. • Aceste tipuri de date sunt structuri de date neomogene care ne permit

urmãtoarele• gruparea unor obiecte (date) de tipuri diferite, referite printr-un nume comun. • Exemplificând, dacã dorim sã prelucrãm date referitoare la mai mulþi elevi,

pentru• fiecare elev trebuie sã cunoaºtem: • Numele – char[20]• Prenumele – char[20]• Nota matematicã - float• Nota informaticã – float • În C++ existã un t ip de date, numit struct, care permite ca fiecãrui elev sã-i• corespundã o singurã înregistrare. • Forma generalã este:• struct [nume structura]• { • [<tip> <nume variabila [, nume variabila, ……]>];• [<tip> <nume variabila [, nume variabila, ……]>];• …• } [lista de variabile];

• Existã douã posibilitãþi de declarare a variabilelor care alcãtuiesc structura:

• 1. Scriind la sfârºit numele variabilelor: • struct elev • { char nume[20], prenume[20];• float nota_mate, nota_info;• int varsta;• } inr1,inr2;

• 2. Declarând variabilele aºa cum suntem obiºnuiþi:

• elev inr1, inr2;

• Definiþia structurii poate fi fãcutã:• În cadrul funcþiei main()• Înaintea funcþiei main() (caz recomandat)

Page 8: Proiect la informatica

Tipul Struct• struct nod fint inf; nod *adr ;g;

• //declararea functiilor de creare, parcurgere, eliminare si inserare• nod *creare(void);• void parcurge(nod *prim);• nod *elimina(nod *prim, int info);• nod *inserare dupa(nod* prim, int info, int info1);• //functia principala• /***********************************************/• void main(void) f• int info, info1; nod *cap;• cap=creare();• parcurge(cap);• cout<<Spuneti ce nod se elimina;• cin>>info;• cap= elimina(cap, info);• parcurge(cap);• cout<<Spuneti ce valoare se insereaza si dupa cine<<endl;• cin>>info1;• cin>>info;• inserare dupa(cap,info,info1);• parcurge(cap);g• //functia de creare a listei• /********************************************/• nod *creare(void)• f nod *prim,*p,*q; int inf; char a;• //crearea primului element al listei• prim=new nod;• cout<< Introduceti prim->inf<<endl;• cin>>inf;• prim->inf=inf;• prim->adr=NULL;• q=prim;• /*pana cand se decide ca operatia este gata, se creaza elementele urmatoare*/• cout<<Gata?[d/n]<<endl;• cin>>a;• while (a!='d') f• p=new nod;

Page 9: Proiect la informatica

Recursivitatea• Un algoritm se numește recursiv dacă se autoapelează adică, dacă în corpul său există un modul care se autoapeleză. Recursivitatea se

realizează cu ajutorul subprogramelor. Un subprogram care se autoapelează se numește subprogram recursiv. • Prin urmare un algortim se numește recursiv sau un program se numește recursiv dacă conține cel puțin un subprogram care se

autoapelează.• Recursivitatea se realizează în felul următor:• - Din afara subprogramului facem un apel al subprogramului• - Dacă nu este îndeplinită o condiție (numită condiție de oprire), algoritmul se autoapelează de un anumit număr de ori (până

când e îndeplinită condiția). La fiecare nouă autoapelare a subprogramului se reexecută secvența de instrucțiuni din corpul său, eventual cu alte date, creându-se un lanț de autoapeluri recursive. Dacă condiția de oprire nu este îndeplinită niciodată sau nu există, algoritmul va avea un rezultat asemănător intrării într-un ciclu infinit.

• Intuitiv, putem spune că un algoritm recursiv are același efect ca și o buclă (ciclu, instrucțiune repetitivă) – repetă execția unui set de instrucțiuni. În mod analog, deducem că repetarea nu trebuie să se realizeze de un număr infinit de ori. De aici provine necesitatea existenței condiției de oprire.

• Prin urmare orice subprogram recursiv trebuie să îndeplinească următoarele condiții:• - să se poată executa cel puțin o dată fără a se autoapela (când apare condiția de oprire);• - toate autoapelurile să se producă astfel încât la un moment dat să se ajungă la îndeplinirea condiției de oprire.• Cea mai mare parte a algoritmilor repetitivi se pot implementa într-o variantă nerecursivă (numită variantă iterativă) folosind

instrucțiuni recursive, cât și într-o variantă recursivă atunci când conțin un modul definit recursiv.• Varianta de implementare rămâne la latitudinea programatorului.• Varianta recursivă este recomandată în cazul în care problemele sunt definite printr-o relație de recurență însă acest timp de algoritmi

sunt mai greu de urmărit și de obicei necesită un timp de execuție mai mare.

Page 10: Proiect la informatica

Probleme

Recursivitate• Sa se afle cmmdc pentru 2 numere utilizand

varianta recursiva• #include<iostream.h>

int a,b;• int cmmdc(int a,int b)

{if(a==b) return a;elseif (a>b) return cmmdc(a-b,b);else return cmmdc(a,b-a);}

• void main(){cout<<"a=";cin>>a;cout<<"b=";cin>>b;cout<<"cmmdc: "<<cmmdc(a,b);}

Subprogram• Subprogramul Nr are un singur parametru, k, prin intermediul căruia

primeşte un număr natural de cel puţin 3 cifre şi cel mult 9 cifre, cu toate cifrele nenule. Subprogramul furnizează tot prin intermediul parametrului k, valoarea obţinută prin eliminarea primei cifre a numărului transmis la apel.Exemplu: dacă subprogramul primeşte prin intermediul parametrului k valoarea 12438, atunci în urma apelului subprogramului Nr, k va primi valoarea 2438.

• #include<iostream.h>void nr(int &k){int n,o;n=k;o=0;while(n>9){o=o*10+n%10;n=n/10;}k=0;while(o!=0){k=k*10+o%10;o=o/10;}}void main(){int k;cin>>k;nr(k);cout<<k;

Page 11: Proiect la informatica

Divide et impera• Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe

subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

• Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

• Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: "ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

• s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;

• nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Page 12: Proiect la informatica

Divide et impera

Sa se calculeze folosind metoda divide et impera suma elementelor unui vector• #include<iostream.h>

int v[20],n;int suma(int li,int ls) {int m, d1 ,d2;  if(li!=ls)                 {m=(li+ls)/2;      d1=suma(li,m);        d2=suma(m+1,ls);       return d1+d2;       }  else      return v[li]; }      void main()  {             cout<<"n=";  cin>>n;      for(int i=1;i<=n;i++)    {cout<<"v["<<i<<"]=";    cin>>v[i];} cout<<"suma celor "<<n<<" elemente ale vectorului "<<suma(1,n);}

Page 13: Proiect la informatica

Liste liniare

• O lista liniara simplu inlantuita are nodul format din doua componente principale: o parte statica, ce contine informatia utila si o parte dinamica, ce contine adresa nodului urmator din lista. Ultimul nod al listei are in partea dinamica valoarea NULL deoarece dupa acesta nu mai este inlantuit niciun alt nod.

Ca modalitate de implementare, putem definii un tip de date inregistrare in care partea dinamica va fi pointer catre acelasi tip, pentru a retine adresa nodului urmator si va fi numita in continuare "adr" iar partea statica va fi numita "info".

Crearea unei liste liniare simplu inlantuite

Pentru a crea o lista simplu inlantuita se parcurg urmatoarele etape:- Se creeaza primul nod, p;- Se creeaza celelalte noduri din lista prin legarea acestora pe rand de ultimul nod creat.Crearea nodului p presupune: alocarea spatiului de memorie pentru acesta (1), citirea informatiei utile (2), legarea nodului nou creat de lsta preexistenta (3). In cazul primului nod, legatura se face cu nodul NULL.Celelalte noduri se creaza in acelasi mod, avand grija la modul in care se fac legaturile dintre acestea cu lista (se leaga de ultimul nod creat (4) si apoi noul nod devine ultimul din lista (5)).

Page 14: Proiect la informatica

Liste liniareExemplu

• Urmatorul program ofera o modalitate de creare si afisare a unei liste liniare simplu inlantuite care prelucreaza numere intregi:

• #include<iostream.h>• #include<conio.h>• struct nod• {int info;• nod *next;};• nod *p,*u ; // acceseaza primul respective ultimul nod• int n; //numarul de noduri• void cre_ad() //functia de creare si adaugare a unui

nou element• {nod *c;• if(!p) //daca lista este vida (p==0) se aloca primul

nod• {p=new nod;• cout<<"valoare primului nod ";• cin>>p->info;• u=p; //la creare primul si ultimul nod vor fi identici• }• else//altfel se adauga un nou element la sfarsit

• { c=new nod; //se aloca un nou nod• cout<<"informatia utila :";• cin>>c->info; //se completeaza campul informatie utila• u->next=c; //se adauga dupa ultimul nod • u=c; //se stabileste noul nod c ca fiind

ultimul• }• u->next=0; //campul adresa urmatoare a

ultimului nod este 0• }• void afis() //functia de afisare parcurge elementele cu afisare• {nod *c;• c=p; //se porneste de la primul nod din

lista• while(c) //cat timp c retine o adresa nenula• {cout<<c->info<<" ";//se afiseza campul informatie utila• c=c->next;} //se avanseaza la urmatoarea

adresa, la urmatorul nod• cout<<endl;• }• void main()• {clrscr();• int b;• cout<<"n=";• cin>>n;• for(int i=1;i<=n;i++)• cre_ad( );• cout<<endl;• afis();• getch();• }

Page 15: Proiect la informatica

Lista liniara

• Scrieti o functie care primeste ca parametru primul nod al unei liste liniare simplu inlantuite si elibereaza zona de memorie ocupata de lista.

• void stergere(nod *&prim) { nod *p; while(prim) {p=prim;

• prim=prim->leg; • delete p; { }

Page 16: Proiect la informatica

Lista liniara• Sa se scrie o functie care

primeste ca parametru adresa primului nod al unei LLSI cu cel putin 3 noduri si sterge primul si ultimul nod al listei.

• void stergpu( nod *&prim) { nod*p,*q; q=prim;

• prim=prim->leg;• delete q;• p=prim; while(p->leg->leg

!=0) p=p->leg;• q=p->leg;• p->leg=0;• delete q; }

Page 17: Proiect la informatica

Grile

• .Scrieţi un program C/C++ care citeşte de la tastatura un număr natural n (2<n<21) si apoi n linii cu cate n numere întregi de cel mult 7 cifre ce formează un tablou bidimensional a. Sa se afişeze pe ecran diferenţa dintre suma elementelor de pe diagonala principala si suma elementelor de pe diagonala secundara a matricei a.

• #include<iostream.h>void main()

• {int n,i,j;long a[20][20],s1=0,s2=0,d;cout<<"n=";cin>>n;for(i=1;i<=n;i++){for(j=1;j<=n;j++){cout<<"a["<<i<<"]["<<j<<"]=";cin>>a[i][j];}}for(i=1;i<=n;i++){for(j=1;j<=n;j++)if(i==j)s1=s1+a[i][j];};for(i=1;i<=n;i++){for(j=1;j<=n;j++)if(i+j==n+1)s2=s2+a[i][j];}cout<<s1-s2;}

• Scrieţi programul C/C++ care citeşte de la tastatura un număr natural n (n<100) si un sir cu n numere întregi din intervalul [100 ;999] ; programul construieşte un sir de numere rezultat prin înlocuirea fiecărui număr din şirul citit cu numărul obţinut prin interschimbarea cifrei unitatilor cu cifra sutelor. Numerele din noul sir se vor afişa pe ecran separate printr-un singur spaţiu. De exemplu , pentru n=3 si şirul 123 , 904 , 500 , se afişează 321 , 409 , 5.

• #include<iostream.h>void main(){int n,i,o,v[20],c;cout<<"n=";cin>>n;for(i=1;i<=n;i++){cout<<"v["<<i<<"]=";cin>>v[i];}for(i=1;i<=n;i++){o=0;c=v[i]%10;o=o*10+c;v[i]=v[i]/10;c=v[i]%10;o=o*10+c;v[i]=v[i]/10;o=o*10+v[i];v[i]=o;cout<<v[i]<<endl;}}

Page 18: Proiect la informatica

• Doua tablouri unidimensionale a si b , cu elementele a1 , a2 , … , an , respectiv b1 , b2 , … bn sunt in relaţia a<=b daca : a1<=b1 , a2<=b2 , … , an<=bn. Scrieţi program in limbajul C/C++ care citeşte doua tablouri unidimensionale a si b cu acelaşi număr de elemente de tip întreg si verifica daca a<=b sau b<=a afişând un mesaj adecvat.

• #include<iostream.h>void main(){int a[10],i,n,j,k,aux,min;cout<<"n=";cin>>n;for(i=1;i<=n;i++){cout<<"a["<<i<<"]=";cin>>a[i];}for(i=1;i<=n-1;i++){min=a[i];k=i;for(j=i+1;j<=n;j++)if(a[j]<min){min=a[j];k=j;}aux=a[k];a[k]=a[i];a[i]=aux;}for(i=1;i<=n;i++)cout<<a[i]<<" ";}

• Scrieţi un program in limbajul C/C++ care afişează toate numerele naturale formate din cifre identice , mai mari decât 10 si mai mici decât o valoare data n, n<=2.000.000. De exemplu pentru n=195 , se afişează : 11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 , 99 , 111.

• #include<iostream.h>int n,i;int identic(int n){int d,c;c=n%10;while (n>0){d=n%10;if(d==c)n=n/10;elsereturn 0;}if(n==0)return 1;}void main(){cout<<"n=";cin>>n;for (i=10;i<=n;i++){if(identic(i))cout<<i<<endl;}}

Page 19: Proiect la informatica

• Scrieţi un program C/C++ care citeşte de la tastatura trei numere naturale x, y si k, (1<x<y<2000000, k<1000) si afişează pe ecran k numere prime din intervalul [x, y]. Daca nu exista k numere prime în intervalul [x,y] se vor afişa toate numerele prime găsite iar pe linia următoare se va afişa mesajul “s-au găsit mai puţine numere prime: ” urmat de numărul acestora. De exemplu, pentru x=3, y=12 si k=5 se vor afişa pe ecran:3 5 7 11 s-au găsit mai puţine numere prime:4

• #include<iostream.h>void main(){int x,y,k,n,d,a,p;cout<<"x=";cin>>x;cout<<"y=";cin>>y;cout<<"k=";cin>>k;a=0;n=x;while ((n>=x)&&(n<=y)&&(a<k) ){d=2;p=1;while((d<=n/2)&&(p==1))if(n%d==0)p=0;elsed++;if(p){cout<<n<<endl;a++;}n++;}if(a<k)cout<<"au fost gasite mai putine nr prime"<<a;}

Page 20: Proiect la informatica
Page 21: Proiect la informatica

Un proiect realizat prin munca obositoare si aproape nesfarsita a urmatorilor colaboranti:Ropan Catalin & Rostas Raul & Titoc Cristian