Cuprins Limbajul C

Gandirea algoritmica
Structura unui program si a unei functii in C
Constructiile de bază ale limbajului C – Notiuni generale
Constructiile de baza ale limbajului C – Tipuri de date
Constructiile de baza ale limbajului C – Operatori
Structuri de date – Lista liniara simplu inlantuita
Structuri de date – Stiva (LIFO – Last In First Out)
Structuri de date – Coada (FIFO – First In First Out)
Instructiuni ale limbajului C
Pointeri – Operatori specifici, tablouri, functii
Pointeri – Tipuri structurate de date
Functii de biblioteca
Operatii cu fisiere
Calcul Matriceal – Produsul a doua matrici
Calcul Matriceal – Inversarea unei matrici
Calcul Matricial – Metoda lui Gauss
Metode de sortare – sortare ordinara
Metode de sortare – prin selectie (Selection sort)
Metode de sortare – insertie directa (Direct Insertion Sort)
Metode de sortare – insertie binara (Binary Insertion Sort)
Metode de sortare – insertie directa folosind o santinela
Metode de sortare – metoda bulelor (Bubble Sort)
Metode de sortare – sortare rapida (Quick Sort)
Metode de sortare – prin interclasare (Merge Sort)
Recursivitate (numar factorial, algoritmul lui Euclid recursiv, sirul lui Fibonacci)
Backtracking – permutarile
Backtracking – aranjamente
Backtracking – combinari
Backtracking – problema reginelor
Backtracking – problema labirintului
Backtracking – problema calului
Backtracking – problema mingii
Metoda Divide et Impera – Suma elementelor unui sir
Metoda Divide et Impera – Problema Turnurilor din Hanoi
Metoda Divide et Impera – Elementul maxim intr-un sir
Metoda Divide et Impera – Problema cautarii binare
Grafuri neorientate – parcurgerea in latime
Grafuri neorientate – parcurgerea in adancime
Grafuri neorientate – Drumuri intr-un graf
Grafuri neorientate – ponderate
Grafuri neorientate – hamiltonian
Grafuri neorientate – euleriene
Grafuri neorientate – implementarea unui graf utilizand matricea de adiacenta
Grafuri neorientate – implementarea unui graf utilizand pointeri
Grafuri neorientate – drumul optim intr-un graf

Metode de sortare – prin interclasare (Merge Sort)

Algoritmul de sortare prin inserţie este eficient pentru valori mici ale lui n (n< =i6). De aceea, sortarea prin interclasare propune o sortare bazată pe principiul Divide et Impera, care să utilizeze sortarea prin inserţie pentru valori mici ale lui n, rezultate prin descompunerea şirului iniţial în subşiruri. Algoritmul Merge Sort se bazează pe 3 paşi esenţiali: • separarea tabloului în 2 părţi de mărimi cât mai apropiate • sortarea acestor părţi prin apeluri recursive, până la atingerea unor valori mici ale lui n pentru care se aplică sortarea prin inserţie sau până la atingerea unor subşiruri de 1 element (cazul banal) • interclasarea părţilor sortate obţinându-se direct un şir ordonat crescător
#include “stdio.h”
#include “conio.h”
//funcţia care interclasează 2 şiruri ordonate crescător
void merge(int a[], int l, int m, int r)
{
  int b[100],i=l,j=m+1,k=l,ind;
  //atât timp cât nici unul din şiruri nu s-a terminat
  while((i < = m)&&(j <= r))   {     if(a[i] <= a[j]) Continue reading

Metode de sortare – sortare rapida (Quick Sort)

Principiul acestei metode este următorul: Se alege un element pivot din tabloul ce trebuie sortat. Tabloul este astfel partiţionat în 2 subtablouri, alcătuite de o parte şi de alta a acestui pivot, astfel: elementele mai mari decât pivotul sunt mutate în dreapta pivotului iar elementele mai mici în stânga pivotului. Cele 2 subtablouri sunt sortate în mod independent prin apeluri recursive ale algoritmului.


#include "stdio.h"
#include "conio.h"
#include "values.h"
//procedura recursivă de sortare a secvenţei a[l]...a[r]
void qs(int a[], int l, int r)
{
  int v,i,j,elem;
  if(r > l)
  {
    v=a[r];
Continue reading

Metode de sortare – metoda bulelor (Bubble Sort)

Principiul acestei metode este următorul: se parcurge şirul, schimbându-se valori adiacente, dacă este cazul. La prima parcurgere cheia de valoare maximă migrează spre ultima poziţie. La a doua parcurgere, cheia de valoare imediat inferioară celei maxime migrează spre penultima poziţie. Datorită acestor migrări, metoda a fost denumită astfel, deoarece elementele de valori mari se ridică la suprafaţă asemenea unor bule.

Metoda se aseamănă oarecum cu sortarea prin selecţie, doar că partea sortată se formează în “Partea dreaptă” a şirului, aceasta crescând până când toate elementele sunt cuprinse în ea.
3 7 4 9 2 8 j=1,5 i=5 – Pe rând, se compară a[j-1] cu a[j], pentru j=1 pana la 5. Dacă a[j-1] > a[j] se inversează. Deci inversăm 7 cu 4, apoi 9 cu 2 și 9 cu 8.
3 4 7 2 8 9 j=1,4 i=4 – i=4; vom compara a[j-1] cu a[j] pentru j=1 până la 4. Dacă a[j-1] > a[j] se inversează. Deci inversăm 7 cu 2.
3 4 2 7 8 9 j=1,3 i=3 – i=3; vom compara a[j-1] cu a[j] pentru j=1 până la 3. Dacă a[j-1] > a[j] se inversează. Deci inversăm 4 cu 2.
3 2 4 7 8 9 j=1,2 i=2 – i=2; vom compara a[j-1] cu a[j] pentru j=1 până la 2. Dacă a[j-1] > a[j] se inversează. Deci inversăm 3 cu 2.
2 3 4 7 8 9 j=1,1 i=1 – i=1; vom compara a[j-1] cu a[j] pentru j=1 până la 1. Dacă a[j-1] > a[j] se inversează. Nu avem inversări.
2 3 4 7 8 9 Șirul este sortat
Continue reading

Metode de sortare – insertie directa folosind o santinela

Această variantă de inserţie foloseşte în a [0] o valoare foarte mică, mai mică decât oricare din cheile din vector. Această valoare simplifică înaintarea în “Partea stângă” sortată, având garanţia că nu vom depăşi marginea stânga a şirului Rolul santinelei este ca elementul care va fi adus pe prima poziţie să fie comparată cu o valoare sigur mai mică. Pentru această variantă de sortare, elementele şirului vor avea indicii de la 1 la n.


#include "stdio.h"
#include "conio.h"
#include "values.h"
//pentru MAXINT
void insertie_cu_santinela(int a[], int n)
{
  int i,j,elem;
  a[0]=-MAXINT;
  //valoarea minimă pentru tipul int
  for(i=2;i < = n;i++)   //pornim cu elementul a[2] (al doilea element al şirului)   {     elem=a[i];     j=i-1; Continue reading

Metode de sortare – insertie binara (Binary Insertion Sort)

Se deosebeşte de inserţia directă doar prin modul de căutare a poziţiei de inserare. Presupunem că căutăm poziţia de inserare a elementului cu valoarea 20 în secvenţa:
1 4 7 9 10 12 15 18 21 23 26 28 33

0 1 2 3 4 5 6 7 8 9 10 11 12
1 4 7 9 10 12 15 18 21 23 26 28 33
S=0 M=6 D=12

Se calculeaza M=(Standa+Dreapta)/2=(0+12)/2=6

1 4 7 9 10 12 15 18 21 23 26 28 33
S=0 M=6 D=12

a[M]=a[6]=15, 20>15 deci cautam in dreapta, noul interval este S=7, D=12

1 4 7 9 10 12 15 18 21 23 26 28 33
S=7 M=9 D=12

M=(7+12)/2=9, a[9]=23, 20<23 deci cautam in stanga, noul interval este S=6 D=8

1 4 7 9 10 12 15 18 21 23 26 28 33
S=6 M=7 D=8

M=(6+8)/2=7 a[7]=18, 20>18 deci cautam in dreapta, noul interval este S=8, D=8

1 4 7 9 10 12 15 18 21 23 26 28 33
S=M=D=8

M=(8+8)/2=8, a[8]=21, 20<21 deci cautam in stanga, noul interval este S=8, D=7

1 4 7 9 10 12 15 18 21 23 26 28 33

Conform algoritmului ne oprim cand S>D iar pozitia de inserat este S=8; inainte de inserare, elementele a[12] -> a[8] se declara spre dreapta cu o pozitie


#include "stdio.h"
#include "conio.h"
//functie care intoarce pozitie in care trebuie inserat
//a[i] in secventa a[1]...a[i-1]
int insertie_binara(int a[], int i)
Continue reading

Metode de sortare – insertie directa (Direct Insertion Sort)

În cazul acestei variante de inserţie, căutarea poziţiei în care se inserează elementul curent se face decrementai, prin parcurgerea “Părţii stânga” de la dreapta spre stânga, până la găsirea poziţiei de inserare.

3 | 7 4 9 2 8 Se porneşte de la i=1, locul elementului a[1]=7 ramane neschimbat
3 7 | 4 9 2 8 Pentru i=2, a[2]=4 va ajunge pe poziţia a[1] iar elementul a[1]=7 va fi decalat la dreapta cu o poziţie
3 4 7 | 9 2 8 Pentru i=3, locul elementului a[3]=9 ramane neschimbat
3 4 7 9 | 2 8 Pentru i=4, locul elementului a[4]=2 este pe poziţia a[0], iar elementele a[3], a[2], a[1] si a[0] se vor decala la dreapta cu o poziţie
2 3 4 7 9 | 8 Pentru i=5, locul elementului a[5]=8 este pe poziţia a[4], iar elementul a[4] va fi decalat la dreapta cu o poziţie
2 3 4 7 8 9 | Şirul este sortat


#include "stdio.h"
#include "conio.h"
void insertie(int a[], int n)
{
  int i,j,elem;
  for(i=1;i < n;i++) Continue reading

Metode de sortare – prin selectie (Selection sort)

Principiul acestei metode este următorul: şirul este împărţit în 2 părţi: o “Parte stânga” sortată şi o “Parte dreapta” nesortată. Iniţial “Partea stângă” este vidă iar “Partea dreapta” conţine tot şirul. Se caută minimul din “Partea dreapta” şi se adaugă la sfârşitul “Părţii stânga”. Algoritmul se încheie în momentul în care “Partea dreaptă” mai conţine un singur element. Acest ultim element este maximul din şir deci, în final, “Partea stânga” va conţine toate elementele şirului sortate, iar “Partea dreapta” devine vidă.

| = pozitia la care suntem
| 3 7 4 9 2 8 (alegem 3 si 2) Minimul este 2; acesta este adus pe poziţia 0
2 | 7 4 9 3 8 (alegem 3 si 7) Minimul este 3; acesta este adus pe poziţia 1
2 3 | 4 9 7 8 (alegem 4) Minimul este 4; acesta ramane pe poziţia 2
2 3 4 | 9 7 8 (alegem 9 si 7) Minimul este 7; acesta este adus pe poziţia 3
2 3 4 7 | 9 8 (alegem 9 si 8) Minimul este 8; acesta este adus pe poziţia 4
2 3 4 7 8 | 9 Partea dreapta conţine un singur element; algoritmul se opreşte
2 3 4 7 8 9 | Sirul este sortat


#include "stdio.h"
#include "conio.h"
void selectie(int a[], int n)
{
  int i,j,k,min;
  for(i=0;i < n-1;i++) Continue reading

Metode de sortare – sortare ordinara

Cel mai simplu algoritm de sortare (dar şi cel mai ineficient) se bazează pe următorul principiu: un şir este sortat dacă prin parcurgerea lui de la început până la sfârşit, fiecare element este mai mic decât succesorul. Dacă această condiţie nu este îndeplinită, inversăm cele 2 elemente. Sortarea se încheie în momentul în care parcurgerea şirului se face fără a fi necesară nici o inversare (fiecare element este mai mic decât succesorul său).

3 7 < => 4 9 2 8 i=1; inversam a[1]=7 cu a[2]=4; k=1
3 4 7 9 < => 2 8 i=3; inversam a[3]=9 cu a[4]=2; k=1
3 7 4 2 9 < => 8 i=4; inversam a[4]=9 cu a[5]=8; k=1
3 7 < => 4 2 8 9 k<>0 deci pornim un nou ciclu; i=1 inversam a[1]=7 cu a[2]=4; k=1
3 4 7 < => 2 8 9 i=2; inversam a[2]=7 cu a[3]=2; k=1
3 4 < => 2 7 8 9 k<>0 deci pornim un nou ciclu; i=1 inversam a[1]=4 cu a[2]=2; k=1
3 < => 2 4 7 8 9 k<>0 deci pornim un nou ciclu; i=0 inversam a[0]=3 cu a[1]=2; k=1
2 3 4 7 8 9 k ramane 0 (nu facem nici o inversare) deci şirul este sortat


#include "stdio.h"
#include "conio.h"
void sortare_ordinara(int a[], int n)
{
  int i,j,k,elem;
  do
  {
    for(i=0,k=0;i < n-i;i++) Continue reading