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
algoritm
Grafuri neorientate – euleriene
Fiind dat un graf neorientat, să se determine dacă este eulerian, iar dacă răspunsul este afirmativ, să se determine toate ciclurile euleriene care încep dintr-un nod dat.
Pentru a rezolva această problemă, vom parcurge următorii paşi:
• se determină dacă graful este conex
• se determină dacă fiecare nod are grad par
#include "stdio.h"
#include "conio.h"
int a[10][10],viz[10],n,m;
//parcurgere in adâncime
void df_r(int nod)
{
int k;
//afişăm nodul curent ca vizitat
printf("%d ",nod);
//marcăm nodul curent ca vizitat
viz[nod]=1;
//pentru fiecare nod k
for(k=1;k <= n;k++)
//dacă există muchie între nodul curent şi nodul k şi nodul k nu a fost incă vizitat,
//apelăm funcţia recursivă de vizitare depth first df_r având ca parametru nodul k
if(a[nod][k] && !viz[k])
df_r(k);
}
Continue reading
Grafuri neorientate – hamiltonian
Se citeşte matricea de adiacenţă a unui graf. Să se determine dacă graful este hamiltonian.
Soluţie: vom folosi metoda backtracking, aplicată asupra unei stive în care vom păstra nodurile care compun lanţul. Vom porni de la primul nod şi vom putea adăuga în stivă doar un nod adiacent. De asemenea, nodul adăugat nu trebuie să se regăsească pe nivelurile anterioare. Dacă am atins în stivă numărul total de noduri iar nodul final este adiacent cu nodul iniţial, am găsit soluţia problemei.
#include "stdio.h"
#include "conio.h"
int stiva[100],n,m,k,nr_solutii,a[20][20];
int verifica()
{
int i;
if(k>1)
//dacă a[st[k-1]][st[k]] este 0 returnăm 0
if(!a[stiva[k-1]][stiva[k]])
return 0;
else
//dacă a [stiva[k-1]][stiva [k]] este 1 căutam pe toate nivelurile
//anterioare nivelului curent
for(i=1;i <= k-1;i++)
//dacă nodul curent se găseşte pe unul din nivelurile
//anterioare returnăm 0
if(stiva[i] == stiva[k])
return 0;
//dacă stiva conţine toate nodurile grafului
if(k == n)
//iar ultimul nod nu este adiacent cu primul nod returnăm 0
if(!a[stiva[1]][stiva[k]])
return 0;
return 1;
}
Continue reading
Grafuri neorientate – ponderate
Într-un graf neorientat, fiecărei muchii i se poate asocia o pondere (un cost). Putem considera un graf neorientat fără ponderi ca fiind o particularizare a unui graf cu costuri, fiecare muchie având costul 1. Această pondere (sau cost) va exprima intensitatea relaţiei dintre 2 noduri ale grafului.
Reprezentarea unui astfel de graf G=(X,U) se face utilizând o matrice a ponderilor P(n,n) a cărei elemente se definesc astfel:
p(i,j) = 0 dacă i=j
p(i,j) = c(i,j) în cazul în care (i,j) este o muchie din U unde c(i,j) este costul muchiei (i,j)
P(i,j) = $latex \infty$ în restul cazurilor
Utilizarea grafurilor ponderate este des întâlnită în practică. Cel mai sugestiv exemplu este cel al unei reţele de oraşe, nodurile grafului reprezentând oraşele, muchiile reprezentând legăturile (şoselele) dintre oraşe iar costul lor este dat de distanţa dintre oraşe.
Să se scrie un program C care verifică dacă un graf este conex şi să se afişeze toate componentele sale conexe.
#include "stdio.h"
#include "conio.h"
int n,m,a[20][20],viz[20],nrc=0;
void viziteaza(int nod)
{
int i;
viz[nod]=nrc;
for(i=1;i <= n;i++)
if(a[nod][i] == i && viz[i] == 0)
viziteaza(i);
}
void main()
{
int nod,i,j,x,y;
printf("Introdu numărul de noduri:");
scanf("%d",&n);
printf("Introdu numărul de muchii:");
scanf("%d",&m);
for(i=1;i <= n;i++)
for(j=1;j <= n;j++)
a[i][j]=0;
printf("Introdu muchiile :\n");
for(i=1;i <= m;i++)
{
printf("De la nodul: ");
scanf("%d",&x);
printf("la nodul: ");
scanf("%d",&y);
a[x][y]=a[y][x]=1;
}
for(nod=1;nod <= n;nod++)
if(viz[nod] == 0)
{
nrc++;
viziteaza(nod);
}
if(nrc == 1)
printf("Graful este conex!\n");
else
printf("Graful nu este conex!\n");
printf("Componentele conexe sunt:\n");
for(i=1;i <= nrc;i++)
{
printf("Componenta %d:",i);
for(j=1;j <= n;j++)
if(viz[j] == i)
printf("%d ",j);
putchar("\n");
}
getch();
}
Grafuri neorientate – parcurgerea in adancime
Implementarea parcurgerii în adâncime pentru un graf neorientat
#include
#include
int a[20][20],n,i,j;
void parc_adancime()
{
int s[40],varf,k,nod,urm[20],viz[20],in;
printf("Introduceti nodul iniţial de pornire= ");
scanf("%d",&in);
for (nod=1;nod <= n;nod++)
{
urm[nod]=0;
viz[nod]=0;
}
varf=1;
//şirul s va păstra ordinea de traversare în adâncime;
//introducem nodul de start în acest şir
s[varf]=in;
//marcăm nodul de pornire ca vizitat
viz[in]=1;
//afişăm nodul de start ca prim nod în traversarea în adâncime
printf("%d ",in);
while (varf >= 1)
{
//nod va fi nodul căruia îi mai căutăm succesori
nod=s[varf];
//k va conţine numărul nodului de unde reîncepem să
// căutam succesori pentru nodul nod
k=urm[nod]+1;
while ((k <= n) && ((a[nod][k] == 0) || ((a[nod][k]==1)&&(viz[k]==1))))
{
k++;
urm[nod]=k;
}
if (k == n+1)
vârf--;
else
{
varf++;
s[varf]=k;
viz[k]=1;
printf("%d", s[varf]);
}
}
putchar("\n");
}
void main()
{
int m,i,j,x,y;
printf("Introduceti numărul de noduri n=");
scanf("%d",&n);
printf("Introduceti numărul de muchii m=");
scanf("%d",&m);
for(i=1;i <= n;i++)
for(j=1;j <= n;j++)
a[i][j]=0;
for(i=1;i <= m;i++)
{
printf("De la nodul:");
scanf("%d",&x);
printf("La nodul:");
scanf("%d",&y);
a[x][y]=a[y][x]=1;
}
parc_adancime();
getch();
}
Metoda Divide et Impera – Problema cautarii binare
Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.
Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.
Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:
1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.
Se citeşte un şir de n elemente numere întregi ordonate crescător şi o valoare întreagă key. Să se decidă dacă valoarea key se găseşte printre valorile şirului de elemente şi în caz afirmativ să se tipărească indicele componentei care conţine acea valoare.
#include "stdio.h"
int a[10],n,key;
void caut(int i, int j)
{
if(key == a[(i+j)/2])
printf("Valoarea a fost gasita la indicele %d\n",(i+j)/2);
else
if(i < j)
if(nr < a[(i+j)/2])
caut(i, (i+j)/2-1);
else
caut((i+h)/2+1,j);
}
Continue reading
Metoda Divide et Impera – Problema Turnurilor din Hanoi
Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.
Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.
Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:
1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.
Legenda acestei probleme spune că Brahma a fixat pe Pământ trei tije de diamante şi pe una din ele a pus în ordine crescătoare 64 de discuri de aur de dimensiuni diferite, cu discul cel mai mare jos. Singura operaţiune permisă călugărilor era mutarea a câte unui singur disc de pe o tijă pe alta, astfel încât niciodată să nu se pună un disc mai mare peste unul mai mic. Legenda spune că atunci când călugării vor muta toate cele 64 de discuri respectând regulile de maa sus, atunci va veni sfârşitul lumii. Presupunând că în fiecare secundă se mută un disc, lucrând fără întrerupere, cele 64 de discuri nu pot fi mutate nici în 500 de miliarde de ani de la începutul acţiunii!
Vom considera trei tije verticale notate Stânga, Mijloc, Dreapta. Pe tija Stânga se găsesc aşezate n discuri de diametre diferite, în ordinea descrescătoare a diametrelor, privind de jos în sus. Iniţial, tijele Mijloc şi Dreapta sunt goale. Să se afişeze toate mutările prin care discurile de pe tija Stânga se mută pe tija Mijloc, în aceeaşi ordine, respectând următoarele reguli:
• la fiecare mişcare se mută un singur disc
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic
• un disc mai mare nu poate fi plasat peste un disc cu diametrul mai mic
Continue reading
Metoda Divide et Impera – Suma elementelor unui sir
Prezentare generala:
Divide et Impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.
Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.
Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:
1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.
#include "stdio.h"
#incude "conio.h"
int a[20];
int divide(int ls, int ld)
{
int mijloc,d1,d2;
if(ls != ld)
{
mijloc=(ls+ld)/2;
d1=divide(ls, mijloc);
d2=divide(mijloc+1,ld);
return(d1+d2);
}
else
return(a[ls]);
}
Continue reading
Backtracking – problema mingii
Se dă un teren parcelat cu porţiuni de teren pătrate, fiecare având o anumită cotă. Cotele se citesc de la tastatură şi se reţin într-o matrice de m/n poziţii. O bilă se găseşte într-o poziţie iniţială, având nişte coordonate iniţiale ce se citesc de la tastatură. Se ştie că bila poate sări de la o cotă mai mare spre o cotă mai mică, pe orizontală, verticală şi pe diagonale, rostogolindu-se astfel către marginea terenului. Se cere să se afişeze toate variantele de deplasare a mingii până la atingerea unei margini.
#include "stdio.h"
#include "conio.h"
int a[8]={1,1,0,-1,-1,-1,0,1}, b[8]={0,1,1,1,0,-1,-1,-1};
//tablou va păstra cotele iar drum drumul
//parcurs de minge (folosind valori 0 şi 1)
int tablou[10][10],drum[10][10],m,n;
//funcţia de afişare a soluţiei void afiseaza(void)
{
int p,r;
for(p=0;p < m;p++)
{
for(r=0;r < n;r++)
printf("%d",drum[p][r]);
putchar("\n");
}
putchar("\n");
getch();
}
Continue reading
Backtracking – combinari
Se citesc 2 numere naturale nenule k,n unde k < n. Să se afişeze toate combinările a k numere din mulţimea (1,2,. ..n}.
#include “stdio.h”
#include “conio.h”
int m,n,a[20];
//funcţia de afişare a soluţiei
void scrie(void)
{
int i;
for(i=0;i < n;i++)
printf("%d ",a[i]+1);
//deoarece lucrăm cu indici de la 0, vom adăuga 1 la valorile rezultate
putchar("\n");
}
//funcţia recursivă de generare a combinărilor
void comb(int k)
{
int i;
//vom încerca să aşezăm pe poziţia curentă, pe rând, toate valorile de la 0 la m-1
for(i=0;i < m;i++)
//încercăm pe poziţia curentă valoarea i
{
a[k]=i;
//dacă este prima valoare aşezată sau dacă ea este mai mare decât
//precedenta putem continua; în caz contrar vom încerca o altă valoare
//a lui i pe poziţia curentă
if((k == 0)||(a[k] > a[k-1]))
if(k == n-1)
//dacă am aşezat n valori (de la 0 la n-1) am ajuns la soluţie
scrie();
else
//dacă nu, apelăm funcţia de aşezare a următoarei poziţii
comb(k+1);
}
}
void main(void)
{
printf(“Introdu pe m:”);
scanf(“%d”,&m);
printf(“Introdu pe n:”);
scanf(“%d”,&n);
//apelăm funcţia recursivă comb încercând să aşezăm primul element
comb(0);
getch();
}
