INFORMATICA

1. Siruri de caractere.2. Tipul STRUCT3. Recursivitate4. Divide et Impera5. Liste liniare SI

Siruri de caractere O constanta de tip sir de caractere se 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).

Declarari

      char sirc[12] = {’c’, ’l’, ’a’, ’s’, ’a’,' ','a',' ','X','-','A','\0'};   // sirul de caractere “clasa a X-a”

char sc[20];

cin>>sc;// citesc de la tastatura sirul sc;

Pentru citirea unui sir care contine si caractere albe se foloseste metoda:

“cin.get(vector-de-caractere, int nr,char=‘\n’)”

ex: char sc[100];

cin.get(sc, 100, ’\n’)

cout<<sc;

Afisari cout<<sirc<<"\n";  //afiseaza clasa a X-a

cout<<sc0[0];   // afiseaza primul caracter din sirul sc0 – c

cout<<sc1[4];  // afiseaza al patrulea caracter din sirul sc1 – a

sc0[0]=’p’;       // elementului din sir de indice 0 i se atribuie valoarea ‘p’;cout<<sc0<<endln;       // se afiseaza plasa a X-a

 sc0[4]='C'; cout<<sc0<<endln;       // se afiseaza plaCa a X-a

Problema Se citeste un cuvant format din litere mici. Sa se afiseze cuvintele care se

obtin prin eliminarea succesiva a primei si ultimei litere din cuvantul citit. Ex: Daca de citeste cuvantul alina se vor afisa: alina lin i

#include<iostream> int main() { char a[100]; cin>>a; while(strlen(a)>0) {cout<<a; cout<<endl; strcpy(a,a+1); strcpy(a+strlen(a)-1,a+strlen(a)); } return 0; }

Tipul STRUCT O structura este o colectie de valori eterogene, stocate intr-o zona

compacta de memorie.Componentele unei structuri, denumite campuri, sunt identificate prin nume simbolice, denumite selectori.Campurile unei structuri pot fi de orice tip, simplu sau derivat, dar nu void sau functie.

Declararea structurilor se face folosind cuvantul cheie struct:

struct [nume_structura]{  tip1 membrii;  tip2 membrii;................  tipn membrii;}[lista_declaratori]; //variabile de tip structura

Exemplu1:struct persoana{ //se declara tipul struct persoana

    char nume[20];    int varsta;}; //lipseste lista_declaratori

Exemplu2:struct persoana{ //se declara tipul struct persoana

    char nume[20];    struct{      int zi,an,luna    }data_nasterii; //camp de tip structura

PROBLEMA: O firma are un numar de angajati, pentru fiecare pastranduse urmatoarele date: nume,prenume, nr copii,locul nasterii. Folosind structuri introduceti datele apoi afisati datele introduce.

#include<iostream>using namespace std;struct persoana{char nume[20], prenume[20];int nr_copii;double salariu;char loc_nastere[20];}angajati[10];int main(){int n;cout<<"Nr. angajati=";cin>>n;for(int i=1;i<=n;i++){

cout<<"Intruduceti datele pentru angajatul "<<i<<endl;cout<<"Numele :"; cin>>angajati[i].nume;cout<<"Prenumele :"; cin>>angajati[i].prenume;cout<<"Nr. copii:"; cin>> angajati[i].nr_copii;cout<<"Locul nasterii:"; cin>> angajati[i].loc_nastere;}cout<<"Datele introduse au fost:"<<endl;for(int i=1;i<=n;i++){cout<<"Numele "<<i<<angajati[i].nume<< endl;cout<<"Prenumele: "<<i<<angajati[i].prenume<< endl;cout<<"Nr. copii: "<<angajati[i].nr_copii<< endl;cout<<"Locul nasterii: "<<angajati[i].loc_nastere; } }

Pentru ca punctul P sa fie situat pe axa OX, x-ul punctului trebuie sa fie egal cu 0;

P situat pe axa ox <=> P.X==0

RASPUNS: a)

RECURSIVITATE Un proces este recursiv atunci când desfasurarea sa

genereazã aparitia unor procese similare lui, aflate în legaturã cu cel care le-a generat.

Recursivitatea este o tehnicã de elaborare a programelor. Un proces recursiv este finit atunci când încheierea executiei

sale se face dupã un numar determiant de operatii executate.

Prin antiteza cu procesul recursiv finit, procesul recursiv infinit, teoretic, nu îsi incheie executia niciodata.

În general, însa, procesele pe care vrem sã le descriem sunt finite si trebuie sã ne asigurãm ca programele noastre sã reflecte acest lucru.

1. Să se găsească valoarea termenului al n-lea din șirul lui Fibonacci.

F(0)=0; F(1)=1;F(n)=F(n-1)+F(n-2).

#include<iostream>

long int n;

int f(int n)

{

if(n==0) return 0;

else if(n==1) return 1;

                else return f(n-1)+f(n-2);

}

void main()

{

cout<<"n=";cin>>n;

cout<<"f("<<n<<")="<<f(n)<<endl;

}

2.Să se afișeze suma cifrelor dintr-un număr natural citit de la tastatură.

#include<iostream >

long int n;

int s(int n)

{

if(n==0) return 0;

               else return s(n/10)+n%10; 

}

void main()

{

cout<<"n=";cin>>n;

cout<<s(n)<<endl;

}

DIVIDE et IMPERA Ideea de baza consta in impartirea unei probleme in 2 sau

mai multe subprobleme care se rezolva separat, apoi se trece la combinarea rezultatelor problemelor rezolvate obtinandu-se, astfel, solutia finala.

Se da un sir de valori (secventa de valori) a1, a2, a3,…, an. Aceasta secventa trebuie prelucrata.

Prelucrarea se va realize in felul urmator: sirul se imparte in 2 sau mai multe subsiruri. Fiecare subsir se va impartii, dupa aceiasi metoda, in 2 sau mai multe subsiruri pana cand se ajunge la o problema rezolvabila sau un rezultat cunoscut.  Din aproape in aproape, prin combinarea rezultatelor obtinute, se obtine rezultatul final.

Aplicatii Divide et Impera1) Maximul dintr-un vector

Se citeste un vector cu n componente, numere naturale. Se cere să se tipărească valoarea maximă.

Functia căutată va genera valoarea maximă dintre numerele retinute în vector pe o pozitie dintre i si j (initial, i=1, j=n). Pentru aceasta, se procedează astfel: dacă i=j, valoarea maxima va fi v[i];

în caz contrar, se imparte vectorul în doi subvectori - presupunem varianta pentru paralelizare pe 2 procesoare. Se calculează mijlocul m al intervalului [i, j]: m = (i+j) div 2. Primul subvector va contine componentele de la i la m, al doilea va contine componentele de la (m+1) la j; se rezolvă subproblemele (aflându-se astfel maximul pentru fiecare din subvectori), iar solutia curentă va fi dată de valoarea maximă dintre rezultatele celor două subprobleme.

#include <iostream> using namespace std; int v[10],n; int max(int i, int j) { int a, b, m; if (i==j) return v[i]; else { m = (i+j)/2; a = max(i, m); b = max(m+1, j);

if (a>b) return a; else return b; } } int main( ) { cout<<”n=”;cin>>n; for (int i=1; i<=n; i++) { cout<<”v[“<<i<<”]=”; cin>>v[i]; } cout<<”max=”<<max(1,n); return 0; }

2) Căutare binară

Se citeste un vector cu n componente numere întregi (numerele se presupun ordonate crescător) si o valoare întreagă ("nr"). Să se decidă dacă nr se găseste sau nu printre numerele citite, iar în caz afirmativ să se tipărească indicele componentei care contine această valoare.

#include <iostream>

using namespace std;

int v[100], n, nr;

void caut(int i, int j)

{ int m = (i+j)/2;

if (nr==v[m])

cout<<”gasit, indice=”<<m;

else

if (i<j)

if (nr<v[m])

caut(i, m-1); else caut(m+1, j); else cout<<”nu a fost gasit.”; } int main( ) { cout<<”n=”; cin>>n; for (int i=1; i<=n; i++) { cout<<”v[“<<i<<”]=”; cin>>v[i]; } cout<<”nr=”; cin>>nr; caut (1,n); return 0;

3) Turnurile din Hanoi Se dau 3 tije simbolizate prin a,b,c. Pe tija a se gasesc discuri de diametre

diferite, asezate in ordine descrescatoare a diametrelor privite de jos in sus. Se cere sa se mute de pe tija a pe b, utilizand ca tija intermediara tija c, respectand urmatoarele reguli:

la fiecare pas se muta un singur disc ;

nu este permis sa se aseze un disc cu diametrul mai mare peste un disc cu diametrul mai mic.

#include<iostream> using namespace std; char a,b,c; int n; void hanoi(int n,char a,char b, char c) { if(n==1) cout<<a<<b<<" "; else {

hanoi(n-1,a,c,b); cout<<a<<b<<" "; hanoi(n-1,c,b,a); } } int main() { cout<<"n=";cin>>n; hanoi(n,'a','b','c'); }

Liste liniare simplu inlantuie

O lista liniara este o succesiune ordonata de elemente cu proprietatile:- exista primul si ultimul element;- fiecare element, cu exceptia ultimului, are un succesor- fiecare element, cu exceptia primului, are un predecesor

Listele liniare pot fi memorate secvential, intr-un vector, sau inlantuit (cu pointeri).Pentru a reprezenta succesiunea elementelor in cadrul unei liste se folosesc sageticatre succesorul fiecarui element

In cazul alocarii inlantuite a listelor informatia memorata in fiecare element este formata din:- informatia utila (valoarea elementului din lista)- informatia de legatura (adresa urmatorului element)

1. 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; }

2. Într-o stivă ce memorează numere întregi se introduc, în ordine, următoarele numere:

1,2,3,4,5,6,7. Câte numere trebuie să eliminăm din stivă astfel ca în vârful stivei să se găsească numărul 5 (4p.)

a. 5 b. 2 c. 3 d. 4

Din stiva se pot elimina elemente doar de la coada. Ca sa ajungem la ultimul element 5 trebuie sa eliminam numarul 7 precum si numarul 6 de la coada stivei.

=> 2 numere.RASPUNS : b.2

Proiect Informatica

Realizat de:Georgiu Mihai-Andrei Clasa a X-a B C.N.A.M.DEJ-2012