C++ Modulul 2

_________________________________________

Lecția 1. Șiruri de caractere

Un șir de caractere este o succesiune de caractere cuprinsă între două ghilimele și poate să conțină orice caractere: litere mari și mici, caractere speciale (#, $, &, etc), delimitatori, cifrele de la 0 la 9 (ca elemente de text, nu ca numere).

Exemplu:

"Programare în limbajul C++"

În C++, un șir de caractere poate fi definit ca un vector de caractere, în două moduri:

char <identificator>[dimensiune maximă]; //declară un vector de tip caracter
char *<identificator>; //declară un pointer către tipul caracter.

Exemple:

char s[30];
char *s;

Într-un șir de caractere se poate memora o valoare atât prin citire, cât și prin atribuire.
Numărul de caractere ale șirului se numește lungimea șirului sau dimensiunea efectivă. Această dimensiune nu coincide neapărat cu dimensiunea alocată de compilator ca efect a declarației șirului.

Caracterele succesive din șir au un număr de ordine, începând cu primul care are indicele 0. Deci dacă șirul s este "Programare", primul caracter este s[0]='P'.

În urma operației de citire, după ultimul caracter citit compilatorul scrie întotdeauna un caracter special 0 binar, sau NULL. Acest caracter este marcherul de sfârșit de șir. Deci dacă se citește șirul "C++" de la tastatură, caracterele succesive vor fi: s[0]='C', s[1]='+', s[2]='+', s[3]=0. Deci un șir cu lungimea n caractere se memorează pe n+1 celule de memorie consecutive. Fiecare caracter în C++ se memorează pe un octet.

Atenție la sintaxă: 'C' înseamnă caracterul C, el este o variabilă de tip char și se memorează pe un octet. "C" este un șir de caractere de lungime 1 și se memorează pe 1+1 = 2 octeți.

Parcurgerea pe caractere a unui șir.

Pentru a afla lungimea unui șir de caractere putem folosi funcția strlen(), care este încorporată în executabil la momentul compilării, cu condiția să avem directiva

                                       #include <string.h>

Caracterul NULL aflat după ultimul caracter din șir nu este luat în considerare la calcului lungimii șirului de către funcția strlen. Dacă șirul s="Marilyn Manson", vom avea strlen(s)=14.

Aplicație:

Se citește un șir de maxim 200 de caractere. Să se elimine succesiv (în mai multe parcurgeri ale șirului) toate succesiunile de caractere identice. Algoritmul se oprește când nu mai există succesiuni de caractere identice.
Exemplu: abcccbssssbklm ....... abbbklm .... aklm

Indicații:

citeste sirul in variabila char sir[100], folosim doi pointeri: j merge inaintea lui i cand se intalnesc caractere identice iar i sta pe loc; daca j intalneste caractere diferite, sir[i] primeste valoarea din sir[j].

O soluție:

#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <string.h>
using namespace std;
bool repeta=true,rep=false;
int i=0,j=0;
int n;
char sir[100];
char lit;
int main()
{
    cout<<endl<<"baga sirul ";
    gets(sir);
    n=strlen(sir);
    cout<<"n="<<n;
    while(repeta)
    {
        repeta=false;
        while(j<=n)
        {
            lit=sir[j];
            if(lit==sir[j+1])
            {
                do
                {
                    j++;
                }
                while(lit==sir[j]);
                repeta=true;
            }
            sir[i]=sir[j];
            i++;
            j++;
        }
        n=i-1;
        i=0;
        j=0;
    }
    cout<<endl<<n<<" sirul compactat ";
    for(i=0;i<=n-1;i++)cout<<sir[i];
}

Aplicații la parcurgerea șirurilor:

1. Se citeste de la tastaura un sir de max 200 caractere conținând litere, cifre și spații.

a. sterge spatiile inutile din text
b. inlocuiste scventele de coduri ASCII cu literele corespunzătoare;
c. afiseaza numarul de subsiruri formate numai din litere;
d. sterge din sir toate cuvintele care au cel putin un caracter care nu este litera.

2. Gaseste cea mai lunga secventa de caractere dintr-un sir care este palindrom

/* gaseste cea mai lunga secventa de caractere dintr-un sir
care este palindrom

se citeste sirul in variabila char sir[100]
se initializeaza variabilele int start=1 si int lg=0
intr-un ciclu de la i=1 la n reprezentand pozitia de start a unui subsir
pentru fiecare i se executa un alt ciclu pentru l=2 la n-i reprezentand lungimea unui sir
se verifica daca subsirul care incepe din pozitia i pe lungime de l caractere este palindrom
daca este, se compara l cu variabila lg, iar daca l>lg atunci se retine i si l in start si lg.
la final se afiseza subsirul.
*/
#include <iostream>
#include <fstream>
using namespace std;
char sir[100];
fstream f("f.txt",ios::in);
int n,i,start,lg=0,l;
bool palindrom(int,int);
int main()
{
    i=1;
    while(f>>sir[i])i++;
    n=i;
    for(i=1;i<=n-1;i++)
        for(l=1;l<=n-i;l++)
            if(palindrom(i,l))
            {
                if(l+1>lg)
                {
                    start=i;
                    lg=l;
                }
            }
    if(lg>1)
        for(i=start;i<=lg+1;i++)cout<<sir[i];
}
bool palindrom(int s,int p)
{
    bool ret=true;
    for(int i=0;i<=p;i++)
        if(sir[s+i]!=sir[s+p-i])ret=false;
    return ret;
}

________________________________________________________________________________

Lecția 2. Funcții pentru șiruri de caractere din biblioteca standard <string.h>

strcpy, strncpy, strcmp, strncmp

Copiere

Pentru copierea în întregime a unui sir (care poate fi uneori o parte din alt sir, cum se va vedea în aplicația următoare) în altă locație, este nevoie sa cunoastem adresa lui de început, (respectiv indicele primului caracter al subsirului dacă este vorba de un subșir). Functia strcpy întoarce o adresă de șir care este tocmai adresa șirului destinație, cea furnizată de noi în primul parametru.

char * strcpy ( char * destinatie,  char * sir_sursa );

Funcția copiază caracter cu caracter și se oprește când întâlnește caracterul NULL,
pe care îl copiază și pe el la sfârșitul șirului destinație.

Atenție: dacă șirul sursă depășește mărimea rezervată pentru șirul destinație, funcția poate da erori necontrolabile, deoarece suprascrie date din vecinătate.

Pentru copierea unui număr precizat de caractere dintr-un șir în altă locație, folosim funcția strncpy.
Aceasta are un parametru suplimentar, lungimea subșirului de copiat:

char * strncpy ( char * destinație,  char * sursă, număr_de_caractere );

Comparare

Pentru a compara două șiruri, aflate la adresele str1 și str2, folosim funcția strcmp:

int strcmp (  char * str1,  char * str2 );

Această funcție întoarce un retur de tip număr întreg, a cărui valoare nu ne interesează, decât dacă este 0, pozitiv sau negativ. Dacă returul funcției este 0, șirurile sunt egale. Dacă este negativ, primul caracter care diferă are un cod ASCII mai mic în str1 decât în str2, iar dacă este pozitiv, este mai mic cel din str2.

Similar cu cazul funcției strncpy, avem și aici o funcție care copară o porțiune de lungime dată din două șiruri: strncmp.

int strncmp (  char * str1,  char * str2, număr_de_caractere );

Aplicație:

Sa se gaseasca perioada minima si sirul care se repeta in cuvintele din fisierul cuvinte.in (maxim 100 de cuvinte).
Lungimea unui cuvant este de maxim 1000 caractere. Datele de iesire se scriu in fisierul cuvinte.out sub forma perioada minima spatiu subsirul care se repeta.

Analiza problemei

1. Se va citi cate un cuvant din fisierul de intrare pana se atinge sfarsitul de fisier. Cuvântul citit se depozitează in variabila char cuvant.
2. Calculam lungimea cuvantului.
3. Initializam variabila intreaga perioada cu 1.
4. Initializam variabila booleana amgasit cu false
5. cat timp perioada este mai mica decat lungimea si nu amgasit:
    5.1 incrementăm perioada
    5.2 dacă lungimea se divide cu perioada
           5.2.1 am gasit = true (am gasit un divizor)

5.2.2 copiem subsirul de inceput din cuvant de lungime = perioada in subsir, si îl bordăm cu un caracter NULL;

5.2.3 într-un ciclu cu număr de repetări = numărul de repetări ale perioadei în lungime, comparăm fragmente succesive din cuvânt de lungime perioada cu subșir. Dacă cel puțin unul din fragmente este diferit decât subșir, amgasit devine fals.

5.3.4 dacă din ciclul anterior se iese cu amgasit = true, rezultă că am găsit o perioadă care se repetă. Afișăm perioada și subșir.

Întrebare: de ce soluția afișată este cea mai mică perioadă care se repetă?

Date de lucru:
cuvant de tip char[1000]
lungime = lungimea cuvantului, intreg
perioada întreg
repetari întreg = de câte ori se cuprinde perioada în lungime
subsir[1000] vector de caractere = șir de caractere
amgasit boolean

#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
fstream fin("cuvinte.in",ios::in);
fstream fout("cuvinte.out",ios::out);
char cuvant[1000];
int lungime;
int perioada;
char subsir[1000];
bool amgasit;
int main()
{
    while(fin>>cuvant)
    {
        lungime=strlen(cuvant);
        perioada=1;
        amgasit=false;
        while(perioada<=lungime&&!amgasit)
        {
            perioada++;
            if((lungime)%perioada==0)
            {
                //un divizor. caut repetarea subsirului de lungime perioada in cuvant
                amgasit=true;
                int start=0;
                int repetari=(lungime)/perioada;
                strncpy(subsir,cuvant,perioada);
                subsir[perioada]=NULL;
                for(start=0;start<=repetari-1;start++)
                {
                    if(strncmp(cuvant+(start*perioada),cuvant,perioada))
                    {
                        amgasit=false;
                    }
                }
                if(amgasit)
                {
                    fout<<perioada<<" "<<subsir<<endl;
                    cout<<perioada<<" "<<subsir<<endl;
                }
            }
        }

    }
}

Aplicații

1. Se citește de la tastatură o frază conținând atât litere mari cât și litere mici. Să se transforme toate literele mari în litere mici și apoi să se reafișeze fraza.
Indicație: literele mici au codurile ASCII cuprinse între a=97 și z=122, în timp ce literele mari au codurile de la A=65 la Z=90. Întotdeauna diferența dintre codul literei mici și codul literei mari este 'a'-'A'=97-65=32. Pentru a transforma literele mari în litere mici, trebuie să adăugăm 32 la codul literei mari. Atenție: trebuie mai întâi să ne asigurăm că este vorba de o literă mare, adică are codul cuprins între 'A' și 'Z'.

2. Se citesc de la tastatură numele a șase elevi. După fiecare nume introdus, dacă este unul dintre următorii: Victor, Andrei și Maria se afișează "tenis", iar dacă este vorba despre Eugen, Rodica și Luiza se afișează "baschet". Fiecare nume se va afișa pe o linie nouă. Dacă se introduc alte nume, se va afișa "informatică".

Test / 06.10.2016

_____________________________________

Lecția 3. Alocarea dinamică a memoriei. Variabile de tip pointer.

1. Pointeri

Memoria internă este din punct de vedere logic o succesiune continuă de octeți. Pentru a-i distinge, aceștia sunt numerotați. Numărul de ordine al unui octet este adresa lui. Orice variabilă de memorie ocupă un număr consecutiv de octeți. Adresa primului octet al variabilei se numește adresa variabilei.

Nu trebuie confundată valoarea variabilei cu adresa ei.

În loc de adresa variabilei, vom folosi termenul pointer.
Un pointer este o variabilă care memorează adresa altei variabile. Facem distincție între pointeri după natura variabilelor referite de ei: există pointeri care conțin adrese de întregi, care sunt diferiți de pointerii care conțin adrese de caractere, sau de pointerii către variabile de tip float. Tipul unei variabile pointer face deci referire la tipul variabilelor asociate. Un pointer se declară astfel:

tip *nume;

Exemple: pointeri către variabile de tip int:

int *adr1, *adr2;

pointeri către variabile de tip float:

float *adr3;

Observații: - Caracterul * poate fi așezat în mai multe feluri:

int* adr1;

int *adr1;

int * adr1;

- Dacă avem mai mulți pointeri de declarat pe aceeași linie, caracterul * se trece de fiecare dată:

int *adr1, *adr2, *adr3;

- Dacă scriem

int *adr1, adr2;

înseamnă că adr1 este pointer către întreg, iar adr2 este întreg.

Legătura dintre pointer și variabila referită.

Pointerul nu trebuie confundat cu variabila referită. Între un pointer și o variabilă referită se realizează o asociere:

pointer ---------------------> variabilă referită

Un pointer poate să nu conțină la un moment dat nici o adresă. Dacă avem la începutul programului declarația:

int * adr_variabila_intreaga;

compilatorul rezervă spațiu pentru variabila de tip pointer cu numele adr_variabila_intreaga. Care este atunci variabila referită? În acest moment nu există. Abia după ce atribuim o valoare pointerului, putem spune care este variabila referită. Putem atribui pointerului adr_variabila_intreaga adresa oricărei variabile întregi dorim. Pentru a afla adresa unei variabile existente, folosim operatorul & numit și operator de referențiere:

int a=7;

*adr_variabila_intreaga = &a;

cout <<*adr_variabila_intreaga;

Acest exemplu ne demonstrează un aspect extrem de important: numele variabilei a și adresarea cu operatorul * prin intermediul pointerului sunt sinonime. Cele două modalități de adresare pot fi folosite întotdeauna una în locul celeilalte.

a este sinonim cu *adr_variabila_intreaga

De ce preferăm totuși să folosim adresarea cu pointeri, în loc de adresarea normală?

Suntem nevoiți să folosim adresarea cu pointeri atunci când nu cunoaștem numele variabilei, ci numai adresa ei. Cu alte cuvinte, variabila este cunoscută numai prin adresa ei, nu și prin nume. Acest lucru se întâmplă atunci când utilizăm alocarea dinamică a memoriei. Pointerii sunt totuși foarte utili și în lucrul cu variabile alocate static, după cum vom vedea ulterior, la studiul listelor și structurilor.

2. Alocarea dinamică

Memoria calculatorului este gestionată de către sistemul de operare Windows. S.O. alocă inițial fiecărei aplicații încărcate în memorie o cantitate de memorie fixă, cerută de aplicație. Aplicația cunoaște ce cantitate de memorie îi este necesară, potrivit numărului și dimensiunii variabilelor statice definite de programator. Această zonă statică de memorie se numește STIVA PROGRAM.

Uneori însă aplicația poate dezvolta un număr necunoscut de variabile de memorie, ceea ce face ca necesarul de memorie să nu poată fi estimat. Metoda de a se aloca un spațiu acoperitor nu este productivă, deoarece conduce la programe de dimensiuni excesiv de mari, care cu toate acestea e posibil să nu încapă în memorie la un moment dat și să se genereze o eroare.

Pentru rezolvarea situației se folosește alocarea de memorie numai la nevoie, într-o zonă exterioară aplicației, numită HEAP. Variabilele se alocă aici la momentul execuției (spre deosebire de variabilele alocate static, care primesc o adresă chiar la momentul compilării). Variabilele alocate dinamic sunt desființate de către S.O. îndată ce nu mai este nevoie de ele. Sistemul de operare gestionează alocarea lor, iar adresa lor efectivă este comunicată modulului apelant.

Pentru a aloca dinamic o variabilă avem nevoie de un pointer către acea variabilă și de operatorul new:

int*p;

p=new int; aici p este un pointer către o variabilă de tipul int.

putem scrie legat:

int*p=new int;

S.O. întoarce în pointerul p doar adresa unde a creat variabila de tipul int, fără să îi știm efectiv numnele. Accesul la acea variabilă se va face numai prin intermediul operatorului *:

*p=25;

cout<<*p;

Durata de viață a unei variabile alocate dinamic în HEAP este până la distrugerea ei de către operatorul delete sau până la terminarea programului:

delete p;

Foarte important: după această operație, pointerul p continuă să existe ca variabilă alocată static, dar conținutul referit de el dispare, nu mai este accesibil. Pointerul p poate primi altă valoare oricând.

Atenție: pointerii sunt variabile alocate static.

Pointeri către tablouri (vectori, matrici, șiruri de caractere).

Numele unui vector este prin definiție un pointer către elementul 0 al vectorului. Asta înseamnă că dacă vectorul V conține elemente de tip caracter, fiind declarat astfel:

char V[50];

iar valoarea lui V este șirul de caractere "toamna se numără bobocii",

expresia V[0] este sinonimă cu expresia *V, iar valoarea acestei expresii este caracterul 'T'; V[1] este sinonim cu *(V+1), având valoarea 'o', etc.

similar, dacă vectorul T conține numere întregi, fiind declarat astfel:

int T[3]={3, 33, 333};

atunci T[0] = * T = 3, T[1]=*(T+1) = 33, etc.

Un tablou q-dimensional se declară astfel: tip nume_tablou[n1][n2]...[nq]

exemplu: int dimens[2][3]; declară un tablou cu 2 dimensiuni: 2 linii și 3 coloane (o matrice).

Dacă avem elementele matricii dimens de felul următor, pe linii: {{5,7,10},{0,8,4}}, numele dimens este pointer către elementul dimens[0]={5,7,10}. Expresia *dimens este deci echivalentă cu expresia dimens[0] și valoarea ei este masivul 1-dimensional (vectorul) {5,7,10}.

Numele unui tablou q-dimensional este pointer către primul element al primei dimensiuni a masivului. Atenție: primul element al primei dimensiuni nu este de data asta un scalar (un element izolat) ci un masiv cu q-1 elemente!

Un pointer către un tablou k-dimensional este o variabilă alocată static și se declară astfel:

tip (*nume)[n1][n2]...[nk];

Exemplui: float (*var)[4][3];

Alocarea dinamică a masivelor (vectori, matrici, șiruri de caractere).

Deoarece numele unui masiv q-dimensional este pointer către un masiv q-1-dimensional, pentru a aloca dinamic un masiv q-dimensional, se va utiliza un pointer q-1-dimensional.

Exemple:

1. Alocăm dinamic în HEAP un vector cu 4 componente de tip int. Numele unui astfel de vector are tipul int* (pointer către int). După alocare, pointerul int*p va conține adresa elementului 0 al vectorului. Din acest moment, pornind de la p, vectorul se accesează exact ca de obicei:

int* p=new int[4]; // a se observa că numele masivului a fost eliminat din declarație, iar operatorul [] se aplică asupra tipului, nu asupra numelui vectorului.

p[3]=2;

Operații cu pointeri

Adunarea unui pointer cu o constantă dă naștere unui nou pointer care adresează o locație de memorie decalată cu valoarea adunată.
Scăderea a doi pointeri are ca rezultat o valoare numerică întreagă care este egală cu distanța de memorie care separă cele două adrese.

Test grilă rezolvat

Ce va afișa programul următor?

#include <iostream>
using namespace std;
int main()
{
   char *a[3]={"abc", "def", "ghi"};
   char *p=&a[0][0];
   cout<<a[1]<<" "<<a[2][1]<<" "<<*(p+5);
}

a) abc d NULL
b) abc d e
c) def h NULL
d) def h e
e) programul conține erori de compilare.

Rezolvare:

- Declarația char *a[3] declară un pointer către un tablou 2-dimensional, respectiv un vector de șiruri. Fiecare element al vectorului este un șir, adică un vector. Un vector de vectori este un tablou 2-dimensional.
- Declarația char *p=&a[0][0] declară un pointer către caracter. Acest pointer este inițializat cu adresa elementului a[0][0].
- a[1] este un șir, este al doilea element al tabloului *a[3] (primul este a[0]). Valoarea acestui șir este "def".
- a[2][1] este un element scalar (un caracter individual), este al doilea element al celui de al treilea șir. Numărătoarea elementelor unui vector începe cu 0. Valoarea lui este

abcdefghi

-*(p+5) este un caracter a cărui adresă se obține adunând 5 la valoarea lui p. Elementele tabloului sunt concatenate în ordinea definirii lor, iar la sfârșitul fiecărui șir se adaugă un octet suplimentar, NULL. Deci fiecare șir ocupă 4 octeți. *(p)='a', *(p+1)='b', *(p+2)='c', *(p+3)=NULL, *(p+4)='d', *(p+5)='e'.

abcdefghi

Deci răspunsul este d).

EXERCIȚII

1. Ce se afișează în urma executării programului următor?

#include <iostream>
using namespace std;
int main()
{
     float *a1, *a2;
     a1=new float;
     *a1=3;
     a2=new float;
     *a2=4;
     a2=a1;
     cout<<*a2;
}

Indicații: a1, a2 = pointeri; *a1, *a2 = întregi; a2=a1 este o atribuire de pointeri (deci atribuire de adrese, nu de valori).

2. ce se afișează în urma executării programului următor, dacă se citesc valorile 7 și 8?

#include <iostream>
using namespace std;
int main()
{ int *a1, *a2, *man;
   a1=new int; cin>>*a1;
   a2=new int; cin *a2;
   man=a2;
   a2=a1;
   a1=man;
   cout<<*a1<<" "<<*a2;
}

Lecția 4. Structuri de date neomogene

Tablourile (vectorii și matricile) sunt structuri de date care memorează componente de același fel. Există însă anumite situații care necesită prelucrarea unor entități conținând componente de natură eterogenă. De exemplu, despre un angajat trebuie să reținem numele (șir de caractere), adresa (șir de caractere), salariul (număr întreg). Dacă avem un singur angajat, toate aceste informații se pot menține sub forma unor date independente. Dacă avem însă un număr mare de angajați, este convenabil să construim un vector de angajați, iar toate informațiile subordonate angajatului (nume, adresă, CNP, salariu, etc) să poată fi legate direct de angajatul respectiv. Soluția oferită de limbajul C++ este definirea unei structuri.

O structură este un tip de date definit de programator, cu ajutorul cuvântului cheie struct și cu respectarea următoarei sintaxe:

struct nume_structură
{
tip_componenta_1 nume_componenta_1;
tip_componenta_2 nume_componenta_2;
..............................................................
tip_componenta_n nume_componenta_n;
};

Exemplu: definirea unei structuri numita elev:

struct elev
{
char nume[20], prenume[20];
char clasa[5];
float media_info;
};

După ce am definit structura elev, putem declara oricâte variabile de tip elev, după metoda obișnuită:

elev elev1, elev2; // se declară variabilele elev1 și elev2 de tipul elev.

Asignarea unui nume pentru un tip de structură

Directiva typedef permite asignarea unui alias (a unui nume intern alternativ) pentru un tip oarecare de date. Exemplu:

typedef int intreg; // de aici inainte vom putea să decalaram variabilele de tip intreg cu declarația

intreg nume_variabila; //echivalent cu int nume_variabila.

Rescriem definiția structurii elev, utilizând directiva typedef:

typedef struct
{
char nume[20], prenume[20];
char clasa[5];
float media_info;
}elev;

Accesul la câmpurile unei structuri

Componentele structurii vor putea fi accesate atât pentru scriere/modificare, cât și pentru citire, cu ajutorul operatorului punct (.): nume_structură.nume_componenta, ca în exemplele următoare:

cin>>elev.nume;
cout<<elev.nume;
elev.media_info=8.5;
cout<<elev.media_info;

Inițializarea unei structuri

Valorile inițiale ale componentelor se enumeră între acolade, separate prin virgule:

nume_structura nume_variabila_structura = {val1,val2, ... valn}

Exemplu:

elev ionescu={"Ionescu", "Dan", "XI C", 7.28}

Câmpuri de tip structură

Un câmp al unei structuri poate fi de orice tip, inclusiv tot o structură.
De exemplu, vom defini o structură de tip data calendaristică:

typedef struct
{
int ziua;
char luna[3] ;
int anul;
}data_calend;

Modificam structura elev, astfel:

typedef struct
{
char nume[20], prenume[20];
data_calend data_nasterii;
char clasa[5];
float media_info;
}elev;

Pointeri către structuri

La fel ca pentru oricare tip de date, și către structuri se pot crea pointeri:

nume_structura * nume_pointer_catre_structura;

exemplu:

elev * pelev; //pelev este un pointer către o variabila de tip elev, care va fi atribuită în viitor pointerului printr-o instrucțiune de genul
pelev=&ionescu;

Accesarea membrilor (componentelor) structurii prin intermediul pointerului

Dacă pelev este pointer către variabila ionescu de tip elev, atunci datele membru ale acestei variabile se vor accesa astfel:

(*pelev).nume sau, cu o notație echivalentă, pelev->nume;

(*pelev).prenume sau echivalent pelev->prenume, etc.

Câmpurile unei structuri se accesează prin intermediul operatorului de adresare -> care este sinonim cu operatorul * și punct.

Atribuiri între structuri

Atribuirea directă între două structuri are ca efect atribuirea individuală între toate câmpurile corespondente. Dacă ionescu este o variabilă de tip elev și e1 este o variabilă de tip elev, atunci
e1=ionescu; are ca efect atribuirea compusă e1.nume=ionescu.nume, e1.prenume=ionescu.prenume, etc.

Vectori de tip structură

Putem organiza mai multe variabile aparținând aceluiași tip de structură în vectori. Dacă e1, e2, ... en sunt variabile de tip elev, putem construi cu ele un vector în felul următor:

elev velev[30]; // acesta este un vector de elemente tip elev, cu numele velev. accesul la elementul cu indicele 7 se face așa: velev[7]. Accesul la datele membru ale elementului cu indicele 7 se face așa: velev[7].nume, vele[7].prenume, etc.

Aplicații

1. Definește o structură pentru evidența cărților dintr-o bibliotecă, știind că pentru fiecare carte trebuie memorate titlul, autorul și anul apariției.

2. Definește o structură care să memoreze n perechi de numere naturale de forma (x,y). Scrie un program care citește cele n perechi din fișierul "perechi.txt" apoi afișează acele perechi care care au proprietatea că al doilea element al perechii este oglinditul (inversul) primului, ca de pildă (243, 342).
Fișierul perechi.txt conține pe prima linie numărul de perechi n, apoi pe următoarele n linii câte o pereche de numere despărțite printr-un spațiu.

3. Să se descompună un număr în factori primi, memorând rezultatul într-un vector cu elemente de tip structură; fiecare element al vectorului va conține două câmpuri, primul indicând factorul prim, iar cel de al doilea puterea la care apare în descompunere.

4. De la tastatură se introduce o frază cu lungime maximă de 80 de caractere. fraza este alcătuită din cuvinte separate printr-unul sau mai multe spații. Nu se folosesc alți separatori între cuvinte. Să se afișeze cuvintele distincte ale frazei și frecvențele lor. Pe fiecare rând se va scrie un cuvânt împreună cu frecvența sa.

Lecția 5. Descompunerea în factori primi utilizând un vector de structuri

#include <iostream>
#include <conio.h>
using namespace std;
typedef struct
{
    int factor; //valoare factor prim
    int putere; //puterea factorului prim
}descfp;
descfp V[20]; //vectorul de structuri
int k; //numarul de descompus
int indfp=-1; // indicele curent in vector
bool prim(int w) //functie care decide daca un numar este prim;
{   // w = parametru formal
    bool codretur=true; //variabila locala
    for(int i=2;i<=w/2;i++)
        if(w%i==0)codretur=false; //daca w nu este numar prim codret <- fals
    if(w==2)codretur=true;
    return codretur;
}
int main()
{
    cout<<"introdu numarul: ";
    cin>>k;
    for(int i=2;i<=k&&k>0;i++)
    {
        if(prim(i)&&k%i==0) //daca i este prim si il divide pe k
        {
            indfp++; //incrementare indice vector V
            V[indfp].factor=i; //memorare factor prim in celula corespunzatoare
            int p=0; //initializare putere factor prim
            while(k%i==0&&k>0) //cat timp k se mai divide la i
            {
                k/=i; //se imparte k la i si k primeste valoarea catului impartirii
                p++; //incrementare putere factor prim
            }
            // acum p contine puterea la care figureaza factorul prim i in descompunere
            // se memoreaza in vectorul V in locatia corespunzatoare
            V[indfp].putere=p;
        }
    }
    // in acest moment indfp contine numarul de factori primi -1
    //afisare vector incepand cu pozitia 0 pana la pozitia indfp
    for(int i=0;i<=indfp;i++)
        cout<<endl<<V[i].factor<<"^"<<V[i].putere;
    getch();
}

Lecția 6. Descompunerea în factori primi utilizând liste înlănțuite alocate dinamic

Crearea și parcurgerea unei liste înlănțuite alocate dinamic

Figura de mai sus ilustrează modul de creare și de parcurgere a unei liste înlănțuite alocate dinamic. O listă este o succesiune de elemente numite atomi sau noduri care conțin atât informație utilă cât și informație de legătură către atomul următor (și uneori și către cel precedent, în cazul listelor dublu-înlănțuite).

În alocarea dinamică a unei liste se folosește un pointer de start către primul atom al listei. Dacă lista este vidă, pointerul de start conține 0 (NULL). Dacă există cel puțin un nod în listă, pointerul de start conține adresa ultimului atom adăugat. Procedând în acest mod, adăugarea a încă unui nod după cel existent se face în 3 pași: 1)se creează cu new noul nod, 2) nodul nou creat preia informația de legătură către nodul anterior chiar din nodul start,3) nodul start se actualizează cu adresa noului atom adăugat în listă.

Parcurgerea de la cap la coadă a listei se face cu un algoritm secvențial din aproape în aproape, până se întâlnește un nod care conține 0 (NULL) în informația de legătură. Acesta este ultimul nod din listă.

Față de algoritmul anterior, cu reprezentare prin vectori de structuri, în acest algoritm structura descfp conține un element în plus, de tipul pointer către atomul următor (precedent).

#include <iostream>
#include <conio.h>
using namespace std;
typedef struct descfp
{
    int factor; //valoare factor prim
    int putere; //puterea factorului prim
    descfp* urmator;
}descfp;
descfp* baza=NULL; //inceputul listei
descfp* pointer;
int k; //numarul de descompus
bool prim(int w) //functie care decide daca un numar este prim;
{   // w = parametru formal
    bool codretur=true; //variabila locala
    for(int i=2;i<=w/2;i++)
        if(w%i==0)codretur=false; //daca w nu este numar prim codret <- fals
    if(w==2)codretur=true;
    return codretur;
}
int main()
{
    cout<<"introdu numarul: ";
    cin>>k;
    for(int i=2;i<=k&&k>0;i++)
    {
        if(prim(i)&&k%i==0) //daca i este prim si il divide pe k
        {
            pointer=new descfp;
            pointer->factor=i; //memorare factor prim in celula corespunzatoare
            pointer->urmator=baza;
            int p=0; //initializare putere factor prim
            while(k%i==0&&k>0) //cat timp k se mai divide la i
            {
                k/=i; //se imparte k la i si k primeste valoarea catului impartirii
                p++; //incrementare putere factor prim
            }
            // acum p contine puterea la care figureaza factorul prim i in descompunere
            // se memorează în atomul referit de pointer în locația corespunzătoare
            pointer->putere=p;
            //se actualizează pointerul baza cu adresa ultimului nod introdus in lista
            baza=pointer; //baza și pointer referă același atom, ultimul întrodus
        }
    }
    // in acest moment atât baza cât și pointer contin adresa ultimei celule din lista
    //afisare lista in ordine inversa
    while(pointer!=NULL)
    {
        cout<<endl<<pointer->factor<<"^"<<pointer->putere;
        pointer=pointer->urmator;
    }
    getch();
}

Lecția 7. Liste: inserarea și ștergerea nodurilor

Marele avantaj al listelor înlănțuite este faptul că operațiile de inserare a unor noduri noi și de ștergere a unor noduri existente nu necesită deplasări și compactări de zone de memorie, ca în cazul vectorilor. Atomii unei liste alocate dinamic se elimină din listă simplu, "scurtcircuitând" informația de legătură către ei. Similar, un atom nou se inserează între doi atomi consecutivi, prin ruperea legăturii de la precedentul și redirectarea ei către atomul nou introdus, care va prelua la rândul lui referința către atomul succesiv.

Dezavantajul listelor înlănțuite este consumul mai mare de memorie decât al unui vector, din cauză că se folosesc acești pointeri de legătură. Acest dezavantaj este contrabalansat de avantajul alocării dinamice (mai eficientă decât cea statică, deoarece se consumă exact atâta memorie câtă este necesară) și de simplitatea algoritmilor de inserare și ștergere.

Deci vom prefera reprezentarea datelor sub formă de liste înlănțuite alocate dinamic atunci când problema noastră solicită foarte multe prelucrări de genul inserări/ ștergeri, dar vom prefera vectorii atunci când datele, odată scrise în memorie, se mențin neschimbate ca ordine.

Exemplificăm prin crearea la început a unei liste de numere întregi introduse de la tastatură (se introduc mai multe numere, terminate prin 0). Se va șterge un număr aflat pe o poziție k, apoi se va introduce alt număr pe o poziție p, unde k și p sunt numere intregi introduse de la tastatură. Pentru verificare, se va reafișa lista după fiecare modificare, utilizând o funcție fără parametri și fără tip de retur (cu tipul void) - afisare_lista().

Inserarea și ștergerea cu doi pointeri:

Operațiile de ștergere și inserare în listă sunt diferențiate după cazul k=primul element (numărul 1) sau nu. Avem nevoie de doi pointeri, care referă două noduri succesive: q= cel pe care îl ștergem și p = predecesorul lui, în cazul ștergerii, sau cele două noduri succesive (p și q) între care inserăm un element nou, în cazul inserării.
Dacă lucrăm asupra elementului nr. 1, atunci rolul pointerului p este luat de pointerul start.

#include <iostream>
using namespace std;
typedef struct atom
{
    int numar;
    atom* ptr;
}atom;
atom* start=NULL,*nodnou;
void afisare_lista()
{
    cout<<endl;
    atom* p=start; //initializam variabila de tip pointer care va adresa elementele listei
    while(p) //echivalent: while(p!=NULL) sau while (p!=0)
    {
        cout<<p->numar<<" ";
        p=p->ptr;
    }
}
int main()
{
    int k;
    do
    {
        cout<<endl<<"un numar: ";
        cin>>k;
        if(k>0)
        {
            nodnou=new atom; //se aloca dinamic un atom nou
            nodnou->numar=k;   // se memoreaza numarul introdus
            nodnou->ptr=start; //legatura catre nodul precedent se preia din start
            start=nodnou; //start va referi noul nod
        }
    }while(k>0);
    //procesul de creare a listei s-a terminat
    //urmeaza afisarea listei
    afisare_lista();
    //stergerea unui nod
    cout<<endl<<"introdu numarul de ordine al nodului care se va sterge: ";
    cin>>k;
    atom *p=start; //pointer de manevra
    if(k==1)
    {
        //p refera catre elementul de sters
        start=start->ptr; //scurcircuitare elementul nr. 1
        delete p; //eliberarea spatiului de memorie
    }
    else
    {
        int i=2;
        atom*q=p->ptr; //la prima iteratie, p->nodul 1 si q->nodul 2
        while(i<k)
        {
            p=q; //p si q refera ambele nodul i
            q=q->ptr; //acum, p refera nodul i, q refera nodul i+1
            i++; //in urma incrementarii lui i, p refera nodul i-1, q refera nodul i
        }
        //in acest moment, q refera al k-lea nod, care trebie sters, p refera nodul k-1
        //se scurcircuiteaza nodul k
        p->ptr=q->ptr; //deci in loc de q, acum p refera nodul q->ptr, succesoryul lui q
        //se elibereaza spatiul
        delete q;
    }
    //reafisarea listei
    afisare_lista();
    //inserare
    cout<<endl<<"introdu numarul de ordine al nodului dupa care se va insera (0 pentru inceputul listei): ";
    cin>>k;
    int ins;
    cout<<endl<<"introdu numarul de inserat: ";
    nodnou=new atom;
    cin>>nodnou->numar;
    if(k==0)
    {
        nodnou->ptr=start; //preia referinta nodului urmator din start
        start=nodnou; //nodnou devine cap de lista
    }
    else
    {
        int i=2;
        atom*p=start, *q=p->ptr; //initial, p refera elem 1, q refera elem 2
        while(i<=k)
        {
            p=q;
            q=q->ptr;
            i++;
        }
        //acum p refera elem nr. i, q refera elem. nr. i+1
        p->ptr=nodnou;
        nodnou->ptr=q;
    }
    afisare_lista();
}

Inserarea și ștergerea cu un singur pointer:

Putem efectua operația de inserare după nodul cu numărul k mai simplu astfel, utilizând un singur pointer pentru deplasarea în listă și un pointer suplimentar de manevră. Dacă nodul start este pointer către începutul listei, vom parcurge lista cu ajutorul pointerului p, care primește la început o copie a lui start.

p=start;

se face apoi într-un ciclu for cu număr cunoscut de pași saltul peste k noduri:

for(int i=2;i<=k;i++) p=p->link;)

se creează noul nod și se înscrie informația în el:

nod* nodnou=new nod;
cout<<endl<<"info="; cin>>nodnou->info;

Se fac legăturile între nod și listă:

nodnou->link=p->link;
p->link=nodnou;

Ștergerea nodului cu numărul de ordine k:
facem o copie p a nodului de start

p=start;

mutăm pointerul p la nodul k-1
for(int i=2;i<=k-1;i++) p=p->link;)
creăm un pointer de manevră q, care va reține adresa nodului k:

nod* r=p->link;

scurtcricuităm nodul r

p->link=r->link;

desființare nodul k:

delete r;

Lecția 8. Aplicații cu liste rezolvate cu ajutorul funcțiilor

Despre funcții

Funcțiile în C++ sunt blocuri de program separate de programul principal main(), care pot fi apelate din interiorul funcției main(). În cadrul unei funcții avem următoarele elemente: antetul, sau semnătura, unde se specifică tipul de retur, numele funcției și lista parametrilor formali (cu nume și tip) separați prin virgule și cuprinși între paranteze, pe de o parte, și corpul funcției cuprins între acolade, pe de altă parte. Pot exista funcții care întorc o valoare de un anumit tip, și atunci este obligatorie existența instrucțiunii return în corpul funcției (cu excepția funcției main() ), și funcții care nu întorc nicio valoare, și atunci nu trebuie să existe instrucțiunea return. Funcțiile care nu întorc valoare de retur au tipul void. Pot exista funcții fără nici un parametru. Fucțiile trebuie definite înainte de a fi apelate, adică trebuie să existe măcar antetul funcției înainte de funcția main().
Parametrii formali ai unei funcții sunt nume (identificatori) având un tip bine stabilit, pe care funcția le înlocuiește la apel cu valorile actuale, concrete, care pot diferi de la un apel la altul.
Parametrii actuali sunt acele valori concrete care sunt transmise unei funcții la momentul apelului efectiv, și care vor înlocui (la momentul execuției) parametrii formali. Numărul și poziția parametrilor actuali din paranteze trebuie să coincidă exact cu numărul și poziția parametrilor formali din lista.
În momentul întâlnirii unui apel de funcție, procesorul suspendă (întrerupe) fluxul normal de instrucțiuni ale programului și cedează controlul corpului funcției. Controlul revine la linia următoare de program la întâlnirea instrucțiunii return, sau la atingerea sfârșitului funcției.
Dacă funcția întoarce o valoare prin return, aceasta înlocuiește numele funcției în expresia în care este întâlnită.

Dacă lista nod* L este descrisă de structura

typedef struct nod
{int info; nod* link;}nod;

putem scrie o funcție fără parametri formali care realizerază crearea listei și întoarce ca rezultat un pointer către listă:

nod* creare()
{
    nod* prim = new nod, *nou;
    int i, n;
    cout<<endl<<"n="; cin>>n;
    prim=NULL;
    for(i=1;i<=n;i++)
{
        nou=new nod;
        cout<<"cheia din nodul "<<i<<": "; cin>>nou- >info;
        nou->link=prim;
        prim=nou;
}
return prim;
}

Deasemenea putem scrie o funcție cu un parametru de tip referință nod și fără tip de retur, care realizează afișarea listei:

void afisare(nod* p)
{
   while(p)
    {
        cout<<p->info<<" ";
        p=p->link;
    }
}

Utilizarea (apelul) funcțiilor:

int main()
{
    nod* L=creare(); // apelul unei funcții cu tip de retur este înglobat într-o expresie de atribuire

    afisare(L); // apelul unei funcții fără tip de retur nu este înglobat într-o atribuire.

}

Aplicații.
1. Căutarea unui nod cu o anumită informație (căutarea unei chei).
Să se scrie un program care verifică dacă într-o listă înlănțuită de numere întregi există un nod cu o anumită valoare introdusă de la tastatură.   Se va scrie o funcție care întoarce tipul bool (adevărat dacă există, fals dacă nu există) și primește doi parametri: adresa nodului de start și valoarea de căutat.

2. Minimul și maximul dintre elementele unei liste
Să se scrie un program care afișează valorile minime și maxime existente într-o listă de numere întregi. Se vor scrie două funcții, minim și maxim, cu un tip de retur întreg și un parametru de tip pointer nod).

3. Suma valorilor dintr-o listă cu elemente numerice
Să se scrie un program care calculează suma elementelor dintr-o listă de numere întregi. Funcția va avea un parametru de tip pointer nod și va întoarce un număr întreg.

4. Reuniunea a două liste este o listă care conține toate elementele a două liste luate o singură dată. Exemplu: reuniunea listelor L1=(2->4->8->9), L2=(2->7->8->11->13) este L3=(2->4->7->8->9->11->13).
Să se scrie un program care reunește două liste, fără a se folosi tablouri sau alte elemente ajutătoare alocate static. Se va considera că L1 și L2 conțin elementele sortate crescător. Funcția întoarce o valoare de tip pointer către noua listă și are doi parametri de tip pointer către cele două liste.

5. Reuniunea a două liste nesortate. Să se rezolve problema de la pct. 4, în ipoteza că listele L1 și L2 nu sunt sortate. Doi parametri tip pointer nod, retur un pointer nod.

6. Intersecția a două liste este o listă care conține elementele comune ale celor două liste. Să se realizeze un program care creează intersecția a două liste de numere întregi. Doi parametri pointeri nod, tip de retur pointer nod.

7. Se citește de la tastatură un șir de maxim 80 de caractere. Să se creeze o listă liniară înlănțuită în care fiecare nod va avea ca informație un caracter al șirului. Să se afișeze apoi lista creată.

8. Scrieți o funcție care verifică dacă o listă de numere conține elementele sortate crecător. Scrieți apoi un apel către funcție.

9. Scrieți o funcție care numără câte apariții ale unei valori date există într-o listă de numere.
Scrieți apoi un apel către funcție.

10. Scrieți o funcție care afișează numărul elementelor negative, nule și pozitive dintr-o listă de numere.
Scrieți apoi un apel către funcție.

11. Scrieți o funcție care decide dacă două liste sunt identice (același număr de noduri și aceleași informații în noduri).

12. Să se scrie o funcție care returnează un pointer către elementul cu numărul k.

13. Să se scrie o funcție care sortează crescător elementele unei liste prin interschimbări directe, fără a modifica legăturile. Funcția utilizează apeluri către funcția creată la punctul 12.

14. Scrieți un subprogram care concatenează (lipește) două liste

15. Se citește de la tastatură un număr întreg de maxim 8 cifre. Să se afișeze oglinditul său folosind memorarea cifrelor într-o listă.

TEST 20.10.2016

Subiectul 1:
Alexandru Octavian, Andronic Vlad Ștefan, Ardelean Remus, Bâtcă Radu, Bogoi Ionuț, Busuioc Andrei Laurențiu, Cautiș Laura Elena

Subiectul 2:
Chirilă Nicu, Cojocaru Florin Dragoș, Constantinescu Raul Ionuț, Cosor Andrei, Dinu Cătălin, Dinu Claudiu, Dârdală Nicoleta

Subiectul 3:
Gurea Vlad Nicolae, Marian Răzvan, Marin Simona Cristiana, Moldoveanu Cristina, Nan Crina Florina, Palade Gabriel, Penghis Anca Daniela

Subiectul 4:
Pomană Alexandru Radu, Radu Florin Cornel, Rotaru Emilian Teodor, Stoica Roxana Bianca, Tănase Nița, Țoca Dragoș Ionuț

Lecția 9. Subprograme

Un program are o structură modulară. Un caz particular de modul îl constituie subprogramele. În C++, subprogramele se numesc funcții. Să luăm cazul unui program care calculează media a două numere, pe care îl vom scrie în 4 variante:

1. Fără funcție

#include <iostream>

using namespace std;

float M, x, y;

void main()

{

cout<<"dați numerele:\n";

cin>>x >>y;

M=(x+y)/2;

cout<<"Media="<<M;

}

Vom scrie acum același program, structurat în două module: un program principal și o funcție. Acest mod de a scrie programul ține seama de funcționalitatea modulelor. Există mai multe variante de a scrie această funcție:

2. Funcție fără parametri și fără valoare returnată (cu variabile globale)

#include <iostream>

float M,x,y;

void calcul_media()

{

M=(x+y)/2; //M, x și y sunt variabile globale, vizibile în interiorul funcției

cout<<"Media="<<M;

}

void main()

{

cout<<"dați numerele:\n";

cin>>x >>y;

calcul_media();

}

3. Funcție cu parametri și fără valoare returnată

#include <iostream>

float M,x,y; //M global, x și y transmiși prin valoare

void calcul_media(float u, float v) //u și v parametri formali

{

M=(u+v)/2;

cout<<"Media="<<M;

}

void main()

{

cout<<"dați numerele:\n";

cin>>x >>y;

calcul_media(x,y); //x și y parametri actuali

}

La apel, valorile parametrilor actuali înlocuiesc parametrii formali în operațiile efectuate în corpul funcției calcul_media.

4. Funcție cu parametri și valoare returnată

#include <iostream>

float M,x,y; //M global, x și y transmiși prin valoare

float calcul_media(float u, float v) //u și v parametri formali

{

float media=(u+v)/2; //media este variabilă locală, invizibilă în exteriorul funcției

return media;

}

void main()

{

cout<<"dați numerele:\n";

cin>>x >>y;

M=calcul_media(x,y);//x și y parametri actuali

cout<<M;

}

Într-un program putem avea o variabilă globală și una locală cu același nume, fără a se crea confuzie: variabila locală o ascunde pe cea globală, adică în cadrul funcției este vizibilă numai variabila locală, iar în rest este vizibilă numai cea globală. Evident, celelalte variabile globale, care nu sunt dublate de variabile locale sinonime, sunt vizibile în cadrul funcției.

Parametri transmiși prin valoare

Putem apela o funcție de mai multe ori, cu date diferite, atât constante cât și variabile. Valorile parametrilor actuali înlocuiesc de fiecare dată în calcule parametrii formali. Adresa parametrilor actuali nu este transmisă funcției. De aceea funcția nu poate modifica partametrii actuali în locația lor reală, deoarece nu le cunoaște adresa, ea primește doar o copie a valorii lor.

int calcul_suma(int u,int v) //u și v parametri formali transmiși prin valoare

{

u=u+v; //aparent, parametrul u este modificat, dar el este parametru formal, nu actual

return u;

}

void main()

{

int x,y;

cout<<calcul_suma(5,7);

cout<<endl<<calcul_suma(122,359);

cout<<endl<<"x șiy=";

cin>>x>>y;

cout<<endl<<calcul_suma(x,y);

cout<<endl<<x; // se poate verifica faptul că x nu este modificat în urma apelului

}

Parametrii actuali trebuie să corespundă ca număr, ordine și tip cu parametrii formali.

Parametrii transmiși prin valoare constituie date de intrare pentru o funcție, niciodată nu pot constitui date de ieșire.

Parametri transmiși prin referință

Rescriem funcția calcul_suma de mai sus, în așa fel încât aceasta să lucreze direct asupra parametrilor actuali:

int calcul_suma(int &u,int &v) //u și v parametri formali transmiși prin referință

{

u=u+v; //parametrul u este modificat, și fiind transmis prin referință, modificarea are efect

//și asupra parametrului actual.

return u;

}

void main()

{

int x,y;

cout<<endl<<"x șiy=";

cin>>x>>y;

cout<<endl<<calcul_suma(x,y);

cout<<endl<<x; // se poate verifica faptul că x este modificat în urma apelului

}

Parametrii transmiși prin referință se pot modifica în urma apelului funcției, deoarece funcția are acces la locația lor de memorie. Parametrii transmiși prin referință pot constitui atât date de intrare, cât și date de ieșire pentru o funcție.

Un parametru transmis prin referință se comportă asemănător cu o variabilă globală pentru funcția respectivă. Totuși, ei nu sunt accesibili și altor funcții, precum adevăratele variabile globale.

Operatorul & se numește operator de adresare, și semnificația lui este "adresa lui...".

Aplicații

1. Unde este eroarea în funcția de mai jos?

int demo(float x, y)
{ return (x+y)/2}

2. Scrie o funcție care returnează suma cifrelor unui număr dat ca parametru.

3. Scrie o funcție care returnează numărul cifrelor pare dintr-un   număr.

4. Scrie o funcție care returnează cifra de rang k dintr-un   număr n. Rangul este numărul de ordine al cifrei începând din dreapta. Numerele n și k se dau ca parametri.

5. Se citesc de le tastatură două numere întregi a și b. Scrie un program care verifică dacă cele două numere au produsul cifrelor egale, folosind o funcție care calculează produsul cifrelor unui număr.

6. Să se calculeze valoarea expresiei E=1+4+7+... +(3n-2). Exemplu: pentru n=5, E=1+4+7+10+13=35.

7. Să se calculeze valoarea expresiei E=2-4+6-... +(-1)^(n+1)*(2n) Exemplu: pentru n=6, E=2-4+6-8+10-12=-6.

8. Să se calculeze produsul primelor n numere naturale impare. Pentru n=4, P=1*3*5*7=105.

9. Scrie o funcție care testează dacă un număr natural x dat ca parametru este prim sau nu.

10. Să se tipărească elementele prime ale unui șir de n numere întregi citit de la tastatură, precum și numărul acestora. Pentru n=5 și șirul 11 12 13 14 15 se va tipări 11 13.

11. (Bac 2000) Scrie un program care generează toate numerele prime strict mai mici decât x (x număr natural). Numerele vor fi scrise în fișierul "bac.txt" câte unul pe linie.

12 (Bac 2000) Ce valori va afișa programul următor?

int n,m;
void T(int n, int &m)
{n+=2; m--}

int main()
{
n=2; m=5;
T(n,m);
cout<<endl<<"n<<" "<<m;
    n=10; m=20;
    T(n,m);
    cout<<endl<<"n<<" "<<m;
}

a) 4 4 12 19
b) 4 5 12 20
c) 2 4 10 19
d) 2 5 10 20
e) 7 2 22 10

13. (Bac 2000) În fișierul BAC.txt se află mai multe numere naturale de cel mult 3 cifre fiecare, despărțiote prin spații. Scrieți un program care creează un alt fișier BAC2.txt care conține exact aceleași numere, câte unul pe linie, în ordinea crescătoare a valorilor acestora. Programul ca conține o funcție care interschimbă între ele două numere întregi date ca parametru.

14. Care din următoarele variante reprezintă formatul corect al unei   funcții reale cu un parametru întreg?
a) integer f(float x)            b) float f(int &x)         c) float f(float &x);          d) int f(float x)

15. Care este valoarea variabilei n în urma execuției programului următor?

int F(char a[2])
{
    int i=0;
    while(a[i++]);
    return i;
}
int main()
{
    int n=F("abcdefgh");
}

a) 9
b) 8
c) 2
d) programul ciclează.
e) programul este greșit deoarece șirul dat ca parametru actual nu corespunde ca lungime cu parametrul formal a al funcției F.

16. In fisierul numere.txt sunt mai multe numere naturale scrise pe un singur rand. Scrie un program care creează un fișier beta.txt care sa conțină câte unul pe linie acele numere care au suma cifrelor număr par.

Rezolvare:

#include <iostream>
#include <fstream>
using namespace std;
fstream n("numere.txt",ios::in);
fstream b("beta.txt",ios::out);
int numar;
int main()
{
    while(n>>numar)
    {
        int S=0;
        int copie;
        copie=numar;
        while(copie>0)
        {
            S+=copie%10;
            copie=copie/10;
        }
        if(S%2==0)
            b<<numar<<endl;
    }

}

17.   (Problemă grad didactic definitivat)
a) Să se scrie o funcție cu numele distinct care returnează numărul de cifre distincte dintr-un număr de maxim 9 cifre primit ca parametru. Exemplu: dacă numărul este 155668912, cifrele distincte sunt: 1,2, 5, 6, 8, 9 iar numărul cifrelor distincte este 6.

b) În fișierul date.in sunt mai multe numere de maxim 9 cifre, separate prin spații. Să se numere aparițiile consecutive de numere compuse dintr-o singură cifră și să se afișeze numărul maxim de astfel de apariții. Programul va conține apeluri către funcția de la punctul a).
exemplu: dacă în fișier sunt numerele 15 222 33 5655 333 1111 55 se va afișa 3.

rezolvare

#include <iostream>
#include <fstream>
using namespace std;
fstream f("date.txt",ios::in);
int distinct(long n)
{
    // returneaza numarul de cifre distincte din n care apar 1 data\
    algoritmul: se separa cifrele lui n\
    intr-un ciclu in care se imparte n succesiv la 10 iar cifrele distincte se numara in variabila p\
    foloseste un vector int c[10] in care se numara aparitia cifrelor
    int p,q;
    int c[10]={0,0,0,0,0,0,0,0,0,0};
    while(n)
    {
        q=n%10;
        n=n/10;
        c[q]++;
    }
    p=0;
    for(int i=0;i<=9;i++)
        {
            if(c[i]>0)
            p++;
        }
    return p;
}

int main()
{
    /*
să se numere aparitiile consecutive de numere compuse dintr-o singura cifra
si sa se afiseze numarul maxim de astfel de aparitii

algoritm:

bool dist=false
int contor=0
int cmax=0
cat timp mai sunt numere infisier,
    daca nr cifre distincte = 1
        dist=true
        contor++
    dist=false
        daca cmax<contor SI contor>0
            cmax=contor
            contor=0
daca cmax>0
    afiseaza   cmax
altfel
    afiseaza "nu exista"
*/

long numar;
bool dist=false;
int contor=0,cmax=0;
while(f>>numar)
{
    if(distinct(numar)==1)
    {
        dist=true;
        contor++;
    }
    else
    {
        if(cmax<contor&&contor>0)
        {
            cmax=contor;
            contor=0;
        }
    }

}
        if(cmax<contor&&contor>0)
        {
            cmax=contor;
            contor=0;
        }
if (cmax>0)
    cout<<endl<<cmax;
else
    cout<<endl<<"nu exista";
}

Lecția 10. Stiva și coada

Stiva (eng. Stack) este o succesiune ordonată de elemente, delimitată prin două capete, în care adăugarea și eliminarea elementelor se poate face pe la un singur capăt, numit vârful stivei (Stack pointer). O stivă care nu conține nici un element se numește stivă vidă. În orice moment, putem scoate din stivă numai elementul care a fost introdus ultimul, adică elementul din vârful stivei. Acest principiu de funcționare se numește LIFO (Last In First Out, Ultimul Intrat Primul Ieșit).
Dacă ne imaginăm stiva așezată vertical, principiul ei de utilizare se aseamănă cu un teanc de CD-uri, în care putem pune numai în vârf și putem lua numai ultimul CD din vărf.
Putem implementa o stivă cu ajutorul unui vector, numit st. Indicele în vector îl numit sp (stack pointer).
Spre deosebire de un vector clasic, o stivă are doar două operații: adăugarea unui element în vârf (numită push) și extragerea ultimului element din vârf (numită pop).

Indicele stivei sp poate varia numai între valorile 0 și o valoarea maximă, Nmax, stabilită la implementarea stivei.

Coada (Queue) este o succesiune ordonată de elemente, în care adăugarea elementelor se face pe la un capăt numit "capăt de introducere", iar eliminarea elementelor se face pe la celălalt capăt, numit "capăt de extragere". În orice moment putem extrage din coadă numai elementul aflat la capătul de extragere. Elementele ies din coadă în ordinea în care au fost introduse, comportament care se numește FIFO (First In First Out).
Coada poate fi implementată cu ajutorul unui vector q[] și a doi indici, pi pentru poziția elementului ultim introdus, și ps pentru poziția elementului care urmează să fie extras. Vectorul are o dimensiune maximă admisibilă, Max.
O coadă fără nici un element se numește coadă vidă, și atunci pi=ps.
Prin procesul de utilizare a cozii, ambii indici pi și ps au tendința să crească, dar pi rămâne mai mare decât ps. Când ps îl ajunge din urmă pe pi și îl egalează, coada este din nou vidă, deși cei doi indici au o valoare nenulă. Acest lucru se explică prin faptul că elementele cozii nu se translatează ci rămân pe aceeași poziție în cazul implementării prin vectori.
Adăugarea unui element înseamnă creșterea lui pi cu 1 și memorarea elementului pe noua poziție. Posibil numai dacă ps<Max-1.
Extragerea unui element înseamnă creșterea lui ps cu 1. Posibil numai dacă coada nu este vidă (pi=ps). Elementele extrase, de pe poziții inferioare indicelui ps, nu mai contează logic, deci ele nu trebuie șterse fizic.

Aplicație: operații cu stiva

Scrieți un program care, la comanda operatorului, realizează repetat una din următoarele operații: adăugarea unui element nou în vârful stivei, eliminarea elementului aflat în vârful stivei, afișarea stivei.

Rezolvare:

#include <iostream>
using namespace std;
int st[50], sp=0;
char opt; //opt=optiune
int main()
{
   do
    {
         cout<<endl<<"optiunea (a=adauga, e=extrage, l=listare, t=terminare:";
         cin>>opt;
         switch (opt)
         {
       case 'a':
           if(sp==50)cout<<endl<<"stiva este plina";
           else
           {
               sp++;
               cout<<endl<<" noul element: "; cin>>st[sp];
           }
           break;
       case 'e':
           if(sp==0) cout<<endl<<"stiva este vida ";
           else
               {
                   cout<<endl<<"s-a extras "<<st[sp];
                   sp--;
                 }
           break;
       case 'l':
           if(sp==0) cout<<endl<<"stiva este vida ";
           else
               for(int i=1;i<=sp;i++)cout<<st[i]<<" ";
           break;
       default: cout<<endl<<"optiune incorecta";
        }
   } while(opt!='t');
}

Rolul stivei interne în funcționarea subprogramelor

Limbajul C++ dispune de propria stivă internă, gestionată de compilator, care ocupă o parte din memoria rezervată programului. Această stivă este folosită în funcționarea programelor și subprogramelor, deoarece în această stivă este plasată starea programului înainte de transferul controlului către funcția apelată, urmând ca această stare să fie refăcută îndată ce controlul a revenit programului apelant, după instrucțiunea care urmează imediat după apel.

Prin starea programului se înțelege un pachet care cuprinde: adresa de revenire în program (adresa instrucțiunii următoare apelului de subprogram) și valorile tuturor variabilelor locale din modulul apelant.

Exemplu:

void B()
{
   int i=20;
   cout<<i; //se va afișa 20
}

void A()     //funcția A apelează funcția B
{
int i=10;
    B();         //înainte de apelul lui B, se va salva pe stivă valoarea i=10 și adresa de revenire în A
cout<<i; //adresa de revenire în A; se restaurează valoarea i=10 și se afișează 10
}

int main()    //funcția main apelează funcția A
{
   int i=5;
     A();   //înainte de transferul către A, se salvează pe stivă valoarea i=5 și adresa de revenire in main
   cout<<i; //adresa de revenire în main
                    //se restaurează valoarea i=5 și se va afișa 5
}

Evoluția stivei interne în cazul execuției programului de mai sus:

Controlul este deținut de funcția main()
1. stiva este goală înainte de apelarea lui A()
2. la întâlnirea apelului către A(), se plasează în stivă starea programului cuprinzând valoarea i=5 și adresa de revenire în main(), adică adresa instrucțiunii cout<<i.

Controlul este cedat funcției A()
3. contorul stivei este incrementat în momentul apelării funcției B() și pe stivă se adaugă valoarea lui i=10 și adresa de revenire în A, adică adresa lui cout<<i. Stiva conține două elemente, ultimul fiind cel adăugat de funcția A.

Controlul este cedat funcției B()

4. Controlul revine la A() în urma terminării funcției B(). Acum se extrage din vârful stivei ultimul element introdus, care conține starea programului A. Variabila locală i își recapătă valoarea 10.

5. Controlul este cedat funcției main(). În acest moment se extrage și ultimul element (primul introdus) din stivă, care restaurează valoarea lui i la 5.

Lecția 11. Recursivitate

Un algoritm recursiv se caracterizează prin proprietatea că se autoapelează, adică în interiorul lui există un apel către sine însuși. Din exteriorul algoritmului există un prim apel către acesta, după care algoritmul se autoapelează de un număr oarecare de ori, finit. La fiecare nouă autoapelare se execută din nou secvența de instrucțiuni a algoritmului, cu alte date, creîndu-se un lanț de auto-apeluri recursive. Faptul că algoritmul se aplică unor date diferite este esențial, deoarece în corpul său trebuie să existe testarea unei condiții de oprire, la îndeplinirea căreia să se termine lanțul de autoapeluri.
Majoritatea algoritmilor repetitivi se pot implementa atât în variantă nerecursviă (sau iterativă, prin cicluri while), cât și în variantă recursivă.
Varianta recursivă se recomandă în special pentru probleme definite prin relații de recurență, și pentru o gamă largă de probleme încadrate la categoria probleme rezolvabile prin metodele backtracking și divide et impera, care vor fi studiate mai târziu.

Un algoritm recursiv trebuie să îndeplinească următoarele două condiții:

să se poată executa cel puțin o dată fără a se autoapela
toate auto-apelurile să se producă astfel încât să se tindă către îndeplinirea condiției de execuție fără auto-apelare.

Exemple de algoritmi recursivi definiți pe baza unor relații de recurență.

Șirul lui Fibonacci

Șirul lui Fibonacci este un șir de numere întregi (F1, F2, ...Fn, ...) definit astfel:

F1=1;
F2=1;
F(k)=F(k-1)+F(k-2), pentru oricare k>=3.

Se obține șirul 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Acest șir de numere are o mare importanță pentru istoria matematicii, fiind cunoscut sub denumirea șirul creșterilor organice; de asemenea, raportul dintre doi termeni consecutivi tinde către un număr irațional cunoscut sub numele de numărul sau raportul de aur, a cărui expresie este larg folosită în arhitectură și artele plastice.
Caracterul recursiv al definiției (adică metoda de calcul a termenului k în funcție de termeni deja calculați anterior) conduce direct la exprimarea algoritmului.

Factorialul unui număr natural

Factorialul unui număr k este numărul k! = 1*2*3*...*(k-1)*k, respectiv egal cu produsul tuturor numerelor mai mici decât el, înmulțit cu el însuși. Se observă însă că k!=k*(k-1)!, adică din nou o relație recurentă:

factorial(k)=

1, pentru k=0
k*factorial(k-1)

Suma primelor n numere naturale impare

S(0)=0
S(1)=1;                           2*i-1 pentru i=1
S(2)=1+3                        2*i-1 pentru i=2
S(3)=1+3+5                    2*i-1 pentru i=3
................................................................
S(k)=(2*k-1)+S(k-1)

Rolul stivei în execuția unei funcții recursive

La fiecare auto-apel se salvează pe stiva internă, împreună cu adresa de revenire, starea programului, adică valorile variabilelor implicate în algoritm. Dacă luăm cazul funcției factorial, apelul inițial factorial(3) conduce la un apel recursiv factorial(2), care conduce la un alt apel recursiv factorial(1), care conduce la un ultim apel factorial(0). Acesta este ultimul apel, deoarece pentru factorial(0) se dă o valoare necalculată, cunoscută.
Lanțul de autoapeluri acre ca efect punerea succesivă în stivă a valorilor parametrului k: 3, 2, 1. După ce lanțul de autoapeluri se termină, urmează un lanț invers de reveniri, prin care se extrag în ordine inversă valorile de pe stivă: 1, 2, 3.

Retururile din auto-apeluri au loc în ordine inversă, dar și eliberarea stivei are loc în ordine inversă. Acest lucru conduce la faptul că fiecare apel se va continua cu aceeași valoare a lui k care fusese primită prin apelul său originar.

Implementarea algoritmului recursiv

Implementarea funcției factorial este imediată:

#include <iostream>
using namespace std;
int n;
long factorial(int k)
{
if(k==0) return 1;
else
return k+factorial(k-1);
}

int main()
{
cout<<"n=";
cin>>n;
cout<<endl<<n<<"!="<<factorial(n);
}

Exerciții

1. (Bacalaureat 2000) Scrieți o funcție recursivă și una iterativă (care folosește un ciclu while sau for) care returnează valoarea expresiei:

a) E=1+3+5+... +(2n-1)

Rezolvare iterativă:

int e(int n)
{
    int exp=0;
    for(int i=1;i<=n;i++)
        exp+=2*i-1;
    return exp;
}

Rezolvare recursivă: este necesar să exprimăm termenul E(n) în funcție de E(n-1)
E(n)=E(n-1)+2*n-1

int e(int n)
{
   if(n==1)return 1;
    else
   return e(n-1)+2*n-1;
}

b) E=1*4*7*...(3n-2)

iterativ:

int E(int n)
{
int exp=1;
for(int i=1;i<=n;i++)
     exp*=3*i-2;
return exp;
}

recursiv: E(n)=E(n-1)*(3*n-2)

int e(int n)
{
    if(n==1) return 1;
    else
       return e(n-1)*(3*n-2);
}

2. Funcția int cmmdc(a, b) pentru cel mai mare divizor comun al două numere, în variantă iterativă și recursivă.

Iterativ:{ while(a!=b) if(a>b) a-=b; else b-=a;return a;}

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

3. Numărul elementelor negative dintr-un șir de n elemente
iterativ:

int negative_it(int n)
{
int contor=0;
for(int i=0;i<=n;i++)
if(v[i]<0)contor++;
return contor;
}

recursiv:

int negative_rec(int n)
{
if(n==0)
   return 0;
else
   if(v[n]>=0) return negative(n-1); else return 1+negative(n-1);
}

3. Suma cifrelor unui număr, recursiv.

4. Produsul cifrelor unui număr, recursiv.

Funcții recursive de tip void

Să se citească prin funcție recursivă un cuvânt de la tastatură delimitat prin caracterul asterisc (*) și apoi să se afișeze literele în ordine inversă.

#include <iostream>
using namespace std;
void invers()
{
    char c;
    cin>>c;
    if(c!='*')
    {
        invers();
       cout<<c; //dacă mai întâi afișăm caracterul c și apoi apelăm invers(), literele nu mai sunt inversate. Inversarea apare din cauză că se afișează după restaurarea de pe stivă, deci ulterior citirii literelor care urmează.
    }
}
int main()
{
    invers();
}

Presupunem că se introduc în ordine literele r, e, t, u, r. Ele vor fi depuse pe stiva sistem în această ordine, iar la revenire din apeluri sunt ridicate de pe stivă și afișate în ordine inversă: r, u, t, e, r.

Funcție recursivă echivalentă cu una nerecursivă

(Bac 2001)
Transformați funcția dată într-o funcție recursivă echivalentă care să nu utilizeze nici un ciclu (fucția să returneze același rezultat ca și funcția dată, oricare ar fi valoarea parametrului).

short ms(long i)
{
short j=0;
while(!(i%10))
{
j++;
i/=10;
}
return j;
}

Lecția 12. Aplicații la funcții recursive

1. Prelucrarea elementelor unui vector de întregi:

Scrieți o funcție recursivă care returnează:

numărul elementelor negative dintr-un șir de numere întregi memorat într-un vector.
numărul elementelor pare,
numărul elementelor prime,
numărul pătratelor perfecte;
suma elementelor pare,
suma elementelor impare,
suma elementelor prime,
suma elementelor pătrate perfecte.
afișează numerele impare mai mici decât un număr dat n în ordine inversă (funcție void)
maximul dintre elementele șirului
minimul dintre elementele șirului
verifică dacă o valoare dată există în vector

2. Prelucrarea cifrelor unui număr:

Scrieți o funcție recursivă care returnează:

suma cifrelor unui număr
numărul cifrelor pare ale unui număr
produsul cifrelor unui număr
afișarea oglinditului unui număr (funcție void)
testează dacă un număr este prim
x^k, folosind relația x^k=x*(x^(k-1))
verifică dacă un număr este palindrom

3. Prelucrarea literelor unui cuvânt (șir de caractere)

Scrieți o funcție recursivă care returnează:

Numărul vocalelor dintr-un șir de caractere
Numărul consoanelor dintr-un șir de caractere
verifică dacă o literă dată există în cuvânt
Afișarea oglinditului unui cuvânt (funcție void)
Transformarea din litere mici în litere mari (funcție void)
Afișează literele alfabetului în ordine inversă (void)
Afișează în ordine inversă doar cifrele care apar într-un cuvânt citit de la tastatură (void)
Afișează în ordine directă literele și semnele speciale care apar într-un cuvânt
citit de la tastatură - fără cifre (void)
Verifică dacă un cuvânt este palindrom
Verifică dacă un cuvânt este anagrama altui cuvânt

REZOLVARE ITERATIVĂ

#include <iostream>
#include <string.h>
using namespace std;
#include <conio.h>
char s[10], t[10];
bool anagrama(char u[], char v[])
{
    bool ana=true;
    int m=strlen(u);
    int n=strlen(v);
    if(m!=n)ana=false;
    else
    {
       for(int i=0;i<=n;i++)
       {
           char * pt=strchr(v,u[i]);
           if(pt==NULL)
               ana=false;
           else
               *pt='*';
       }
    }
    return ana;
}

int main () {
   cout<<"cuvântul 1: ";cin>>s;
   cout<<endl<<"cuvântul 2: ";cin>>t;
   if(anagrama(s,t))cout<<"da";
   else
       cout<<"nu";
   getch();
   return 0;
}

REZOLVARE RECURSIVĂ

#include <iostream>
#include <string.h>
using namespace std;
#include <conio.h>
char s[10], t[10];
bool anagrama(char u[], char v[])
{
    int m=strlen(u);
    int n=strlen(v);
    if(m!=n)return false;
    else if(m==0)return true;
    else
    {
        char * pt=strchr(v,*u); //cauta în v cartacterul din u[0]
        if(pt==NULL)
            return false;
        else
            {
                //se aduce caracterul gasit pe prima pozitie în v prin interschimbare cu v[0]
                char aux=v[0];
                *v=*pt;
                *pt=aux;
                return anagrama(u+1,v+1);
            }
    }
}

int main () {
   cout<<"cuvântul 1: ";cin>>s;
   cout<<endl<<"cuvântul 2: ";cin>>t;
   if(anagrama(s,t))cout<<"da";
   else
       cout<<"nu";
   getch();
   return 0;
}

PROBLEME REZOLVATE

1. Funcție recursivă care găsește cuvântul cel mai lung dintre mai multe cuvinte introduse de la tastaură.

Să se scrie o funcție recursivă care citește o serie de cuvinte de la tastatură până când se introduce un cuvânt care începe cu caracterul * și returnează un pointer către cel mai lung cuvânt introdus. În funcția main() se va afișa acest cuvânt de lungime maximă.

Hint: se va folosi alocarea dinamică pentru a se memora cel mai lung cuvânt introdus până la momentul actual.

#include <iostream>
#include <string.h>
#include <conio.h>
using namespace std;
char* maxcuv()
{
   char cuvactual[20]; //spațiu rezervat pentru cuvântul citit actual
   char* recursiv; // declarare pointer pentru a se accesa returul furnizat de apelul recursiv
   char* cuvret=new char[20]; //alocare dinamică pentru cuvantul maxim returnat de instanta actuală
   cuvret[0]=NULL; //initializare cuvant de retur cu sirul vid pentru eventualitatea sfărșitului de apeluri recursive
   cout<<endl<<"cuvantul urmator: ";
   cin>>cuvactual;
   if(cuvactual[0]!='*') //daca se introduce * nu se mai fac autoapeluri si se termina recursivitatea

{
   recursiv=maxcuv(); // se interceptează returul din apelul recursiv
   if(strlen(cuvactual)>strlen(recursiv))
       strcpy(cuvret,cuvactual); //in cuvret se copiaza cel mai lung cuvant dintre cel curent si cel recursiv
   else
       strcpy(cuvret,recursiv);
}
   return cuvret;
}
int main()
{
   cout<<maxcuv();
   getch();
}

2. Funcție recursivă care găsește cuvântul cel mai lung dintr-o frază aflată în memorie.

Să se scrie o funcție recursivă care întoarce un pointer către cel mai lung cuvânt dintr-o frază.
În funcția main() se va afișa acest cuvânt de lungime maximă.

#include <iostream>
#include <string.h>
#include <conio.h>
using namespace std;
char fraza[100];
char* maxcuv(int poz)
{
    char cuvactual[20]; //spatiu rezervat pentru cuvantul curent
    char* recursiv; // declarare pointer pentru a se accesa returul furnizat de apelul recursiv
    char* cuvret=new char[20]; //alocare dinamica pentru cuvantul maxim returnat de instanta actuala
    cuvret[0]=NULL; //initializare cuvant de retur cu sirul vid pentru eventualitatea sfârsitului de apeluri recursive
   while(fraza[poz]==' ')poz++; //salt peste spatiile dintre cuvinte
   int j=0; //pointer in cuvactual
   while(fraza[poz]!=' '&&fraza[poz]!=NULL)
   {
       cuvactual[j++]=fraza[poz++]; //copiere 1 cuvant in zona de buffer cuvant
   }
   cuvactual[j++]=NULL; //plasare terminator de sir
    if(strlen(cuvactual) ) //daca s-a intalnit sfarsitul frazei nu se mai fac autoapeluri si se termina recursivitatea
   {
       recursiv=maxcuv(poz); // se intercepteaza returul din apelul recursiv
       if(strlen(cuvactual)>strlen(recursiv))
           strcpy(cuvret,cuvactual); //in cuvret se copiaza cel mai lung cuvant dintre cel curent si cel recursiv
       else
              strcpy(cuvret,recursiv);
   }
    return cuvret;
}
int main()
{
   gets(fraza);
   cout<<maxcuv(0);
   getch();
}

Lecția 13:Tehnici de programare

1. metoda backtracking

Metoda baccktracking este o metodă standardizată de programare, care se folosește atunci când avem nevoie de generarea exhaustivă și sistematică a unei mulțimi de soluții (o parcurgere exhaustivă tratează sau vizitează toate elementele mulțimii, sistematic). De cele mai multe ori nu avem nevoie de toate elementele, ci de un subset al lor, care îndeplinesc anumite condiții specifice.

Exemplul 1: permutările de n elemente.

Permutările de n elemente sunt mulțimi ordonate ce conțin elementele mulțimii {1, 2, ..., n} luate o singură dată. Pentru n=3, avem mulțimea de pornire {1, 2, 3}. Permutările se generează după metoda:

cu elementul 1 pe prima poziție se alcătuiesc permutările (1,2,3) și (1,3,2)
cu elementul 2 pe prima poziție se alcătuiesc permutările (2,1,3) și (2,3,1)
cu elementul 3 pe prima poziție se alcătuiesc permutările (3,1,2) și (3,2,1).

Problema care se pune este de a forma toate combinațiile ordonate de câte 3 cifre din mulțimea {1,2,3} cu condiția ca cele trei cifre din combinație să fie unice. Faptul că sunt ordonate, înseamnă că (1,2,3) este diferit de (3,2,1) deoarece au altă ordine în interior.

Exempul 2: combinările de n elemente luate câte k.

Combinări de 4 elemente luate câte 3. Se dă mulțimea {1,2,3,4}. Să se genereze toate grupurile posibile de triplete neordonate: (1,2,3), (1,2,4), (1,3,4), (2,3,4). Aici nu are importanță ordinea elementelor dintr-un triplet, deci dacă am acceptat soluția (1,2,3) nu mai putem accepta nici o soluție formată din aceste 3 cifre: (2,1,3) sau (3,1,2) și celelalte. Față de permutări, unde aveam condiția specifică cifrele să fie unice, la combinări avem încă o condiție: să nu existe două soluții compuse din aceleași elemente.

Exemplul 3: șiruri din literele A și M de lungime n (problemă BAC 2001).

Să se genereze toate șirurile de caractere de lungime n, formate numai din literele A și M, cu condiția să nu existe două litere A alăturate. n cuprins între 0 și 13 se citește de la tastatură. De exemplu, pentru n=3, avem șirurile MMM, AMM, MAM, MMA, AMA.
Și aici există o condiție specifică, aceea de a nu exista doi de A unul lângă altul.

Toate aceste probleme mai au în comun o caracteristică: soluțiile acceptabile au o lungime fixă, cunoscută. Există însă și probleme rezolvabile prin metoda backtracking cu soluții de lungime variabilă.

Principiul metodei se bazează pe stivă și pe recursivitate.

Se generează pe rând într-o stivă (implementată printr-un vector) toate soluțiile care îndeplinesc condițiile specifice de validare. Dacă numărul de elemente care pot constitui o soluție este numărul N cunoscut, atunci o configurație a stivei st[1], st[2],... st[N] se numește soluție finală. O soluție st[1], st[2],... st[p], unde p este cuprins între 1 și n, este o soluție parțială.

Pe fiecare nivel intermediar p al stivei încercăm să punem pe rând, în ordine, fiecare din cele q elemente ale mulțimii care furnizează materialul de construcție a soluțiilor: în cazul exemplului 1, e vorba de numerele {1,2,3}, al exemplului 2 din mulțimea {1,2,3,4}, al exemplului 3 din mulțimea {A,M}. stiva va avea atâtea nivele câte elemente poate avea o soluție. În cazul exemplului 1: 3 nivele, exemplul 2: 3 nivele, exemplul 3: n nivele.

Forma generală a metodei

Soluțiile finale st[1]...st[n] sunt generate în cadrul unei funcții recursive void bktr(int k) unde parametrul k reprezintă nivelul la care s-a ajuns cu completarea stivei. Fiecare execuție a funcției din lanțul de autoapeluri tratează un nivel distinct al stivei.

Dacă mulțimea furnizoare de elemente este V={v1, v2,...vn}, schema generală a funcției bktr este:

void bktr(int k)

pentru i de la 1 la n execută (1)

început

st[k] <-- v[i] (2)

daca (valid(k) returnează adevărat) atunci (3)

dacă <soluția este finală> atunci (4)

<tipărire soluție > (5)

altfel

auto-apel bktr(p+1)

sfârșit

OBSERVAȚII:

(1): Ciclul (1) se implementează de regulă printr-un ciclu for. Fiind o funcție recursivă, necesitatea de întrerupere a lanțului de auto-apeluri este rezolvată de contorul ciclului for. Când se atinge limita maximă n, funcția nu mai face auto=apel.

(2): Urcarea pe stivă a elementului v[i] este provizorie, căci dacă el nu este soluție validă va fi înlocuit imediat de elementul v[i+1] în cadrul ciclului for.

(3): funcția bool valid(int k) întoarce true dacă elementul din vârful stivei este acceptabil din punctul de vedere al condițiilor specifice și false dacă nu satisface.

(4) condiția de soluție finală revine de obicei la atingerea nivelului n al stivei, dacă soluțiile au lungimi agale, cunoscute, cazul cel mai frecvent.

(5) funcția de tipărire a soluției listează de regulă conținutul stivei, de la bază până la vârf.

Implementarea metodei pentru problema permutărilor

Mulțimea V este {1,2,3}, n=3. O implementăm prin vectorul V={1,2,3}. Soluția are tot 3 elemente.

void permutari(int k)
{
      for(int i=0;i<=n-1;i++);
      {
           st[k]=V[i];
           if(valid(k))
                if(k==n)
                   tipar(k);
                else
                    permutari(k+1);
       }
}

Funcția valid verifică dacă st[k] are o valoare diferită de oricare element aflat deja pe stivă.

bool valid(int k)
{
   bool val=true;
   for(int i=1;i<k&&val;i++)
       if(st[i]==st[k]) val=false;
   return val;
}

Funcția tipar(k) afișează stiva:

void tipar(int k)
{
   cout<<endl;
   for(int i=1;i<=k;i++)
      cout<<st[i]<<" ";
}

Implementarea metodei pentru problema combinărilor

Mulțimea V={1,2,3,4}, are n=4 elemente, soluția are q=3 elemente.

void combinari(int k)
{
      for(int i=0;i<=n-1;i++);
      {
           st[k]=V[i];
           if(valid(k))
                if(k==q)
                   tipar(k);
                else
                    combinari(k+1);
       }
}

Funcția valid va testa în plus față de problema permutărilor, condiția ca elementele stivei să fie în ordine strict crescătoare, ceea ce nu permite soluții duplicat ( formate din aceleași elemente altfel aranjate).

bool valid(int k)
{
   bool val=true;
   for(int i=2;i<=k&&val;i++)
       if(st[i]<=st[i-1]) val=false;
   return val;
}

Funcția tipar rămâne la fel.

Implementarea metodei pentru problema șirurilor de A și M

Mulțimea V={A,M} are n=2 elemente. Soluția are q elemente, q este <13 citit de la tastatură.
Pe stivă se vor pune deci fix q elemente, cu condiția să nu fie 2 de A unul lângă altul.

void siruriAM(int k)
{
   for(int i=0; i<=n-1; i++)
   {
       st[k]=V[i];
       if(valid(k))
          if(k==q) tipar();
          else siruriAM(k+1);
    }
}

bool valid(int k)
{ if(k>=2 && st[k]=='A' && st[k-1]=='A')return false;
   else return true;
}

voit tipar(int k)
{ cout<<endl;
   for(int i=1;i<=k<i++)cout<<st[i];
}

Probleme

1. (BAC 2001) Să se genereze toate șirurile formate din n cifre, n<15 citit de la tastatură, fiecare șir având următoarele proprietăți:
- conține numai cifrele {1,2,3,4};
- oricare două cifre alăturate sunt fie ambele pare, fie ambele impare.

2. (BAC 2001) Pentru n dat, citit de la tastatură, să se afișeze toate șirurile de litere L1,L2,L3... formate din n litere (din alfabetul A...Z) cu condiția ca toate literele să fie distincte și oricare două litere alăturate din șir să fie alăturarte și în alfabet.

3. Problema comis-voiajorului: un comis-voiajor are de vizitat n orașe numerotate 1,2,...n. El trebuie să plece dintr-un oraș de start și să viziteze toate orașele, trecând o singurtă dată prin fiecare și să revină în orașul de plecare. Se cunoaște că între unele orașe există drumuri, iar între altele nu. drumurile directe dintre două orașe i și j se memorează cu ajutorul unei matrici [i, j] în care A[i,j]=1 dacă există drum de la i la j, și 0 dacă nu există drum de la i la j.

4. Problema rucsacului: un turist are un rucsac în care încap maxim Q obiecte și n obiecte disponibile, din trei categorii: 'i' = îmbrăcăminte, 'a' = alimente, 't' = trusa medicală. Datele se citesc din fișierul rucsac.dat care conține pe primele două linii numărul n și numărul Q, apoi pe următoarele liniii tipurile obiectelor care se pot alege. Determinați toate posibilitățile turistului de a încărca m obiecte în rucsac, știind că:
- trebuie să ia cel puțin trei articole alimentare
- cel mult două de îmbrăcăminte
- cel mult două din trusa medicala
- din fiecare categorie să ia cel puțin un obiect.

5. Problema labirintului: Se dă un labirint sub formă de matrice cu n linii și m coloane. Fiecare element al matricei se codifică cu 0 dacă este zid și cu 1 dacă este culoar. Într-un punct de coordonate i,j se găsește o persoană. Să se găsească toate ieșirile din labirint, știind că persoana se poate deplasa numai în direcțiile sus-jos-stânga-dreapta.

6. Săritura calului: Se dă o tablă de șah de dimensiune n*n. Un cal se află într-unul din colțuri. Să se găsească toate modalitățile prin care acesta poate să parcurgă toată tabla, fără să treacă de două ori prin același loc.

7. Colorarea hărților: Fiind dată o hartă cu n țări, se cere o soluție de colorare a hărții, utilizând cel mult 4 culori, astfel încât două țări adiacente să fie colorate diferit.

8. Plata sumei. Se dă suma s și n tipuri de monede având valorile a1, a2,... an. Se cer toate modalitățile de plată a sumei s utilizând aceste monede. Există un număr nelimitat de exemplare din fiecare monedă.

9. Labirintul 2: Aceeași cerință ca la problema 5, însă celulele matricii sunt codificate astfel: ieșirile din cameră către sus, dreapta, jos, stânga, în ordinea asta, sunt codificate în ultimele 4 cifre binare: ele au valorile 0 dacă direcție este închisă de un zid, respectiv 1 dacă este coridor. Deci numărul 1001 în baza 2 (egal cu 9 în baza 10) semnifică: se poate merge spre nord și spre vest. Se dă o celulă de start (i,j) și se cer toate drumurile care duc la o ieșire.

10. Anagrame. se citește un cuvânt de 6 litere și se cer toate anagramele cuvântului citit.

11. Ecuație cu numere naturale. Găsiți toate soluțiile cu numere naturale ale ecuației 3x+y+4xz=100.

12. Pisici și câini. Se cer toate soluțiile de așezare în linie a p pisici și c câini astfel încât să nu existe o singură pisică între doi câini.

13. Cele n regine. Se dă o tablă de șah cu latura n*n și n dame. Se cer toate posibilitățile de aranjare a damelor pe tablă astfel încât să nu se atace reciproc.

Lecția 14. Recapitulare

Problema rezolvată: să se construiască 2 liste apoi să se construiască a 3-a lista formată din reuniunea nodurilor celor două liste inițiale, apoi a 4-a listă conținând intersecția nodurilor listelor 1 și 2.

/*crează 2 liste apoi creaza reuniunea si intersectia lor
nodurile se citesc din fisierele lista1.txt si lista2.txt
funcția de creare listă are ca parametru numele fisierului cu nodurile
fisierele lista1.txt si lista2.txt contin numărul de noduri n apoi n valori pentru noduri
date de test:

lista1.txt conține:
5...........................n=numar de noduri
15
47
28
10
99

lista2.txt conține
6 ...........................n= numărul de noduri
15
33
25
10
3
8
*/

#include <iostream>
#include <fstream>
using namespace std;
struct nod
{
    int info;
    nod* lnk;
};
nod* creare_lista(char* fisier)
{
    fstream f(fisier,ios::in);
    nod* p=new nod;
    p=NULL;
    nod* q;
    int n;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        q=new nod;
        q->lnk=p;
        f>>q->info;
        p=q;
    }
    return p;
}
void listare_lista(nod* p)
{
    cout<<endl;
    while(p)
    {
        cout<<p->info<<" ";
        p=p->lnk;
    }
}
bool caut_valoare_in_lista(int val,nod* lista)
{
    bool sw=false;
    while(lista&&!sw)
    {
        if(lista->info==val)
            sw=true;
        else
            lista=lista->lnk;
    }
    return sw;
}
nod* reuniune(nod* l1,nod* l2)
{
    nod* p=l1; //copie pt reutilizarea lui l1
    //copiaza lista 1 in lista reuniune
    nod* r=new nod,*q;
    r=NULL; //r este adresa de start a listei noi
    while(l1)
    {
        q=new nod;
        q->info=l1->info;
        q->lnk=r;
        r=q;
        l1=l1->lnk;
    }
    //adauga la r nodurile din lista 2 care nu se regasesc in lista 1
    while(l2)
    {
        if(!caut_valoare_in_lista(l2->info,p))
        {
            q=new nod;
            q->info=l2->info;
            q->lnk=r;
            r=q;
        }
        l2=l2->lnk;
    }
    return r;
}
nod* intersectie(nod* l1, nod* l2)
{
    nod* p=new nod;
    p=NULL;
    while(l1)
    {
        if(caut_valoare_in_lista(l1->info,l2))
           {
               nod* q=new nod;
               q->info=l1->info;
               q->lnk=p;
               p=q;
           }
        l1=l1->lnk;
    }
    return p;
}
int main()
{
    nod* L1=creare_lista("lista1.txt");
    nod* L2=creare_lista("lista2.txt");
    listare_lista(L1);
    listare_lista(L2);
    nod* L3=reuniune(L1,L2);
    listare_lista(L3);
    nod* L4=intersectie(L1,L2);
    listare_lista(L4);
}

Săritura calului

Să se genereze mutările unui cal pe o tablă de șah cu n*n pătrate astfel încât să se acopere întreaga suprafață a tablei, fără a trece de două ori prin același pătrat. Dacă problema nu are soluție, să se afișeze textul "Nu există soluție".

#include <iostream>
#include <conio.h>
using namespace std;
int A[10][10]; //această matrice va memora 0 dacă pătratul nu a fost vizitat și 1 dacă a fost vizitat.
int n;
bool valid(int k);
void tipar();
void xcal(int k);
bool xsol=false; //semnalizator pentru găsirea unei soluții
int st[100][2];
int main()
{
    cout<<"n=";
    cin>>n;
    xcal(1);
    if(!xsol)
        cout<<"nu sunt solutii";
    getch();
}
void xcal(int k)
{
    for(int i=1;i<=n*n&&!xsol;i++) //pătratele sunt vizitate în ordine după indicele i
    {
        int L=(i-1)/n+1; //din valoarea lui i se pot deduce numărul de linie L și de coloană C.
        int C=(i-1)%n+1;
        st[k][0]=L;
        st[k][1]=C;
        if(valid(k))
        {
            A[L][C]=1; //se consemnează vizitarea pătratului L, C
            if(k==n*n)
            {
                tipar();
                xsol=true; //se consemnează obținerea unei soluții
            }
            else
                xcal(k+1);
            A[L][C]=0; // se șterge marcajul de vizitare al pătratului pentru a putea fi reutilizat
                                // eventual pe altă variantă, dacă varianta actuală nu va avea succes.
        }
    }
}
bool valid(int k)
{
    bool codret=false;
    int L=st[k][0];
    int C=st[k][1];
    if(k==1)codret= true; //prima celulă 1,1 este validă întotdeauna
    else
        if(A[L][C]==1)codret=false; //dacă celula a mai fost vizitată, fals.
        else
        {
            int lant=st[k-1][0]; //se verifică relația dintre două poziții succesive
            int cant=st[k-1][1]; // dacă îndeplinește regula mutării calului
            if(L==lant-1&&(C==cant-2||C==cant+2))codret=true;
            else if(L==lant-2&&(C==cant-1||C==cant+1))codret=true;
                else if(L==lant+1&&(C==cant-2||C==cant+2))codret=true;
                    else if(L==lant+2&&(C==cant-1||C==cant+1))codret=true;
        }
    return codret;
}
void tipar()
{
    cout<<endl;
    for(int i=1;i<=n*n;i++)
        cout<<"("<<st[i][0]<<" "<<st[i][1]<<")";
}

Formular trimitere rezolvare teză

FORMULAR

Rezultate backtracking și liste

Nume	bkt	liste
Alexandru Octavian	6	6
Andronic Vlad Ștefan	4	4
Ardelean Remus	10	6
Bâtcă Radu	4	5
Bogoi Ionuț	10	10
Busuioc Andrei Laurențiu	6	6
Cautiș Laura Elena	7	9
Chirilă Nicu	7	7
Cojocaru Florin Dragoș	7	6
Constantinescu Raul Ionuț	10	6
Cosor Andrei	8	10
Dinu Cătălin	9	5
Dinu Claudiu	7	10
Dârdală Nicoleta	7	6
Gurea Vlad Nicolae	7	6
Marian Răzvan	9	6
Marin Simona Cristiana	6	6
Moldoveanu Cristina	7	7
Nan Crina Florina	6	5
Palade Gabriel	7	7
Penghis Anca Daniela	9	8
Pomană Alexandru Radu	6	6
Radu Florin Cornel	9	6
Rotaru Emilian Teodor	8	5
Stoica Roxana Bianca	8	6
Tănase Nița	7	8
Țoca Dragoș Ionuț	9	5

Lecția 15. Metoda DIVIDE ET IMPERA

Prezentare generală

Divide et impera este o tehnică de programare care se bazează pe identificarea unei operații elementare simple (care, de la caz la caz, poate fi calculul unei expresii, sau o comparare între doi termeni ai unui șir, etc) care se poate efectua în mod repetat, recursiv asupra unor eșantioane mici din masivul de date inițial. Acest masiv de date inițial este de regulă un vector. Fiecare eșantion mic furnizează o soluție parțială. Aceste soluții parțiale sunt apoi integrate, prelucrate, combinate una câte una în corpul funcției recursive divide&impera, pe ramura de retur a acesteia.

Funcția recursivă D&I are în corpul ei două alternative principale:

S-a ajuns la o problemă care admite o rezolvare imediată, caz în care se termină lanțul apelurilor recursive, se efectuează problema cerută (calculul expresiei, sau comparația, etc) și se întoarcfe rezultatul pe return.
Nu s-a ajuns la situația de la punctul 1, ceea ce conduce la descompunerea mai departe a masivului în două sau mai multe eșantioane mai mici, apelul recursiv al funcției pentru fiecare eșantion, combinarea rezultatelor primite și apoi returul.

Exemplu:

Valoarea maximă dintr-un șir.

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

Această problemă admite bineînțeles o soluție banală, iterativă, dar constituie și cel mai simplu exemplu de aplicare a metodei Divide & impera.

Pentru a putea aplica un algoritm divide et impera, trebuie să identificăm o metodă de eșantionare a domeniului în două regiuni, de exemplu în două părți egale: domeniul I elementele de la i=1 până la i=[n/2], și domeniul II conținând elementele celelalte, de la [n/2]+1 până la n.

Logica algoritmului este următoarea: dacă am calculat maximul din primul domeniu și maximul din al doilea domeniu, maximul din întregul masiv inițial este egal cu maximul dintre cele două subdomenii, I și II.

Deci vom avea o funcție recursivă cu următoarea schemă:

Dacă domeniul se mai poate impărți,

împarte domeniul în două,
Apelează recursiv funcția pentru fiecare subdomeniu
Combină (compara, calculează, etc) cele două rezultate primite, deci returnează în acest caz maximul dintre cele două rezultate

Daca domeniul nu se poate împărți, deoarece nu conține decât un singur element, întoarce valoarea acelui element.

Implementare

#include <iostream>

using namespace std;

Int v[10], n;

Int maxim(int i,int j)

{

Int a,b;

if(i==j) return v[i];

else

{

a=maxim(i,(i+j)/2);

b=maxim((i+j)/2+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<<”maximul = “<<maxim(1,n);

}

Observație: Pentru a putea utiliza funcția recursivă maxim cu un algoritm divide et impera, este necesar ca în lista de parametri ai funcției să existe valorile între care este delimitat subdomeniul curent pe care se aplică apelul. De aceea, de regulă, o funcție d&i are cel puțin doi parametri de tipul limite de interval: i și j. Inițial, i și j cponțin limitelui întregului masiv de date, adică 1 și n.

Comparație între metodele backtracking și divide & impera

Backtracking	Divide & impera
recursivă	recursivă
Utilizează o stivă	Nu utilizează stivă
Soluția este un vector (stiva)	Soluția poate fi atât vector cât și scalar
Soluția poate fi multiplă	Soluția este unică
Tipul funcției recursive este void void bkt(int k)	Tipul funcției recursive este de regulă diferit de void, dar există și exemple de funcții d&i de tip void
Funcția recursivă are un parametru întreg, nivelul următor al stivei	Funcția recursivă are doi parametri întregi, capetele intervalului
Lanțul apelurilor recursive se oprește când s-a atins limita stivei = mărimea soluției	Lanțul apelurilor recursive se oprește atunci când domeniul nu se mai poate diviza, adică atunci când capătul din stânga coincide cu capătul din dreapta, deci când i=j.

Sortarea rapidă (Quick sort)

Se dă vectorul vec cu componente întregi. Se cere să se sorteze crescător.

Algoritmul quick sort este mai rapid decât cele clasice, prin metoda bulelor, a inserției directe sau a selectării directe, care dau rezultatul în n*n operații. Complexitatea lui quick sort este n*log(n).

Ideea algoritmului este următoarea: se alege un element al șirului (opțional, primul element) și se plasează pe o poziție intermediară, astfel încât toate elementele mai mici decât acesta (numit pivot) să se așeze în stânga lui, iar toate elementele mai mari se așează în dreapta.

Algoritmul continuă recursiv în mod identic, pentru subșirul din stânga și apoi pentru subșirul din dreapta.

Elementul pivot este așezat direct pe poziția sa definitivă. Pentru a realiza acest lucru, doi indici i și j pornesc simultan din cele două extremități ale vectorului și se apropie unul de altul până se întâlnesc. Locul unde se întâlnesc este poziția unde se va așeza pivotul. Pivotul nu este mutat din loc până când nu i se găsește poziția, ci doar elementele mai mici decât el din dreapta sunt aduse către începutul vectorului, iar elementele mai mari decât el situate în stânga lui sunt trimise în dreapta, prin interschimbare. Când i devine egal cu j, elementul pivot este adus prin interschimbare pe poziția precedentă, iar algoritmul se reia pentru cele două subșiruri, de la stânga și de la dreapta pivotului.

Testul de la începutul funcției if(inf<sup) decide dacă se mai face sau nu un apel recursiv. În cazul în care inf=sup, sub-șirul nu are decât un singur element, care deci este sortat.

Exemplu: se dă vectorul vec={5,3,7,2,9} unde n= 5 și pivot=vec[0]=5.

Funcția qs primește ca parametri valoarea indicilor inf=0 și sup=n-1=4 de la capetele intervalului.

Se caută poziția finală a elementului pivot=5.

Indicele i se inițializează cu inf=0, deci vec[i]=5, iar j se inițializează cu sup=4, vec[j]=9.

vec={5,3,7,2,9} i=1 j=4;

I avansează către dreapta cât timp vec[i] se menține mai mic sau egal decât pivot și se oprește când vec[i]>pivot.

vec={5,3,7,2,9} i=2 j=4;

Acum, i se oprește, iar j scade cu câte o unitate cât timp vec[j] se menține mai mare strict decât pivotul, și se oprește când vec[j] devine mai mic decât pivotul.

vec={5,3,7,2,9} i=2 j=3

Acum j se oprește. Când ambii indici i și j s-au oprit, dacă i este mai mic decât j, elementele indicate de ei își schimbă pozițiile între ele, fără a fi afectate însă valorile indicilor.

vec={5,3,2,7,9} i=2 j=3

Dacă i este mai mic decât j, i se incrementează iar j se decrementează.

vec={5,3,2,7,9} i=3 j=2

În acest moment, în mod normal ar trebui reluat procesul de înaintare a lui i spre dreapta și a lui j spre stânga. Deoarece însă i a devenit mai mare decât j, înseamnă că s-a atins poziția finală a pivotului, care este i-1. Se aduce elementul pivot pe poziția i-1, prin interschimbare cu elementul aflat pe i-1.

vec={2,3,5,7,9}

În acest moment, elementul vec[2]=5 se află pe poziția lui finală, deoarece toate elementele de la stânga lui sunt mai mici decât el, iar toate elementele de la dreapta lui sunt mai mari decât el.

Acum se apelează în mod recursiv funcția qs pentru cele două sub-șiruri, de la stânga și de la dreapta pivotului.

#include <iostream>

#include <fstream>

using namespace std;

fstream f("date.in",ios::in);

int a, n=1;

int *vec;

void permut(int i,int j)

{

int aux=vec[i];

vec[i]=vec[j];

vec[j]=aux;

}

void qsort(int inf,int sup)

{

if(inf<sup)

{

int pivot=vec[inf],i=inf,j=sup;

while(i<j)

{

while(i<=sup&&vec[i]<=pivot)i++;

while(j>=inf&&vec[j]>pivot)j--;

if(i<j)

{

permut(i,j);

i++;

j--;

}

i--;

vec[inf]=vec[i];

vec[i]=pivot;

qsort(inf,i-1);

qsort(i+1,sup);

}

int main()

{

vec=new int[20];

while(f>>a)

{

vec[n++]=a;

}

n--;

qsort(1,n);

for(int i=1;i<=n;i++)

cout<<vec[i]<<" ";

}

Turnurile din Hanoi

Se dau 3 tije a, b, c. Pe tija a se găsesc un număr de n discuri cu diametre diferite, așezate în ordine descrescătoare a diametrelor, astfel încât discul cel mai mare se află jos. Se cere să se mute discurile de pe tija a pe tija b, utilizând ca tijă intermediară tija c, respectând următoarele reguli:

La fiecare mutare se mută un singur disc
Nu se poate așeza un disc cu diametrul mai mare peste unul cu diametrul mai mic.

poziția inițială

Ideea algoritmului pentru transferarea a n discuri este următoarea:

se mută (nu știm cum) primele n-1 discuri, în afară de ultimul, pe tija de manevră,
Se mută discul n, cel de la bază, pe tija destinație,
Se mută (nu știm cum) cele n-1 discuri de pe tija de manevră pe tija destinație, deasupra discului n.

În rezolvarea cazului n am inserat rezolvarea cazului n-1, ceea ce înseamnă că am ales un algoritm recursiv. Dacă rezolvăm cazul n-1, cazul n se rezolvă simplu. Trebuie să dăm o rezolvare nerecursivă doar pentru cazul n=2.

Pentru cazul n=2, soluția este banală:

Mută discul 1 de pe tija a pe tija c
Mută discul 2 de pe tija a pe tija b
Mută discul 1 de pe tija c pe tija b

Observăm că soluția banală este compusă tot din 3 operații ca și soluția generală, particularizând n=2.

Observăm că cele 3 mutări se diferențiază între ele prin numărul tijei de pornire, al numărului tijei de destinație și al numărului discului mutat. Cele 3 mutări respectă următoarele reguli:

Prima mutare se face de pe tija sursă pe tija de manevră
A doua mutare se face de pe tija sursă pe tija destinație
A treia mutare se face de pe tija de manevră pe tija destinație.

Cele trei tije a, b, c își schimbă între ele succesiv rolurile de tuijă sursă, destinație sau manevră.

Corespunzător fiecărei informații de mai sus, funcția de mutare va avea deci 4 parametri: numărul inelului mutat, numărul tijei sursă, numărul tijei destinație și numărul tijei de manevră.

Acest algoritm este de tipul Divide et impera, deoarece:

Reduce problema de la rezolvarea masivului de date inițial (tija cu n discuri) la rezolvarea unui eșantion elementar (tija cu un singur disc) prin diminuări succesive ale eșantionului, deoarece fiecare apel recursiv succesiv are de rezolvat un domeniu mai mic cu o unitate;
Combină soluțiile intermediare.

#include <iostream>
using namespace std;
int n;
void mutare(int inel,char sursa,char dest,char man)
{
     if(inel==1)cout<<endl<<"muta inelul "<<inel<<" de pe tija "<<sursa<<" pe tija "<<dest;
     else
     {
         mutare(inel-1,sursa,man,dest);
         cout<<endl<<"muta inelul "<<inel<<" de pe tija "<<sursa<<" pe tija "<<dest;
         mutare(inel-1,man,dest,sursa);
     }
}
int main()
{
     cout<<"n=";
     cin>>n;
     mutare(n,'a','b','c');
}

Sortare prin interclasare

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("sir");

int n,m;

int a[20],b[20];

void sort(int,int);

void divimp(int,int);

void interclas(int,int,int);

int main()

{

cout<<"n=";

cin>>n;

for(int i=1;i<=n;i++)cin>>a[i];

divimp(1,n);

cout<<endl;

for(int i=1;i<=n;i++)cout<<a[i]<<" ";

}

void sort(int u,int v)

{

if(a[u]>a[v])

{

int k=a[u];

a[u]=a[v];

a[v]=k;

}

void divimp(int u,int v) // imparte sirul in 2 subdomenii, sorteaza fiecare subdomeniu apoi

// interclaseaza cele doua subdomenii

{

int k;

if(v-u<=1)sort(u,v);

else

{

k=(u+v)/2;

divimp(u,k-1);

divimp(k,v);

interclas(u,k,v);

}

void interclas(int p,int m,int q)

{

/* i index in a[p]... a[m-1]

j index in a[m]... a[q]

k index in b[1]... b[n]

int i,j,k;

i=p;

j=m;

k=1;

while(i<=m-1&&j<=q)

{

if(a[i]<=a[j])

{

b[k]=a[i];

i++;

k++;

}

else

{

b[k]=a[j];

j++;

k++;

}

if(i<=m-1)

{

for(j=i;j<=m-1;j++)

{

b[k]=a[j];

k++;

}

else

{

for(i=j;i<=q;i++)

{

b[k]=a[i];

k++;

}

k=1;

for(i=p;i<=q;i++)

{

a[i]=b[k];

k++;

}

}

sa se afle cmmdc prin divide et impera

/*fisierul numere.txt contine maxim 2000 de numere

cmmdc al 2 numere se afla cu algoritmul lui Euclid prin impartiri succesive sau prin diferenta.
cmmdc al 3 numere este cel mai maree divizor comun dintre cmmdc al numarului 1 si 2 si cmmdc al numarului 2 si 3
si asa mai departe

se citesc numerele in vectorul A[100]
se impart in doua partitii prin injumatatirea intervalului.
se afla cmmdc al partitiei 1 si cmmdc al partitiei 2 si se alege cmmdc dintre ele.
Date de test
45 60
125 345 65
9875 4555
*/
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
fstream f("numere.txt",ios::in);
int A[100];
int n;
int divizor,median;
int cmmdcDI(int,int);
int cmmdc(int,int);
int main()
{
    int i=1;
    while(f>>A[i])
    {
        cout<<A[i]<<endl;
        i++;
    }
    n=i-1;
    cout<<"cmmdc="<<cmmdcDI(1,n);
}
int cmmdcDI(int inf,int sup)
{
    if(inf==sup)
        divizor=A[inf];
    else
        {
            median=(inf+sup)/2;
            int div1=cmmdcDI(inf,median);
            int div2=cmmdcDI(median+1,sup);
            divizor=cmmdc(div1,div2);
        }
    return divizor;
}
int cmmdc(int a,int b)
{
    while(a!=b)
    {
        if(a>b)
        {
            a=a-b;
        }
        else
        {
            b=b-a;
        }
    }
    return a;
}

/* PROBLEMA TAIETURILOR

Se da o bucata dreptunghiulara de tabla cu lungime l si inaltime h
avand pe suprafata ei n gauri de coordonate numere intregi.
Se cere sa se decupeze din ea o bucata de arie maxima care nu prezinta gauri.
Sunt permise numai taieturi orizontale si verticale.

Rezolvare.

Coordonatele gaurilor sunt retinute in doi vectori XV si YV.
Dreptunghiul initial, precum si dreptunghiurile care apar
in procesul taierii sunt memorate in program prin coordonatele coltului din stânga jos (X,Y)
si prin lungime si inaltime (L,H).

Pentru un dreptunghi verificam daca avem sau nu o gaura in el. daca acesta are o gaură,
problema se descompune in alte patru probleme de acelasi tip.
daca dreptunghiul nu contine nici o gaura, se compara aria lui cu aria altui dreptunghi
fără gaura gasite anterior.

Date de test: 10 8 3 3 3 4 6 7 7

#include <iostream>
#include <conio.h>
#include <fstream>
using namespace std;
ifstream f("gauri.txt");
int n,l,h,xg,yg,lg,hg;
int ox[20],oy[20];
void smax(int x0,int y0,int lung,int inalt);
int main()
{
    f>>l>>h>>n;
    for(int i=1;i<=n;i++)f>>ox[i]>>oy[i];
    xg=0;
    yg=0;
    lg=0;
    hg=0;
    smax(0,0,l,h);
    cout<<endl<<"coordonate x="<<xg<<" y="<<yg<<" L="<<lg<<" H="<<hg;
    getch();
}
void smax(int x,int y,int lung,int inalt)
{   bool egaura=false;
    int i=1;
    while(i<=n&&!egaura)
        if((ox[i]>x)&&(ox[i]<(x+lung))&&(oy[i]>y)&&(oy[i]<(y+inalt)))
            egaura=true;
        else
            i++;
    if(egaura)
    {
            smax(x,y,ox[i]-x,inalt);
            smax(ox[i],y,x+lung-ox[i],inalt);
            smax(x,y,lung,oy[i]-y);
            smax(x,oy[i],l,y+inalt-oy[i]);
    }
    else
        if(lung*inalt>lg*hg)
            {
                xg=x;
                yg=y;
                lg=lung;
                hg=inalt;
            }

}

Metoda Greedy

Enunț general: se consideră o mulțime A. se cere o submulțime a sa astfel încât să fie îndeplinite anumite condiții.

Schemă de rezolvare generală:
soluția = mulțimea vidă;
Repetă
    alege x din A
    dacă este posibil, atunci include x în submulțimea soluție
Până când se obține soluția.

Problema comis-voiajorului

Un comis-voiajor pleacă dintr-un oraș, trebuie să viziteze un număr de orașe și să se întoarcă înapoi de unde a plecat cu un efort minim. Orice oraș i este legat de alt oraș j printr-o șosea lungă de A[i][j] kilometri. Se cere traseul de urmat astfel încât acesta să aibă un număr minim de kilometri.

Soluția prin Greedy: la fiecare pas se selectează orașul nevizitat aflat cel mai aproape. Se folosește vectorul de selecție S și matricea drumurilor A.

/* voiajorul trebuie sa viziteze TOATE orasele cu un cost minim.
solutia 1 prin metoda Greedy, solutia 2 prin backtracking
*/
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
ifstream f("voiajor.txt");
int n;
const int FIRST=1;
int last;
int totalcost, costmin=30000;
int A[10][10]; //matricea costurilor
int S[10]; //vectorul de selectie
int st[10]; //stiva pt backtracking
void desel();
void greedy(int);
void bkt(int);
bool valid(int);
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f>>A[i][j];
    cout<<endl<<"Solutia prin algoritm greedy"<<endl;
    desel();
    cout<<endl<<"1 ";
    S[FIRST]=1;
    greedy(FIRST);
    cout<<FIRST;
    cout<<endl<<"costul total="<<totalcost+A[last][FIRST];
    desel();
    cout<<endl<<"Solutia prin algoritm backtracking"<<endl;
    bkt(1);
    cout<<endl<<"costul minim prin backtracking="<<costmin;
    getch();
}
void desel()
{
    for(int i=1;i<=n;i++)
    {
        S[i]=0;
        st[i]=0;
    }
    totalcost=0;
}
void greedy(int nod)
{
    int i=1;
    bool gasit=false;
    int cmin=32000;
    int next=0;
    while(i<=n)
    {
        if(i!=nod&&cmin>A[nod][i]&&S[i]==0)
        {
            gasit=true;
            cmin=A[nod][i];
            next=i;
            last=next;
        }
        i++;
    }
    if(gasit)
        {
            totalcost+=A[nod][next];
            S[next]=1;
            cout<<next<<" ";
            greedy(next);
        }
    else
        return;
}
bool valid(int u)
{
    bool gasit=false;
    for(int i=1;i<u;i++)
        if(st[i]==st[u])gasit=true;
    return !gasit;
}
void bkt(int k)
{
    for(int i=1;i<=n;i++)
    {
        st[k]=i;
        if(valid(k))
            if(k==n)
            {
                st[n+1]=st[1];
                totalcost=0;
                for(int j=1;j<=n;j++)
                {
                    cout<<st[j]<<" ";
                    totalcost+=A[st[j]][st[j+1]];
                }
                cout<<st[n+1]<<" cost="<<totalcost<<endl;
                if(totalcost<costmin)costmin=totalcost;
            }
            else
                bkt(k+1);
    }
}

Metoda Programării dinamice

În programarea dinamică, de cele mai multe ori pentru a rezolva o problemă se scrie o relație de recurență care se rezolvă apoi iterativ. O altă categorie de probleme de PD sunt cele de optim, prin care se cere o soluție care să maximizeze sau să minimizeze o anumită funcție.
Principiul de bază al PD este: dacă în problema dată optimul general implică optimul parțial (înainte sau înapoi) atunci se poate aplica Programarea Dinamică. exemplu: Dacă drumul cel mai scurt dintre București și Suceava trece prin Focșani, atunci porțiunea din acest drum dintre București și Focșani este cel mai scurt drum dintre București și Focșani.
metoda PD constă în a căuta optimul general printre optimele parțiale, pe care le reținem la fiecare pas.

Problema triunghiului
Se consideră un triunghi de numere naturale care conține n linii. Se pornește din linia 1. Su ccesorul unui număr poate fi fie numărul situat pe linia următoare sub numărul precedent, fie cel situat pe coloana din dreapta. Care este cea mai mare sumă care se poate forma astfel și care sunt numerele care o formează?

2
3 5
6 3 4
5 6 1 4

S=2+3+6+6=17

Rezolvare: Se înlocuiesc pe rând, linie cu linie, toate numerele din triunghi cu sumele maxime care se pot obține până la ele. Pe ultima linie vom obține mai multe sume, dintre care se alege suma maximă. Drumul parcurs se recompune invers. Aceasta este soluția înainte. Există și o rezolvare mergând înapoi, de la ultima linie către vârful triunghiului.

/*calculeaza cea mai mare dintre sumele obtinute prin adunarea
numerelor vizitate plecand din varful triunghiului pana la baza
mergand in jos sau oblic dreapta
triunghiul de numere se afla in fisierul tr.num.
se da o solutie recursiva inainte
*/
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
fstream fnum("tr.txt",ios::in);
ofstream fout("tr.out");
char a[10][10];
int b[10][10];
char cif;
int n,i,j;
const int IMAX=30;
void scriu_fisier();
int det_suma_maxima(int l,int c);
int det_suma_maxima(int l,int c)
{
    if(l==n)return b[l][c];
    else
    {
        int vertical=det_suma_maxima(l+1,c);
        int oblic=det_suma_maxima(l+1,c+1);
        return vertical>=oblic?b[l][c]+vertical:b[l][c]+oblic;
    }
}
void scriu_fisier()
{
    fout<<"5 3 4 5 6 7";
    fout.close();
}
void citire_numere();
void citire_numere()
{
    fnum>>cif;
    cout<<cif;
    n= cif-'0';
    for ( i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            fnum>>a[i][j];
//            cout<<a[i][j];
            b[i][j]=a[i][j]-'0';

        }
    }

}
void main()
{
    citire_numere();
    int suma_maxima=det_suma_maxima(1,1);
    cout <<"suma maxima= "<<suma_maxima;
     cin>>n;
}

Problema subșirului crescător de lungime maximă

Se dă un vector cu n elemente întregi. Se cere să se afișeze cel mai lung subșir crecător al acestuia.
Exemplu: pentru n=5 se dă vectorul V={4, 1, 7, 6, 7}. Subșirul afișat va fi: 4, 7, 7.

Rezolvare: se va calcula pentru fiecare element al vectorului lungimea celui mai lung subșir crescător care se poate forma începând cu el. Se utilizează un vector auxiliar. care reține aceste lungimi.

/* programare dinamica
sa se gaseasca cel mai mare subsir crescator
*/
#include <iostream>
using namespace std;
int x[13]={5,1,9,2,4,7,10,12,5,19,6,14,11};
int l[13];
int n=13;
int succ[13];
void init();
void init()
{
    for( int i=0;i<n;i++)
    {
        l[i]=1;
        succ[i]=0;
    }
}
void subsir(int k);
void subsir(int k)
{
    int man=x[k];
    int xman=k;
    int j=k+1;
    while(j<n)
    {
        if(x[j]>man)
        {
            l[k]++;
            man=x[j];
            succ[xman]=j;
            xman=j;
        }
        j++;
    }
}
void main()

{
    init();
    for(int i=0;i<n;i++)subsir(i);
    for(int i=0;i<n;i++)
        cout<<l[i]<<endl;

    cout<<endl;
//    cin>>n;
    int imax=0;
    for(int i=0;i<n;i++)
    {
        if( l[i]>l[imax])
        {
            imax=i;
        }
    }
    cout<<endl<<x[imax]<<" ";
    int i=imax;
    while (succ[i]>0)
    {
        cout<<x[succ[i]]<<" ";
        i=succ[i];
    }
    cin>>n;

}

Pagini

C++ Modulul 2

_________________________________________

Lecția 1. Șiruri de caractere

Aplicații la parcurgerea șirurilor:

________________________________________________________________________________

Lecția 2. Funcții pentru șiruri de caractere din biblioteca standard <string.h>

strcpy, strncpy, strcmp, strncmp

Aplicație:

Test / 06.10.2016

_____________________________________

Lecția 3. Alocarea dinamică a memoriei. Variabile de tip pointer.

1. Pointeri

2. Alocarea dinamică

Pointeri către tablouri (vectori, matrici, șiruri de caractere).

Alocarea dinamică a masivelor (vectori, matrici, șiruri de caractere).

Operații cu pointeri

Lecția 4. Structuri de date neomogene

Asignarea unui nume pentru un tip de structură

Accesul la câmpurile unei structuri

Câmpuri de tip structură

Pointeri către structuri

Accesarea membrilor (componentelor) structurii prin intermediul pointerului

Aplicații

Lecția 5. Descompunerea în factori primi utilizând un vector de structuri

Lecția 6. Descompunerea în factori primi utilizând liste înlănțuite alocate dinamic

Crearea și parcurgerea unei liste înlănțuite alocate dinamic

Lecția 7. Liste: inserarea și ștergerea nodurilor

Lecția 8. Aplicații cu liste rezolvate cu ajutorul funcțiilor

TEST 20.10.2016

Lecția 9. Subprograme

Parametri transmiși prin valoare

Parametri transmiși prin referință

Aplicații

Lecția 10. Stiva și coada

Aplicație: operații cu stiva

Rolul stivei interne în funcționarea subprogramelor

Lecția 11. Recursivitate

Exemple de algoritmi recursivi definiți pe baza unor relații de recurență.

Șirul lui Fibonacci

Rolul stivei în execuția unei funcții recursive

Exerciții

Funcții recursive de tip void

Funcție recursivă echivalentă cu una nerecursivă

Lecția 12. Aplicații la funcții recursive

Lecția 13:Tehnici de programare

1. metoda backtracking

Forma generală a metodei

Probleme

Lecția 14. Recapitulare

Formular trimitere rezolvare teză

FORMULAR

Rezultate backtracking și liste

Lecția 15. Metoda DIVIDE ET IMPERA

Valoarea maximă dintr-un șir.

Implementare

Comparație între metodele backtracking și divide & impera

Niciun comentariu:

Trimiteți un comentariu