[Link]-o sala, intr-o zi, trebuie planificate n spectacole.

Pentru fiecare spectacol se cunoaste intervalul

in care se desfasoara [st,sf]. Se cere sa se planifice un numar maxim de spectacole astfel incat sa nu
se suprapuna.
#include<iostream>
using namespace std;
int s[2][10],o[10],n,i,h1,m1,h2,m2,ora;
void sortare()
{
int gata,m,i;
do
{
gata=1;
for(i=1;i<=n-1;i++)
if(s[1][o[i]]>s[1][o[i+1]])
{
m=o[i];
o[i]=o[i+1];
o[i+1]=m;
gata=0;
}
}
while(!gata);
}
main()
{
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
o[i]=i;
cout<<"ora de inceput pentru spectacolul"<<i<<" (hh mm)=";
cin>>h1>>m1;

s[0][i]=h1*60+m1;
cout<<"ora de sfarsit pentru spectacolul"<<i<<" (hh mm)=";
cin>>h2>>m2;
s[1][i]=h2*60+m2;
}
sortare();
cout<<"ordinea spectacolelor este "<<endl<<o[1]<<endl;
ora=s[1][o[1]];
for(i=2;i<=n;i++)
if(s[1][o[1]]>=ora)
{
cout<<o[i]<<endl;
ora=s[1][o[i]];

}
2. Un comis-voiajor pleaca dintr-un oras, trebuie sa viziteze un numar de orase si sa nu se intoarca in
orasul de unde a plecat cu efort minim. Orice oras i este legat printr-o sosea de orice alt oras j printrun drum de A[i,j] [Link] cere traseul pe care trebuie sa-l urmese comis-voiajorul, astfel incat sa
parcurga un numar minim de kilometri.
#include <iostream>
using namespace std;
int s[10],a[10][10],n,i,j,v,p,vs,vs1,mint,cost;
main()
{

cout<<"Numar noduri=";cin>>n;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
cout<<"A["<<i<<"]["<<j<<"]=",cin>>a[i][j],a[j][i]=a[i][j];

cout<<"Nod de pornire:";cin>>v; s[v]=1;

vs1=v;
cout<<"Drumul trece prin:"<<v<<' ';
p=v;
for(i=1;i<n;i++)
{
mint=3000;
for(j=1;j<=n;j++)
if(a[v][j]!=0&&s[j]==0&&mint>a[v][j])
{
mint=a[v][j];
vs=j;
}
cost+=a[v][vs];
cout<<vs<<' ';
s[vs]=1;
v=vs;
}
cout<<p;
cost+=a[vs1][v];
cout<<endl<<"Cost="<<cost;

}
3. Se efectueaza plata unei sume s utilizand un numar minim de monezi. Se cunosc valorile
monezilor.
#include<iostream>
using namespace std;
int n,i,man,inv,s,a[100];
main()
{
cout<<"Suma=";cin>>s;

cout<<"Numarul de bancnote:";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"a["<<i<<"]=";cin>>a[i];
}
do
{
inv=0;
for(i=1;i<=n-1;i++)
if(a[i]<a[i+1])
{
man=a[i];
a[i]=a[i+1];
a[i+1]=man;
}
}
while(inv);
i=1;
cout<<s<<endl;
do
{
if(s/a[i]>0)
cout<<s/a[i]<<" bancnote cu valoarea "<<a[i]<<endl,s=s%a[i];
i++;
}
while(i<=n);
}
4. Se considera o multime de n numere reale. Se cere o submultime a sa cu un numar maxim de
elemente, astfel incat suma elementelor sale sa fie maxima
#include<iostream>
using namespace std;

float A[100],B[100];
int n,m,i;
void Greedy()
{
for(i=1;i<=n;i++)
if(A[i]>=0)
{
m++;
B[m]=A[i];
}
}
main()
{
cout<<"n=";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"A["<<i<<"]=";
cin>>A[i];
}
Greedy();
for(i=1;i<=m;i++)
cout<<B[i]<<" "
}
5. Programul construieste si, apoi tipareste,
o lista de valori intregi, de tip coada,
dupa care construieste cu valorile din lista
o alta lista ordonata, pe care o afiseaza

#include <stdio.h>
#include <stdlib.h>

#include <conio.h>
void main()
{
struct intrare
{
int

valoare;

struct intrare *urmator;

};
struct intrare *start, *ptr_lista, *pp, *pc, *plo, *vr;
int valoare, inv;
start = NULL;
clrscr();
printf ("Introduceti un sir de valori, terminat cu 0.\n");
printf ("Valoare:");
scanf ("%d", &valoare);
while ( valoare )
{
if ( start == NULL )
{
start = ( struct intrare * ) malloc( sizeof (struct intrare ));
/* se poate utiliza si functia new in loc de malloc */
start-> valoare = valoare;
start-> urmator = NULL;
ptr_lista = start;
}
else
{
ptr_lista ->urmator=(struct intrare*)
malloc(sizeof(struct intrare));
if ( ptr_lista -> urmator != NULL )

/* se adauga la lista*/

{
ptr_lista = ptr_lista -> urmator;
ptr_lista -> valoare = valoare;
ptr_lista -> urmator = NULL;
}
else
exit (0);
}
printf ("Valoare:");
scanf ("%d", &valoare);
}
/* afisare lista */
printf("\nLista introdusa:\n");
ptr_lista = start; /* initializare adresa de inceput a listei */
if ( ptr_lista != NULL )
{
do
{
printf ("(%d) -> ", ptr_lista -> valoare);
ptr_lista = ptr_lista -> urmator;
} while ( ptr_lista != NULL );
printf ("NULL\n");
}
else
printf ("Lista vida ( NULL )\n");
printf("\nApasati o tasta pentru a ordona lista\n");
getch();

/* construire lista ordonata */

if (!start)

exit(1);
if (start) // copiez primul element din lista init in cea ordonata
{
vr=(struct intrare *) malloc( sizeof (struct intrare ));
vr-> valoare = start->valoare;
vr-> urmator = NULL;
plo=vr;
}
ptr_lista=start->urmator; // se continua in lista init cu elem urmator
while (ptr_lista)
{
pc=plo;
pp=NULL;
while (pc && ptr_lista->valoare > pc->valoare){
pp=pc;
pc=pc->urmator;
}
// s-a gasit pozitia de inserat intre pp si pc!
vr=(struct intrare *) malloc( sizeof (struct intrare ));
vr->valoare = ptr_lista->valoare;
if (!pp){plo=vr;
}
else
pp->urmator=vr;
vr->urmator = pc;
ptr_lista=ptr_lista->urmator;
};

/* afisare lista ordonta*/

printf("\nLista ordonata:\n");

ptr_lista = plo; /* initializare adresa de inceput a listei */

if ( ptr_lista != NULL )
{
do
{
printf ("(%d) -> ", ptr_lista -> valoare);
ptr_lista = ptr_lista -> urmator;
} while ( ptr_lista != NULL );
printf ("NULL\n");
}
else
printf ("Lista vida ( NULL )\n");

printf("\nApasati o tasta pentru termina programul\n");

getch();

}
6. Programul construieste, apoi tipareste,
o lista de valori intregi, de tip coada,
dupa ordoneaza valorile in aceasta lista si o afiseaza

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void main()
{
struct intrare
{
int

valoare;

struct intrare *urmator;

};
struct intrare *start, *ptr_lista, *start_lo, *pp, *pc, *plo;
int valoare, inv;
start = NULL;
clrscr();
printf ("Introduceti un sir de valori, terminat cu 0.\n");
printf ("Valoare:");
scanf ("%d", &valoare);
while ( valoare )
{
if ( start == NULL )
{
start = ( struct intrare * ) malloc( sizeof (struct intrare ));
/* se poate utiliza si functia new in loc de malloc */
start-> valoare = valoare;
start-> urmator = NULL;
ptr_lista = start;
}
else
{
ptr_lista ->urmator=(struct intrare*)
malloc(sizeof(struct intrare));
if ( ptr_lista -> urmator != NULL )
{
ptr_lista = ptr_lista -> urmator;
ptr_lista -> valoare = valoare;
ptr_lista -> urmator = NULL;
}
else
exit (0);

/* se adauga la lista*/

}
printf ("Valoare:");
scanf ("%d", &valoare);
}
/* afisare lista */
printf("\nLista introdusa:\n");
ptr_lista = start; /* initializare adresa de inceput a listei */
if ( ptr_lista != NULL )
{
do
{
printf ("(%d) -> ", ptr_lista -> valoare);
ptr_lista = ptr_lista -> urmator;
} while ( ptr_lista != NULL );
printf ("NULL\n");
}
else
printf ("Lista vida ( NULL )\n");
printf("\nApasati o tasta pentru a ordona lista\n");
getch();

/* construire lista ordonata */

plo=start;

// pointer la inceputul listei ordonate

if (plo)
{
do
{inv=0;
pc=plo;
pp=NULL;
while (pc->urmator){

pp=pc;
pc=pc->urmator;
if (pp->valoare > pc->valoare){
valoare=pp->valoare;
pp->valoare=pc->valoare;
pc->valoare=valoare;
inv=1;
}
}
}while(inv);

}
/* afisare lista ordonta*/
printf("\nLista ordonata:\n");
ptr_lista = plo; /* initializare adresa de inceput a listei */
if ( ptr_lista != NULL )
{
do
{
printf ("(%d) -> ", ptr_lista -> valoare);
ptr_lista = ptr_lista -> urmator;
} while ( ptr_lista != NULL );
printf ("NULL\n");
}
else
printf ("Lista vida ( NULL )\n");

printf("\nApasati o tasta pentru termina programul\n");

getch();

}
7. Programul construieste si, apoi tipareste,
o lista de valori intregi, de tip coada,
dupa care modifica lista (legaturile),
astfel incat valorile sa fie ordonate, si o afiseaza

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void main()
{
struct intrare
{
int

valoare;

struct intrare *urmator;

};
struct intrare *start, *ptr_lista, *pp, *pc, *plo, *vr;
int valoare, inv;
start = NULL;
clrscr();
printf ("Introduceti un sir de valori, terminat cu 0.\n");
printf ("Valoare:");
scanf ("%d", &valoare);
while ( valoare )
{
if ( start == NULL )
{
start = ( struct intrare * ) malloc( sizeof (struct intrare ));
/* se poate utiliza si functia new in loc de malloc */
start-> valoare = valoare;

start-> urmator = NULL;

ptr_lista = start;
}
else
{
ptr_lista ->urmator=(struct intrare*)
malloc(sizeof(struct intrare));
if ( ptr_lista -> urmator != NULL )

/* se adauga la lista*/

{
ptr_lista = ptr_lista -> urmator;
ptr_lista -> valoare = valoare;
ptr_lista -> urmator = NULL;
}
else
exit (0);
}
printf ("Valoare:");
scanf ("%d", &valoare);
}
/* afisare lista */
printf("\nLista introdusa:\n");
ptr_lista = start; /* initializare adresa de inceput a listei */
if ( ptr_lista != NULL )
{
do
{
printf ("(%d) -> ", ptr_lista -> valoare);
ptr_lista = ptr_lista -> urmator;
} while ( ptr_lista != NULL );
printf ("NULL\n");

}
else
printf ("Lista vida ( NULL )\n");
printf("\nApasati o tasta pentru a ordona lista\n");
getch();

/* se ordoneaza lista */
if (!start)
exit(1);
ptr_lista=start; // se init cu primul element
vr=ptr_lista->urmator;
plo=ptr_lista;

// plo - pointer la lista ordonata, initial primul

ptr_lista->urmator=NULL;
ptr_lista=vr;
while (ptr_lista)
{
pc=plo;
pp=NULL;
while (pc && ptr_lista->valoare > pc->valoare){
pp=pc;
pc=pc->urmator;
}
// s-a gasit pozitia de inserat intre pp si pc!
vr=ptr_lista->urmator; // memorez noua adresa de inceput a list neord
if (!pp){ptr_lista->urmator=plo;
plo=ptr_lista;
}
else
{pp->urmator=ptr_lista;
ptr_lista->urmator = pc;

}
ptr_lista=vr;
};

/* afisare lista ordonta*/

printf("\nLista ordonata:\n");
ptr_lista = plo; /* initializare adresa de inceput a listei */
if ( ptr_lista != NULL )
{
do
{
printf ("(%d) -> ", ptr_lista -> valoare);
ptr_lista = ptr_lista -> urmator;
} while ( ptr_lista != NULL );
printf ("NULL\n");
}
else
printf ("Lista vida ( NULL )\n");

printf("\nApasati o tasta pentru termina programul\n");

getch();

}
8. S se scrie un tip structur pentru reprezentarea unei liste nlnuite, prin

intermediul creia se vor reine valori textuale pentru afiarea unui mesaj. Lista
va conine 3 elemente.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
//scriem o structura pentru reprezentarea unul nod (element) al listei
struct nod_lista{

char* inf;
nod_lista* next;
};
//construim un tip propiu pentru reprezentarea unui nod de lista pe baza structurii definite anterior
typedef struct nod_lista nod;
//functia principala in rulare
void main()
{
nod* a; //primul element al listei
a=(nod*)malloc(sizeof(nod));
a->inf="Salut"; //continutul primului element

nod* b; //al doilea element al listei

b=(nod*)malloc(sizeof(nod));
a->next=b; //urmatorul element al primului element
b->inf="limbajul";

nod* c; //al treilea element al listei

c=(nod*)malloc(sizeof(nod));
b->next=c;
c->inf="C/C++!";
c->next=NULL; //sau c->next=0;

while(a) //a!=NULL sau a!=0

{
printf("%s ",a->inf);
a=a->next;
}
getch();
}

9. Arbore, construit recursiv, ce contine cuvinte, si numarul

de aparitie a acestora, citite de la tastatura (cate un cuvant pe linie)
introducerea cuvintelor se termina cu un cuvant vid (Enter la inceputul
liniei), si apoi sunt afisate cuvintele in ordine alfabetica.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define LUNGMAX 20
struct st_arbore
{
char *cuvant; /* pointer la cuvantul citit */
int nrap; /* numarul de aparitii */
struct st_arbore *st, *dr;
};
int nle=0;

void actualizare (struct st_arbore * arb , char *cuv){

/* Functia actualizeaza arborele binar.
Daca cuvantul nu a mai fost citit se creaza un nou nod,
altfel se incrementeaza contorul de aparitii al
nodului corespunzator cuvantului citit anterior.
Se determina pe care ramura a arborelui se va insera
cuvantul, sau daca exista deja
*/
if (strcmp(cuv, arb->cuvant) < 0)
if (arb->st)
actualizare (arb->st, cuv);
else

{
arb->st=(struct st_arbore *) malloc (sizeof(struct st_arbore)) ;

arb=arb->st;
arb->cuvant=cuv;
arb->nrap=1;
arb->st=NULL;
arb->dr=NULL;
}
else if (strcmp(cuv, arb->cuvant) >0 )
if(arb->dr)
actualizare (arb->dr, cuv);
else

{
arb->dr=(struct st_arbore *) malloc (sizeof(struct st_arbore)) ;
arb=arb->dr;
arb->cuvant=cuv;
arb->nrap=1;
arb->st=NULL;
arb->dr=NULL;
}

else
arb->nrap=arb->nrap + 1;
}

void tiparire_arbore (struct st_arbore *arbo)

/* functia afiseaza arborele de cautare ce contine cuvinte si
numarul lor de aparitii */
{
if (arbo!=NULL)
{
tiparire_arbore (arbo->st) ; /* tiparire arbore stanga */
printf ("%s (ap: %d)\n", arbo -> cuvant, arbo -> nrap ) ;

nle++;
if (nle%24==0){
printf("Apasati o tasta pentru a continua afisarea!\n");
getch();
}
tiparire_arbore (arbo->dr) ; /* tiparire arbore dreapta */
}
}
void main ()
{struct st_arbore *arb;
char cuvant[LUNGMAX] ;
clrscr();
printf("Introduceti cuvinte, care vor fi apoi tiparite in ordine"
" alfabetica:\n");
gets(cuvant) ;
arb=(struct st_arbore *) malloc (sizeof(struct st_arbore)) ;
/* am presupus ca nu se returneaza de catre malloc
valoarea NULL */
arb->cuvant=strdup(cuvant);
arb->nrap=1;
arb->st=NULL;
arb->dr=NULL;
gets(cuvant) ;
while (strcmp(cuvant, ""))
{actualizare (arb, strdup(cuvant));
gets(cuvant);
}
printf("Lista ordonata a cuvintelor (numar aparitii):\n");
tiparire_arbore (arb);
}

10. Se construieste un Arbore de cuvinte cu retinerea nr de aparitii

pt fiecare cuvant introdus
la constructie se va apasa enter daca nu se doreste a se introduce
informatie in nod

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
int ok;
struct arbore
{
char info[30];
int nr_ap, niv;
struct arbore *st, *dr;
};

struct arbore *tata_lor;

void parcurge(struct arbore *p, char s[30] )

{
if (p)
{
if (!strcmp(p->info,s))
{ p->nr_ap++;
ok=1;
}

parcurge(p->st,s);
parcurge(p->dr,s);

}
}

void creare(struct arbore *&p)

{
char s[30];
printf("Dati info nodului: ");
gets(s);
if (strlen(s))
{ ok=0;
parcurge(tata_lor,s);
if(ok==0)
{ p=new arbore;
strcpy(p->info,s);
p->st=NULL; p->dr=NULL;
p->nr_ap=1;
creare(p->st);
creare(p->dr);
}

}
}

void afis(struct arbore *p)

{
if (p)
{ afis(p->st);
printf("Nodul cu info %s apare de %d ori.\n",p->info,p->nr_ap);
afis(p->dr);
}

void main()
{
clrscr();
creare(tata_lor);
afis(tata_lor);
getch();
}
11. Arbore de nr in care cautam o valoare si returnam pointer la valoarea
respectiva daca a fost gasita. Programul mai verifica daca arborele
este echilibrat. La constructie se va introduce 0 pt back

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct arbore
{
int info;
struct arbore *st,*dr;
};

void creare(struct arbore *&p)

{
int n;
printf("Dati info nodului: ");
scanf("%d",&n);
if (n)
{

p=new arbore;
p->info=n; p->st=NULL; p->dr=NULL;
creare(p->st);
creare(p->dr);
}
}

arbore* cauta_val(struct arbore *p, int val)

{
if (p)
{
if (p->info==val)
return p;
cauta_val(p->st,val);
cauta_val(p->dr,val);
}
}

void echilibrat(struct arbore *p, int n, int *nr)

{
if (p)
{
if (n>*nr) *nr=n;
echilibrat(p->st,n+1,nr);
echilibrat(p->dr,n+1,nr);
}
}

void main()
{

struct arbore *tata_lor, *q=NULL;

int x, niv_dr=0, niv_st=0;
clrscr();
creare(tata_lor);
printf("Dati valoarea care trebuie cautata: ");
scanf("%d",&x);
q=cauta_val(tata_lor,x);
if (q) printf("Valoarea a fost gasita la adresa %p\n",q);
else printf("Valoarea nu a fost gasita.\n");

echilibrat(tata_lor->st,1,&niv_st);
echilibrat(tata_lor->dr,1,&niv_dr);
if (abs(niv_st-niv_dr)<=1) printf("Arborele este echilibrat.\n");
else printf("Arborele nu e echilibrat.\n");
getch();
}
12. Se numara nr de noduri si frunze dintr_un arbore binar de nr intregi
se det latimea maxima
la constructie se va introduce 0 pt back

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct arbore
{
int info;
struct arbore *st, *dr;
};

void creare(struct arbore *&p)

{
int n;
printf("Dati info nodului:");
scanf("%d",&n);
if (n)
{
p=(struct arbore*) malloc(sizeof(struct arbore));
p->info=n;
p->st=NULL; p->dr=NULL;
creare(p->st);
creare(p->dr);
}
}

void numara(struct arbore *p, int *noduri, int *frunze)

{
if (p)
{
*noduri+=1;
if (!p->st && !p->dr) *frunze+=1;
numara(p->st,noduri,frunze);
numara(p->dr,noduri,frunze);
}
}
int NNN (arbore *r, int n) /* numar noduri de pe nivelul n */
{ if (!r)
return 0;
if (n == 0)
return 1;

return NNN(r->st, n-1) + NNN(r->dr, n-1);

}

void main()
{int x[100],max,i;
int nr_noduri=0, nr_frunze=0;
struct arbore *tata_lor;
clrscr();
creare(tata_lor);
numara(tata_lor,&nr_noduri,&nr_frunze);
for(i=1;i<=20;i++)
x[i]=NNN(tata_lor,i);
max=x[1];
for(i=1;i<=20;i++)
if(x[i]>max)
max=x[i];

printf("Arborele are %d noduri.\n", nr_noduri);

printf("Arborele are %d frunze.\n", nr_frunze);
printf("Arborele are latimea maxima de %d.\n",max);
getch();
}
13. O stiva de containere (cod, continut, data ambalarii,greutate)
se simuleaza activ de adaugare si extragere a containerelor din coada

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

int max=20,nc;

typedef struct dataa

{
int zi,luna,an;
}data;

typedef struct structura

{
int cod,greutate;
char continut[20];
data datta;
structura *leg;
}container;

int push(container *&varf)

{container *p;
clrscr();
if(nc+1>max)
{ printf("La coada nu mai pot fi adaugate containere!");
getch();
return(0);
}
else
{ p=new container;
if(p==NULL)
{ printf("\nAlocare esuata!\n");
return(0);
}

printf("Introduceti datele pt container : ");

printf("\nCod container: "); scanf("%d",&p->cod);
printf("\nContinut container: "); fflush(stdin); gets(p->continut);
printf("\nData ambalarii: "); scanf("%d/%d/%d",&p->[Link],&p->[Link],&p->[Link]);
printf("\nGreutate :"); scanf("%d",&p->greutate);
p->leg=varf;
varf=p;
return(1);
}
}
int pop (container *&varf, int codd)
{ container *p,*q;
p=varf;
while(p)
{ if(p->leg->cod==codd)
{ q=p->leg;
printf("\nContainerul cu codul %d, ce continea %s, ambalat la %d/%d/%d cu greutate de %d
kg a parasit coada!",q->cod,q->continut,q->[Link],q->[Link],q->[Link],q->greutate);
p->leg=q->leg;
free(q);
getch();
return(0);
}
p=p->leg;
}
if(varf==NULL)
{ printf("\nCoada este goala!");
getch();
}
return(1);

}
void afisare(container *varf)
{container *p;
clrscr();
p=varf;
if(p==NULL)
printf("Coada este nula!\n");
else
{ printf("\nComponenta cozii :");
while(p)
{ printf("\nContainerul cu codul %d, contine %s, ambalat la %d/%d/%d cu greutate de %d",p>cod,p->continut,p->[Link],p->[Link],p->[Link],p->greutate);
p=p->leg;
}
}
getch();
}

void main (void)

{
int codd,ok;
char c;
container *varf=NULL;
clrscr();
printf("Apasati tasta s pt adaugarea unui container in coada.\n");
printf("Apasati tasta l pt extragerea unui container din coada.\n");
printf("Apasati tasta a pt afisarea cozii.\n");
printf("Apasati tasta q pt iesire din program.\n");
printf("Dati optiunea dvs:");
while ((c=getch())!='q')
{

if (c=='s' || c=='S') { ok=push(varf);

if(ok==0)
printf("Containerul nu a putut fi adaugat");
}
else
if (c=='l' || c== 'L')
{ codd=-1;
while(pop(varf,codd))
{ clrscr();
printf("Introduceti codul containerul ce doriti a fi extras: ");
scanf("%d",&codd);
}
}
else
if(c=='a'|| c=='A') afisare(varf);
clrscr();
printf("Apasati tasta s pt adaugarea unui container in coada.\n");
printf("Apasati tasta l pt extragerea unui container din coada.\n");
printf("Apasati tasta a pt afisarea cozii.\n");
printf("Apasati tasta q pt iesire din program.\n");
printf("Dati optiunea dvs:");
}
}
14. Prog. construieste o stiva de numere intregi, distincte,
pe care o afiseaza, utilizand functiile: adauga_stiva si afisare_stiva

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

struct

s_stiva
{
int

valoare;

int nr_aparitii; /* numarul de aparitii ale numarului in stiva */

struct s_stiva *urmator;
};

struct s_stiva *adauga_stiva (struct s_stiva *ultimul, int val)

{
/*Functia returneaza un pointer la ultimul element din stiva daca s-a putut
adauga un nou element, sau NULL daca nu s-a adaugat ("Memorie plina!") */
struct

s_stiva *ptr_stiva;

if (ultimul==NULL)
{
ultimul=(struct s_stiva *) malloc(sizeof(struct s_stiva));
if (ultimul==NULL)
{printf("Memorie plina!\n");
return(NULL);
}
else
{
ultimul->valoare=val;
ultimul->nr_aparitii=1;
ultimul->urmator=NULL;
return(ultimul);
}
}
else
{

ptr_stiva=ultimul;

/* se cauta daca exista valoarea */

while(ptr_stiva->valoare!=val && ptr_stiva->urmator!=NULL)

ptr_stiva=ptr_stiva->urmator;
if(ptr_stiva->valoare==val)
{ptr_stiva->nr_aparitii++;
return(ultimul);
}
else
{ptr_stiva=(struct s_stiva *)malloc(sizeof(struct s_stiva));
if (ptr_stiva==NULL)
{printf("Mmeorie plina!\n");
return(NULL);
}
else
{ptr_stiva->valoare=val;
ptr_stiva->nr_aparitii=1;
ptr_stiva->urmator=ultimul;
return(ptr_stiva);
}
}
}
}

void afisare_stiva(struct s_stiva *ultim)

{
int nr_val_linie = 0;
while (ultim!=NULL)
{
printf("%2d(%d)-> ", ultim->valoare, ultim->nr_aparitii);
ultim=ultim->urmator;

nr_val_linie++; /* contor pentru nr. de valori afisate pe linie */

if (nr_val_linie%8==0)
printf("\n");
}
printf ("\n");
}

void eliberare_spatiu (struct s_stiva *ptrs){

struct s_stiva *p=ptrs;
while(p){ptrs=p;
p=p->urmator;
free(ptrs);
}
}

void main()
{
struct s_stiva *ultim=NULL;
int numar;
clrscr();
printf("Prg. construieste si afiseaza o stiva de nr. intregi, distincte.\n");
printf("Introducerea se termina cu EOF(CTRL-Z, ENTER.\n");
printf("Introduceti numar: ");
while(scanf("%d", &numar)!=EOF)
{if((ultim=adauga_stiva(ultim, numar))==NULL)
break;
printf("Introduceti numar: ");
}
afisare_stiva(ultim);
eliberare_spatiu(ultim);

}
15. Programul construieste o stiva de caractere, pe care apoi o tipareste.

#include <stdio.h>
struct st_lista
{
char

car;

struct st_lista *urmator;

};
void main()
{
struct st_lista *vr, *primul;
char c;
primul = NULL;
printf("\nProgramul construieste si afiseaza o stiva de caractere.\n");
printf("Introduceti caractere (CTRL-Z, Enter-pentru sfarsit):\n");
fflush(stdin);
while ((c=getchar()) != EOF)
if (c!='\n')
{vr=(struct st_lista *) malloc(sizeof(struct st_lista));
if (vr == NULL)
{ /* daca pointerul returnat de functia malloc() este
NULL */
printf("Memorie plina !!!!!!\n");
mesaj de eroare */
break;
caractere */
}
vr->car=c;
vr->urmator=primul;
primul=vr;

/* se tipareste un

/* si se termina executia ciclului de citire

}
vr=primul;

/* initializare pointer curent, vr, pentru a referi

primul caracter */

while (vr != NULL)

{
printf("%c -> ", vr->car);
vr=vr->urmator;
}
printf(" NULL");/* tiparire sfarsit lista caractere sau lista vida daca
primul era NULL */
}
16. Programul construieste o stiva de caractere distincte, pe care apoi o tipareste.

#include <stdio.h>
struct st_lista
{
char

car;

struct st_lista *urmator;

};
void main()
{
struct st_lista *vr, *primul;
char c;
int distinct (struct st_lista *prim, char ch);
primul = NULL;
printf("\nProgramul construieste si afiseaza o stiva de caractere.\n");
printf("Introduceti caractere (CTRL-Z, Enter-pentru sfarsit):\n");
fflush(stdin);
while ((c=getchar()) != EOF)
if (c != '\n' && (distinct(primul, c)))

{
vr=(struct st_lista *) malloc(sizeof(struct st_lista));
if (vr == NULL)
{

/* daca pointerul returnat de functia

malloc() este NULL */

printf("Memorie plina !!!!!!\n");

eroare */

/* mesaj de

break; /* si se termina executia ciclului de citire

caractere */
}
vr->car=c;
vr->urmator=primul;
primul=vr;
}
vr=primul;

/* initializare pointer curent, vr, pentru a referi

primul caracter */

while (vr != NULL)

{
printf("%c -> ", vr->car);
vr=vr->urmator;
}
printf(" NULL");/* tiparire sfarsit lista caractere sau lista vida daca
primul era NULL */
}
int distinct (struct st_lista *prim, char ch)
{
struct st_lista *ptr;
int gasit;
ptr=prim;

/* initializare pointer curent cu primul din lista */

gasit=0;/* presupunem ca nu l-am gasit inca */

while (ptr != NULL && !gasit)

/* cat timp nu s-a terminat lista si nu

l-am gasit */
{

/* se continua parcurgerea listei */

gasit=(ptr->car == ch);
ptr=ptr->urmator;
}
return (!gasit);
}
17. Programul permuta liniile dintr-o matrice pentru a ordona
crescator valorile de pe diagonala principala a matricei.

#include <stdio.h>
#include <conio.h>
#define NR_MAX 3
int a[NR_MAX][NR_MAX];
int nl, nc, l, c;
int ntotsol=0; // numarul total de solutii

void main (void)

{
int lin, col, il, ic, aux;
int incearca (int);
clrscr();
printf("Programul ordoneaza valorile de pe diagonala unei matrici.\n");
printf("Numar de linii/coloane: ");
scanf("%d%d", &nl, &nc);
printf("\n");
for (l=0; l<nl; l++)
for (c=0; c<nc; c++)
{
printf("a[%d,%d]=", l+1, c+1);

scanf("%d", &a[l][c]);
};
printf("\nApasati o tasat pentru a continua programul\n");
getch();
for (l=0; l<nl; l++)
for (c=0; c<nc; c++)
{// se aduce linia 'l' si coloana 'c' pe pozitia (0,0)
for (col=0; col<nc; col++)
{aux=a[0][col];
a[0][col]=a[l][col];
a[l][col]=aux;
};
for (lin=0; lin<nl; lin++)
{
aux=a[lin][0];
a[lin][0]=a[lin][c];
a[lin][c]=aux;
};
if (incearca(0)) // daca exista solutie (ord. diagonala)
ntotsol++;

// se numara solutia si se tipareste

printf("\nSolutia %d:\n", ntotsol);

for (il=0; il<nl; il++)
{
for (ic=0; ic<nc; ic++)
printf("%4d", a[il][ic]);
printf("\n");
};
printf("\nApasati o tasta pentru a continua programul !\n");
getch(); // se duc la loc linia si coloana mutate anterior
for (col=0; col<nc; col++)

{aux=a[0][col];
a[0][col]=a[l][col];
a[l][col]=aux;
};
for (lin=0 ;lin<nl; lin++)
{aux=a[lin][0];
a[lin][0]=a[lin][c];
a[lin][c]=aux;
};
};
printf("\nNumarul total de solutii este %d.\n", ntotsol);
printf("\nApasati o tasta pentru a termina programul !\n");
getch();
};

int incearca (int i)

{
int lin, col, l, c;
int

aux, q;

lin=col=i;
do
{
q=0;
if ((i > 0 && a[lin][col] >= a[i-1][i-1] ) || (i == 0))
{
for (c=0; c<nc; c++)
{aux=a[i][c];
a[i][c]=a[lin][c];
a[lin][c]=aux;
};

for (l=0; l<nl; l++)

{aux=a[l][i];
a[l][i]=a[l][col];
a[l][col]=aux;
};
if (i < nl-1)
{
q=incearca (i+1);
if (!q)
{
for (c=0; c<nc; c++)
{aux=a[i][c];
a[i][c]=a[lin][c];
a[lin][c]=aux;
};
for (l=0; l<nl; l++)
{aux=a[l][i];
a[l][i]=a[l][col];
a[l][col]=aux;
};
};
}
else
q=1;
};
if (col == nc-1)
{
col=i;
lin++;
}

else
col++;
} while (!q && lin < nl && col < nc);
return (q);
}
18. Programul citeste un vector de valori intregi
si determina daca o anumita valoarea (suma dorita) se poate furniza
prin insumarea valorilor din vector, si ofera toate solutiile posibile

#include <stdio.h>
#include <conio.h>
#define MAXV 16

typedef struct
{int nval, val[MAXV]; /* numar valori disponibile in vector */
long rest;

/* si vectorul; rest (suma) de realizat */

int nrsol;

/* numar solutii */

unsigned sel;

/* marcaj valori selectate, prin setarea

bitului corespunzator pozitiei valorii selectate */

} TDate;
int nle=0; /* numar de linii afisate pe ecran */

void AfiSolutie (TDate *a)

{int i;
unsigned x;
printf ("%2i:", ++a->nrsol);
for (x = a->sel, i = 0; i < a->nval; i++, x >>= 1)
if (x & 1)
printf ("%4i", a->val[i]);
else

printf(" -");
printf("\n");
nle++;
if(nle%23==0)
{printf("Se continua afisarea dupa apasarea unei taste!\n");
getch();
}
}

/* cauta variante de completare a restului din solutia curenta

prin backtracking */
void Cauta (TDate *a, int iv) /* iv - indicele valorii analizate */
{if (a->rest == 0)

/* solutie exacta */

{AfiSolutie (a); return;}

for (; iv < a->nval ; iv++)

/* cat timp mai exista valori de analizat */

if (a->rest >= a->val[iv] )

/* valoarea iv este acceptabila */

{a->sel += (1 << iv);/* avans: marcheaza acceptare val[iv],

prin pozitionarea unui bit 1 pe pozitia iv */
a->rest -= a->val[iv]; /* si micsoreaza rest de completat */
Cauta (a, iv+1);

/* continua cautarea */

a->sel -= (1 << iv); /* revenire: renunta la val[iv],

prin stergerea bitului 1 de pe pozitia iv */
a->rest += a->val[iv]; /* si reface rest de completat */
}
}

void main ()
{int i;
long Suma;
TDate x;

clrscr();
printf ("Introduceti valori, terminand cu 0 sau caracter nenumeric:\n");
for (i = 0; i < MAXV; i++)
if (scanf("%i", &([Link][i])) < 1 || [Link][i] == 0)
break;
if (!i)
{ printf ("Lipsa date!!!\n"); exit(1); }
[Link] = i;
printf("\nAti introdus %u valori:\n", [Link]);
for (i = 0; i < [Link]; i++)
printf ("%5i", [Link][i]);
printf ("\n");
for (;;)
{printf ("\nSuma dorita de construit (calculat) cu valori "
"din vector\n\t(oprire program orice caracter nenumeric): ");
fflush(stdin);
if (!scanf ("%ld", &Suma))
break;
[Link] = 0; [Link] = Suma; [Link] = 0;
Cauta (&x, 0);

/* Cauta solutii */

if (! [Link])
printf ("Nu exista solutie !\n");
}
}
19. "acoperirea" unei table de sah
prin mutarile unui cal, astfel incat fiecare casuta a tablei sa fie
parcursa (atinsa) o singura data; se afiseaza prima solutie gasita

#include <stdio.h>
#include <conio.h>

#define N 5
#define NSQ N*N
#define NrMaxMutCal 8
// N - dimensiunea tablei de sah; NSQ=N^2;
// NrMaxMutCal=8, nr. maxim mutari posibile ale calului, pt. o pozitie data

int i, j, q;
long int nr_incercari;
int h[N+1][N+1];
int a[NrMaxMutCal+1]={0, 1, 1, 2, 2, -1, -1, -2, -2};// poz. relative pe cele doua
int b[NrMaxMutCal+1]={0, 2, -2, 1, -1, 2, -2, 1, -1};// doua coordonate,
// ale celor 8 mutari posibile
void muta (int i, int x, int y, int *pq){// determina mutarea urmatoare
int k, u, v, l, c, q1;
k = 0;
do {
k = k + 1;

// selectie urmatoarea mutare

u = x + a[k];

// noile coordonate

v = y + b[k];
q1 = 0;

// initializare indicator 'succes mutare'

if ((u >= 1 && u <= N) && (v >= 1 && v <= N) && (h[u][v] == 0))
// daca mutarea este valida si casuta nu a fost vizitata
{h[u][v] = i;

// memorare mutare 'i'

if (i < NSQ)
{// daca sol. nu e completa se incearca mutarea urm.
muta (i+1, u, v, &q1);
if (!q1) // daca nu este valida se sterge mutarea
{h[u][v] = 0;
nr_incercari++; // se numara ramurile taiate
}

// (infundate)

}
else
q1 = 1;// daca s-a acoperit tabla->tipareste solutia
} // se continua daca nu s-a gasit o solutie (q1=0) si daca
} while (!q1 && k < NrMaxMutCal); // mai sunt mutari posibile (k<8)
// din pozitia curenta
*pq = q1;

// se transmite reusita sau nereusita mutarii respective

void main (void) {

int i, j, q;
clrscr();
for (i=1; i<=N; i++)

// initializare tabla de sah,

for (j=1; j<=N; j++) // pentru a memora mutarile urmatoare

h[i][j] = 0;
h[1][1] = 1;

// pozitia de start de pe tabla de sah

muta( 2, 1, 1, &q);

// apel mutare 2, din pozitia (1,1),

if (!q)

// q-indicator de succes mutare, acoperire tabla de sah

printf("Problema nu are solutie !!!\n");

else
{for (i=1; i<=N; i++)
{for (j=1; j<=N; j++)
printf("%4d", h[i][j]);
printf("\n");
}
printf("\nNumarul total de incercari a fost de: %ld\n\n",
nr_incercari);
}
}
20. Problema 'Turnurilor din Hanoi', rezolvata recursiv.

#include <stdio.h>
#include <conio.h>
enum pozitie { stanga , mijloc , dreapta};

void tipareste_pozitie ( enum pozitie poz )

{
switch ( poz )
{
case 0 : printf ( "stanga" );/* se poate case stanga */
break;
case 1 : printf ( "mijloc" );
break;
case 2 : printf ( "dreapta" );
}
}

void deplasare( enum pozitie sursa , enum pozitie dest )

{
printf ( "muta un disc din " );
tipareste_pozitie ( sursa );
printf ( " in " );
tipareste_pozitie ( dest );
printf ( "\n" );
return;
}

void muta ( int n, enum pozitie sursa, enum pozitie inter, enum pozitie dest )
{
if ( n > 0 )

{
muta ( n - 1 , sursa , dest , inter );
deplasare ( sursa , dest );
muta ( n - 1 , inter, sursa , dest );
}
}

void main (void)

{
int i , nd;
clrscr();
printf ( "Nr. de discuri :" );
scanf ("%d", &nd);
while ( getchar() != '\n' );
printf ("Mutarile pt. deplasarea unui turn cu %d discuri sunt :\n", nd);
muta ( nd , stanga , mijloc , dreapta );
printf("\n\n");
}

21. Se citeste un vector cu n elemente numere naturale. Sa se determine elementul minim din vector
folosind Divide et impera.
#include<iostream>
using namespace std;
int min(int a[100],int s , int d)
{
if ( s == d ) return a[s];
else
{
int m = (s+d)/2;
int m1 = min(a,s,m);
int m2 = min(a,m+1,d);

if ( m1 < m2 ) return m1;

else return m2;

}
}

int main()
{
int a[100];
int n ;
cin>> n;
for (int i = 0 ; i < n ;i++)
cin>>a[i];

cout << min(a,1,n);

system("pause");
return 0;
}
22. Se citeste un vector cu n elemente numere naturale. Sa se calculeze CMMDC al elementelor
vectorului folosind Divide et impera.
#include<iostream>
using namespace std;
int cmmdc(int a[100], int s, int d)
{ if(s==d) return a[s];
else
{ int x,y;
x=cmmdc(a,s,(s+d)/2);
y=cmmdc(a,(s+d)/2+1,d);

while(x!=y)
if(x>y) x=x-y;
else y=y-x;
return x;
}
}

int main()
{
int a[100],n,i;
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
cout<<cmmdc(a,1,n);
system("pause");
return 0;
}
23. Sa se calculeze folosind metoda divide et impera suma elementelor unui vector.
#include<iostream.h>
int v[20],n;
int suma(int li,int ls)
{int m, d1 ,d2;
if(li!=ls)
{m=(li+ls)/2;
d1=suma(li,m);
d2=suma(m+1,ls);
return d1+d2;
}
else
return v[li];
}

void main()
{
cout<<"n=";
cin>>n;
for(int i=1;i<=n;i++)
{cout<<"v["<<i<<"]=";
cin>>v[i];}
cout<<"suma celor "<<n<<" elemente ale vectorului "<<suma(1,n);
}
24. Se citeste un numar real x. Sa se calculeze radical de ordinul 3 din x folosind un algoritm de tip
Divide et impera.
#include<iostream>
using namespace std;
double r3(double x, double s, double d)
{
if(d-s<=0.0001) return d;
else
{ double m=(s+d)/2;
if(m*m*m<x) return r3(x,m,d);
else return r3(x,s,m);
}
}

int main()
{ double x;
cin>>x;
if(x>0) if(x<1) cout<<r3(x,0,1);
else cout<<r3(x,0,x);
else if(x>-1) cout<<r3(x,-1,0);
else cout<<r3(x,x,0);

system("pause");
return 0;
}
25. Ord. descresc., prin selectie Heapsort:
construim Heap-ul, arborele de selectie, memorat intr-un
vector, dupa care se interschmba prima valoare (maximul)
cu ultima si in vectorul ramas (n-1) se construieste
din nou Heap-ul, s.a.m.d.

#include<stdio.h>
#include <conio.h>
void cerne (double a[], int l, int r)
{
int i,j;
double x;
i=l; j=2*i; x=a[i]; /* x ce se cerne prin arbore/ vector */
while (j<=r){
if (j<r) /* nu s-a ajuns la capat */
if (a[j]<a[j+1]) /* j-ind. val. mai mare din */
j++;
if (x>a[j])

/* perechea (2*i, 2*i + 1) */

/* daca x > valoarea respectiva (j) */

goto gata; /* altfel, se muta */

a[i]=a[j]; /* valoarea mai mare a[j] la a[i], si se */
i=j; j=2*i; /* continua cernerea pe nivelul urmator */
} /* noul i devine j (vechi i), iar j=2i, daca j<r */
gata: a[i]=x; /* pune x in poz. i, a[i]<a[2i], a[i]<a[2i+1] */
}

void heapsort(double a[], int n){

int i, l, r;

double x;
l=(n/2)+1; r=n;
while (l>1){
l--;
cerne(a,l,r);
for( i = 1 ; i <= n ; ++i ){
printf (" %[Link] ", a[i]);
if (i%10==0)
printf("\n");
}
printf("\nApasa o tasta pentru continuare program!\n");
getch();
}
while(r>1)
{x=a[1];
a[1]=a[r];
a[r]=x;
r--;
cerne(a,l,r);
for( i = 1 ; i <= n ; ++i ){
printf (" %[Link] ", a[i]);
if (i%10==0)
printf("\n");
}
printf("\nApasa o tasta pentru continuare program!\n");
getch();
}
}

void main(void)

{
double sir[1000];
int ne, i;
clrscr();
printf("HeapSort pentru ordonare crescatoare vector.\n");
printf ("Numarul de elemente: ");
scanf ("%d",&ne);
for ( i = 1 ; i <= ne ; ++i)
{
printf (" sir(%d)=", i);
scanf ("%lf", &sir[i]);
}
heapsort(sir,ne);
for( i = 1 ; i <= ne ; ++i ){
printf (" %[Link] ", sir[i]);
if (i%10==0)
printf("\n");
}
printf("\nPROGRAM TERMINAT! Apasa o tasta-iesire!!!\n");
getch();
}

26. Ord. descresc., prin selectie Heapsort:

construim Heap-ul, arborele de selectie, memorat intr-un
vector, dupa care se interschmba prima valoare (minimul)
cu ultima si in vectorul ramas (n-1) se construieste
din nou Heap-ul, s.a.m.d.

#include<stdio.h>

#include <conio.h>
void cerne (double a[], int l, int r)
{
int i,j;
double x;
i=l; j=2*i; x=a[i]; /* x ce se cerne prin arbore/ vector */
while (j<=r){
if (j<r) /* nu s-a ajuns la capat */
if (a[j]>a[j+1]) /* j-ind. val. mai mica din */
j++;
if (x<a[j])

/* perechea (2*i, 2*i + 1) */

/* daca x < valoarea respectiva (j) */

goto gata; /* altfel, se muta */

a[i]=a[j]; /* valoarea mai mica a[j] la a[i], si se */
i=j; j=2*i; /* continua cernerea pe nivelul urmator */
} /* noul i devine j (vechi i), iar j=2i, daca j<r */
gata: a[i]=x; /* pune x in poz. i, a[i]<a[2i], a[i]<a[2i+1] */
}

void heapsort(double a[], int n){

int i, l, r;
double x;
l=(n/2)+1; r=n;
while (l>1){
l--;
cerne(a,l,r);
for( i = 1 ; i <= n ; ++i ){
printf (" %[Link] ", a[i]);
if (i%10==0)
printf("\n");

}
printf("\nApasa o tasta pentru continuare program!\n");
getch();
}
while(r>1)
{x=a[1];
a[1]=a[r];
a[r]=x;
r--;
cerne(a,l,r);
for( i = 1 ; i <= n ; ++i ){
printf (" %[Link] ", a[i]);
if (i%10==0)
printf("\n");
}
printf("\nApasa o tasta pentru continuare program!\n");
getch();
}
}

void main(void)
{
double sir[1000];
int ne, i;
clrscr();
printf ("Numarul de elemente: ");
scanf ("%d",&ne);
for ( i = 1 ; i <= ne ; ++i)
{
printf (" sir(%d)=", i);

scanf ("%lf", &sir[i]);

}
heapsort(sir,ne);
for( i = 1 ; i <= ne ; ++i ){
printf (" %[Link] ", sir[i]);
if (i%10==0)
printf("\n");
}
printf("\nPROGRAM TERMINAT! Apasa o tasta-iesire!!!\n");
getch();
}
27. Prog. de ordonare cresc. sir, utilizand metoda de inserare binara,
adica: se considera un sir ordonat, format initial din primul element din
sirul initial, si un sir neordonat, format din restul elementelor sirului,
din care se iau pe rand celelalte elemente si li se cauta, de la dreapta
la stanga, pozitia in sirul ordonat, construit tot in sirul initial.
Cautarea se face utilizand metoda "binara".

#include<stdio.h>
#include <conio.h>
int ncomp=0, nins=0; /* numar de comparatii si inserari/deplasari */

/*

functia de sortare prin inserare binara

*/

void sort_ins_binara ( double a[], int n )

{
double x;
int i, j, s, d, m;
for (i=1; i<n; ++i)
{
x=a[i]; s=0; d=i-1;/* initializari: x-elementul de inserat */

while (s <= d) /* s, d-limitele stanga/dreapta pentru subsir dest */

{ncomp++;
m=(s+d)/2; /* mijlocul subsirului */
if (x < a[m]) /* in functie de apartenenta elementului x */
d=m-1; /* la subsirul din stanga sau dreapta */
else

/* se stabileste noua limita din stanga/dreapta */

s=m+1; /* a noului subsir, in care se cauta */

/* dupa determinarea pozitiei de inserare a elem.*/

for (j=i-1; j>=s; --j, nins++) /* se deplaseaza tot sirul cu */

a[j+1]=a[j]; /* o pozitie la dreapta, de la pozitia */
a[s]=x; /* de inserare pana la sfarsit, dupa care */
/* se insereaza noul element, x */
}
}

void main(void){
double sir[100]; int ne,i;
clrscr();
printf("Numar elemente:");
scanf("%d", &ne);
for(i=0; i<ne; i++)

/* citire sir de ordonat */

{
printf("sir(%d)= ", i+1);
scanf("%lf", &sir[i]);
}
printf("Sirul ordonat este: \n");
sort_ins_binara(sir , ne);
for (i=0;i<ne;i++)

/* apelul functiei de sortare binara */

/* afisare sir ordonat */

{
printf(" sir (%2d) = %lf \n", i+1, sir[i]);

if ((ne+1)%4==0)

/* tiparesc cate 4 valori pe linie */

printf("\n");
}
printf("\n");
printf("Ordonarea s-a realizat prin %d comparatii si %d deplasari\n",
ncomp, nins);
}
28. Prog. ordonare cresc. sir, utilizand metoda de inserare directa, adica:
se considera un sir ordonat, format initial din primul element din sirul initial,
si un sir neordonat, format din restul elementelor sirului, din care se iau pe
rand celelalte elemente si li sa cauta, de la dreapta la stanga, pozitia in
sirul ordonat, construit tot in sirul initial.

#include <stdio.h>
#include <conio.h>
int ncomp=0, nins=0; /* numar de comparatii si inserari/ deplasari */

void sort_ins_direct (double a[], int n)

{/* functia de sortare prin inserare directa */
double x;
int i, j;
for (i=1; i<n; ++i)
{
x=a[i]; /* elementul curent de inserat */
j=i-1;

/* dimensiunea sirului destinatie */

while (x < a[j] && j >= 0)

{

/* se cauta pozitia de inserare */

a[j+1]=a[j];
j--;
ncomp++; nins++;

}
a[j+1]=x;

/* inseare element curent */

}
}

void main()
{
double sir[100];
int ne, i;
clrscr();
printf("Numar elemente:");
scanf("%d", &ne);
for(i=0; i<ne; i++)

/* citirea elementelor sirului de sortat */

{
printf("sir(%d)= ", i+1);
scanf("%lf", &sir[i]);
}
sort_ins_direct (sir, ne); /* ordonarea sirului prin inserare directa */
printf("\n Sirul ordonat:\n");
for(i=0; i<ne; i++)

/* afisare sir ordonat */

{
printf(" sir(%d)=%5.2lf ", i+1, sir[i]);
if ( (i+1) %5 == 0 ) /* daca s-au afisat 5 valori din sir pe o linie */
printf("\n");

/* se trece pe o linie noua */

}
printf("\n");
printf("Ordonarea s-a realizat prin %d comparatii si %d deplasari\n",
ncomp, nins);

29. Sortarea unui vector utilizand algoritmul QuickSort, iterativ

#include<stdio.h>
#include<conio.h>
#define DIM 100

typedef int VECTOR[DIM];

int ncomp=0, ninv=0;

/* numar de comparatii, inversiuni */

void cit_vect(int n, VECTOR v)

{int i;
for(i=0; i<n; i++)
{printf("v[%d]=", i+1);
scanf("%d", &v[i]);}
}

void scrie_vect(int n, VECTOR v)

{int i;
for(i=0; i<n; i++)
printf("v[%d]=%d\n", i+1, v[i]);
}

void QuickSortit (VECTOR a, int n)

/* Sortara partajata (QuickSort) realizata iterativ */
{int s, d, i, j, is, x, t;
struct st_stiva {int s, d;}; /* element stiva: pozitia stanga, dreapta */
struct st_stiva stiva[DIM]; /* stiva ce contine lista de cereri partitie */
is=1; stiva[is].s=0; stiva[is].d=n-1; d=n-1; /* initializari */
do{
s=stiva[is].s; d=stiva[is].d; is--; /* partitia curenta de realizat*/
do

{i=s; j=d;

/* este luata din varful stivei */

x=a[(s+d)/2];
do

/* santinela */

{
while (a[i]<x) i++, ncomp++;
while (a[j]>x) j--, ncomp++;
if (i<=j)
{t=a[i];
a[i]=a[j];
a[j]=t;
i++; j--;
ninv++;
}
} while(i<=j);

if (i<d){ /* depun in stiva cererea de a sorta */

is++; /* partitia dreapta */
stiva[is].s=i;
stiva[is].d=d;
}
d=j;

/* se continua sortarea partitiei stanga, (s, d) */

} while (s<d); /* pana are un singur element (s==d) */

}while (is>0);
}

/* se reia sortarea pentru partitiile stanga */

/* ramase nerezolvate, in stiva */

void main(void)
{int n;
VECTOR v;
clrscr();
printf("Programul ordoneaza (sorteaza) un vector cu alg. QuickSort.\n");
printf("Dimensiune vector, n=");scanf("%d", &n);
cit_vect(n, v);
QuickSortit (v, n);

printf("\nVectorul ordonat este:\n");

scrie_vect(n, v);
printf("Sortarea s-a realizat dupa %d comparatii si %d inversiuni\n",
ncomp, ninv);
getch();
}
30. Programul ordoneaza un vector prin selectie directa,
utilizand pentru aceasta determinarea minimului si a pozitiei lui,
la fiecare iteratie si realizand o singura inversiune intre acest
minim si valoarea a[i], corespunzatoare iteratiei curente;
se determina si numarul de comparatii si inversiuni realizate

#include<stdio.h>
#include <conio.h>
int ncomp=0, ninv=0; /* numar de comparatii si inversiuni */
void sort_sel_direct ( double a[], int n )
/* functia sorteaza un vector prin metoda de selectie directa */
{
double x;
int i, j, k;
for ( i = 0 ; i < n-1 ; ++i )
{
k = i;

/* initializare indice, k, si elementul minim, x */

x = a[i];
for ( j = i+1 ; j < n ; ++j, ncomp++ ) /* determinare minim si indicele lui din sir */
if (a[j] < x)
{
k = j;
x = a[k];
}

a[k] = a[i];

/* interschimbare minim cu primul din subsirul sursa, */

a[i] = x; /* adica cu primul din subsirul neordonat */

ninv++;
}
}
void main()
{
double sir[100];
int ne,i, nl=0;
clrscr();
printf("Numar elemente:");
scanf("%d",&ne);
for(i=0;i<ne;i++)

/* citirea elementelor sirului de ordonat */

{
printf("sir(%d)=",i+1);
scanf("%lf",& sir[i]);
}
sort_sel_direct(sir,ne); /* ordonarea sirului prin selectie directa */
for(i=0;i<ne;i++)

/* afisarea sirului ordonat */

{
printf(" sir(%2d)=%5.1lf",i+1,sir[i]);
nl++;

/* actualizare contor numar de valori afisate pe o linie */

if ( nl % 5 == 0 ) /* daca s-au afisat 5 valori pe o linie se trece pe */

printf("\n");

/* o linie noua */

}
printf("\n");
printf("Ordonarea s-a realizat prin %d comparatii si %d inversiuni\n",
ncomp, ninv);
}
31. Programul ordoneaza un sir de valori prin

metoda inversiunilor (bulelor) - forma clasica

#include <stdio.h>
#include <conio.h>
int ncomp=0, ninv=0; /* numar de comparatii si inversiuni/ deplasari */

void sort_met_bulelor (double a[], int n)

/*

functia sorteaza un vector prin metoda inversiunilor (bulelor) */

{double x;
int i, j;
for (i=1; i<n; i++)
for (j=n-1; j>=i; j--, ncomp++)
if (a[j-1] > a[j])
{
x=a[j-1];
a[j-1]=a[j];
a[j]=x;
ninv++;
}
}
void main(){
double sir[100];
int ne,i, nl=0;
clrscr();
printf("Numar elemente:");
scanf("%d", &ne);
for(i=0; i<ne; i++) /* citirea elementelor sirului de ordonat */
{printf("sir(%d)=",i+1);
scanf("%lf", &sir[i]);
}

sort_met_bulelor (sir, ne); /* ordonarea sirului prin selectie directa */

for(i=0; i<ne; i++)

/* afisarea sirului ordonat */

{
printf("sir(%2d)=%5.1lf ", i+1, sir[i]);
nl++;

/* actualizare contor numar de valori afisate pe o linie */

if (nl % 5 == 0) /* daca s-au afisat 5 valori pe o linie */

printf("\n");

/* se trece pe o linie noua */

}
printf("\n");
printf("Ordonarea s-a realizat prin %d comparatii si %d deplasari\n",
ncomp, ninv);
}