Notes

sortari
insertion ----
int main()
{
int a[20], n,i,j,aux;
printf("n=");scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("a[%d]= ",i);
scanf("%d",&a[i]);
}
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
if(a[i]>a[j])
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
}
for(i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
MERGE -----
void Citire(int a[], int n)
{
int i;
for(i=1;i<=n;i++)
{
printf("a[%d]= ",i);scanf("%d",&a[i]);
}
}
void Afisare(int a[], int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d ",a[i]);
}

void Merge(int a[], int p, int q, int r)
{
int s[100], d[100], n1,n2,i,j,k;
n1=q-p+1;
n2=q-r;
for(i=1;i<=n1;i++)
s[i]=a[p+i-1];
for(j=1;j<=n2;j++)
d[j]=a[q+j];
s[n1+1]=INT_MAX;
d[n2+1]=INT_MAX;
i=1;
j=1;
for(k=p;k<=r;k++)
if(s[i]<d[j])
{
a[k]=s[i];
i++;
}
else
{
a[k]=d[j];
j++;
}
}
void MergeSort(int a[], int p, int r)
{
int q;
if(p<r)
{
q=(p+q)/2;
MergeSort(a,p,q);
MergeSort(a,q+1,r);
Merge(a,p,q,r);
}

}
SELECTION --
void intereschimbare(int a, int b)
{
int aux;
aux=a;
a=b;
b=aux;
}
void selection(int a[], int n)
{
int mini,i,j;
for(i=1;i<=n-1;i++)
{
mini=i;
for(j=i+1;j<=n;j++)
if(a[j]<a[mini])
mini=j;
}
intereschimbare(a[mini], a[i]);

}
QUICKSORT ---
int Partitionare(int a[], int p, int r)
{
int x, i, j, aux;
x=a[r];
i=p-1;
for(j=p;j<r;j++)
if(a[j]<=x)
{
i++;
aux=a[i];
a[i]=a[j];
a[j]=aux;
}
a[r]=a[i+1];
a[i+1]=x;
return i+1;
}
void QuickSort(int a[], int p, int r)
{
int q=0;
if(p<r)
{
q=Partitionare(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}
cut rod
#include <stdio.h>
#include <stdlib.h>
#include "limits.h"
void citire(int a[], int n)
{ int i;
for(i=1;i<=n;i++)
{
printf("a[%d]= ", i);
scanf("%d", &a[i]);
}
}
void afisare(int a[], int n)
{
int i;
for(i=1;i<=n;i++)
printf("%d ", a[i]);
}
int max(int a, int b)
{
if(a<b)
return b;
else
return a;
}

/*int cutrod(int a[], int n)
{
int q, i;
if(n==0)
return 0;
q=INT_MIN;
for(i=1;i<=n;i++)
q=max(q,a[i]+ cutrod(a, n-i));
return q;
}*/
/* int memoizedcutrodaux(int a[], int n, int r[])
{
int i, q;
if(r[n]>0)
return r[n];
if(n==0)
q=0;
else
{
q=INT_MIN;
for(i=1;i<=n;i++)
q=max(q, a[i] + memoizedcutrodaux(a,n-i,r));
}
r[n]=q;
return q;
}
int memoizedcutrod(int a[], int n)
{
int q, i, r[100];
for(i=0;i<=n;i++)
r[i]=INT_MIN;
q=memoizedcutrodaux(a,n,r);
afisare(r,n);
return q;


}

*/
int bottomupcutrod(int a[], int n)
{
int q,i,j,r[100];
r[0]=0;
for(j=1;j<=n;j++)
{
q=INT_MIN;
for(i=1;i<=j;i++)
q=max(q, a[i]+ r[j-i]);
r[j]=q;
}
afisare(r,n);
return r[n];

}
int main()
{
int a[100], n;
printf("n= ");
scanf("%d", &n);
citire(a,n);
printf(" n Valoarea maxima este= %d n ", bottomupcutrod(a,n));

}
greedy si recursiv
#include <stdio.h>
#include <stdlib.h>
#include "recursive_activity_selector.h"
#include "greedy_activity_selector.h"
#include "read_array.h"
#include "print_array.h"
int main()
{
int sol_rec[200], sol_iter[200], n, s[200], f[200], lenght_sol_rec, lenght_sol_iter;
printf("INTRODUCETI n=");
scanf("%d", &n);
read_arrays(s,n);
read_arrayf(f,n);
f[0]=0;
lenght_sol_rec=recursive_activity_selector(s,f,0,n,sol_rec);
printf("sol recursiva=");
print_array(sol_rec, lenght_sol_rec);
printf("n");
lenght_sol_iter=greedy_activity_selector(s,f,n,sol_iter);
printf("sol iterativa=");
print_array(sol_iter,lenght_sol_iter);
}
#ifndef RECURSIVE_ACTIVITY_SELECTOR_H_INCLUDED
#define RECURSIVE_ACTIVITY_SELECTOR_H_INCLUDED
int recursive_activity_selector(int s[], int f[], int k, int n, int a[]);


#endif // RECURSIVE_ACTIVITY_SELECTOR_H_INCLUDED
#include "recursive_activity_selector.h"
int recursive_activity_selector(int s[], int f[], int k, int n, int a[])
{
int m;
static int na=0;
m=k+1;
while (m<n && s[m] < f[k])

m++;

if(m<=n)
{
na++;
a[na]=m;
recursive_activity_selector(s, f, m, n,a);
}
return (na);
}
#ifndef GREEDY_ACTIVITY_SELECTOR_H_INCLUDED
#define GREEDY_ACTIVITY_SELECTOR_H_INCLUDED
int greedy_activity_selector(int s[], int f[], int n, int a[]);


#endif // GREEDY_ACTIVITY_SELECTOR_H_INCLUDED
#include "greedy_activity_selector.h"
#include <stdio.h>
int greedy_activity_selector(int s[], int f[], int n, int a[])
{

int na,k,m;
na=0;
k=0;
for(m=1; m<=n; m++)
if (s[m] >= f[k])
{
na++;
a[na]=m;
k=m;
}
return na;
}
#ifndef READ_ARRAY_H_INCLUDED
#define READ_ARRAY_H_INCLUDED
void read_array(int a[], int n);



#endif // READ_ARRAY_H_INCLUDED
#include "read_array.h"
#include <stdio.h>
void read_arrays(int a[], int n)
{
int i;
for(i=1; i<=n; i++)
{
printf("s[%d]= ", i);
scanf("%d", &a[i]);
}

}
void read_arrayf(int a[], int n)
{
int i;
for(i=1; i<=n; i++)
{
printf("f[%d]= ", i);
scanf("%d", &a[i]);
}

}
#ifndef PRINT_ARRAY_H_INCLUDED
#define PRINT_ARRAY_H_INCLUDED
void print_array(int a[], int n);


#endif // PRINT_ARRAY_H_INCLUDED
#include "print_array.h"
void print_array(int a[], int n)
{
int i;
for(i=1; i<=n; i++)
printf("%d", a[i]);
}

dame
#include<stdio.h>
#include<stdlib.h>
#include"backtracking.h"

int nr_sol;

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

void print_array(int a[], int n)
{
int i;
for(i=1; i<=n; i++)
printf("a[%d]=%dn", i, a[i]);
}


void tipareste_solutia(int x[], int n)
{ int i, j;
printf("n");
printf("Solutia cu numarul %d:n", nr_sol);
for(i=1; i<=n; i++)
{for(j=1; j<=n; j++)
if(x[i]==j) printf("R " );
else printf(" - " );
printf("n");
}
}

int se_ataca (int x[], int pos)
{
for(int i=1; i<=(pos-1); i++)
if(x[i]==x[pos] || abs(x[i]-x[pos])==abs(i-pos)) return 1;

return 0;
}

void dame(int x[], int n)
{
int k=1;
for(int i=1; i<=n; i++) x[i]=0;
while(k>0)
{
if(k>n)
{nr_sol++;
tipareste_solutia(x, n);
k--;
}
x[k]++;
if(x[k]<=n)
{if(se_ataca(x, k)==0)
k++;}
else {x[k]=0;
k--;}
}
}
#ifndef BACKTRACKING_H_INCLUDED
#define BACKTRACKING_H_INCLUDED

void print_array(int a[], int n);
void read_array(int a[], int n);
void tipareste_solutia(int x[], int n);
int se_ataca (int x[], int pos);
void dame(int x[], int n);




#endif // BACKTRACKING_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#include "backtracking.h"

int main()
{ int n, x[100];
printf("Dati nr de dame:");
scanf("%d", &n);
dame(x, n);
//printf("Nr de solutii este: %d", nr_sol);
return 0;
}

liste
#include <stdio.h>
#include "makenull.h"

void make_null(t_lista *L)
{
L->head=(t_nod_lista*) malloc(sizeof(t_nod_lista));
L->head->next=L->head->prev=NULL;
}
void list_insert(t_lista *L, t_nod_lista *x)
{
if(x==NULL)
return;
x->next=L->head->next;
if(L->head->next != NULL)
L->head->next->prev=x;
L->head->next=x;
x->prev=L->head;
}
void list_print(t_lista L)
{
t_nod_lista *x;
x=L.head->next;
if(x==NULL)
printf("lista e vida");
while(x!=NULL)
{
printf("%d ", x->cheie);
x=x->next;
}
}
t_nod_lista* list_search(t_lista L, int key)
{
t_nod_lista *x;
x=L.head;
while(x!=NULL && x->cheie!=key)
x=x->next;
return x;
}
void list_delete(t_lista *L, t_nod_lista *x)
{
if(x->prev!=NULL)
x->prev->next=x->next;
else L->head->next=x->next;

if(x->next!=NULL)
x->next->prev=x->prev;
}
void list_free(t_lista *L)
{
t_nod_lista *x;
x=L->head->next;
while(x!=NULL)
{
list_delete(L,x);
free(x);
x=L->head->next;
}
free(L->head);
}
#ifndef MAKENULL_H_INCLUDED
#define MAKENULL_H_INCLUDED

typedef struct nod_lista{
int cheie;
struct nod_lista *next, *prev;
} t_nod_lista;

typedef struct{
t_nod_lista *head;
} t_lista;

void make_null(t_lista *L);
void list_insert(t_lista *L, t_nod_lista *x);
void list_print(t_lista L);
t_nod_lista* list_search(t_lista L, int key);
void list_delete(t_lista *L, t_nod_lista *x);

#endif // MAKENULL_H_INCLUDED


typedef struct nod_lista{
int cheie;
struct nod_lista *next,
*prev;

}t_nod_lista;
typedef struct{
t_nod_lista *head;

}t_lista;
void makenull; lista *L
void list_insert; lista *L, t_nod_lista *x
void list_print; lista L, t_nod_lista x
void list_delete; lista *L, t_nod_lista *x;
t_nod_lista *list_search; int key
void list_free. lista l

#include <stdio.h>
#include <stdlib.h>
#include "makenull.h"
int main()
{
t_lista L;
t_nod_lista *x;
int s=-1, key;
make_null(&L);
while(s)
{
printf("nMeniu principaln");
printf("Tastati 1 pentru inseraren");
printf("Tastati 2 pentru cautaren");
printf("Tastati 3 pentru stergeren");
printf("Tastati 4 pentru afisarea listein");
scanf("%d",&s);
switch(s)
{
case 1:
printf("cheia de inserat: ");
scanf("%d",&key);
x=(t_nod_lista*)malloc(sizeof(t_nod_lista));
x->cheie=key;
list_insert(&L,x);
break;
case 2:
printf("cheia de inserat: ");
scanf("%d",&key);
x=list_search(L,key);
if(x!=NULL)
printf("%d", key);
else printf("Cheie negasita");
break;
case 3:
printf("cheia de inserat: ");
scanf("%d",&key);
x=list_search(L,key);
if(x!=NULL)
list_delete(&L,x);
else printf("Cheie negasita");
break;
case 4:
printf("Lista contine: ");
list_print(L);
break;
}
}
list_free(&L);
return 0;
}