Strona główna

Minmax #include const n=8; int tab[n]={2,3,5,2,5,6,2,9}; main { int I, max=tab[0],min=tab[0]; for(i=1;imax) max=tab[i]; for


Pobieranie 40.45 Kb.
Data19.06.2016
Rozmiar40.45 Kb.
MINMAX

#include

const n=8;

int tab[n]={2,3,5,2,5,6,2,9};

main()

{

int i, max=tab[0],min=tab[0];



for(i=1;imax) max=tab[i];

for(i=1;i

printf("\n max=%d, min=%d", max,min);

return 0;

}




FIBO

#include

unsigned long int fib(int x)

{

if (x<2) return 1; else



return fib(x-1)+fib(x-2);

}

void fib_dyn(int x, int f[])



{

f[0]=1;


f[1]=1;

for(int i=2;i

f[i]=f[i-1]+f[i-2];

}

void main()



{

int f[100];

fib_dyn(16,f); // oblicza 15 kolejnych elementow ciagu

for(int i=0;i<=15;i++)

cout << "fib("<

}




Algorytm zachłanny (ang. greedy algorithm) to taki algorytm, który w celu wyznaczenia rozwiązania przechodzi przez wszystkie możliwe w danej sytuacji kroki. Innymi słowy algorytm zachłanny nie patrzy czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej.




Quicksort

template

void quicksort(T data[],int first, int last){

int lower=first+1; upper=last;

swap(data[first], data[(first+last)/2]);

T bound=data[first];

while(lower<=upper){

while(data[lower]

lower++;

while(bound

upper--;

if(lower

swap(data[lower++],data[upper--]);

else lower++;

}

swap(data[upper],data[first]);



if(first

quicksort(data,first,upper-1);

if(upper+1

quicksort(data,upper+1,last);

}

template



void quicksort(T data[], int n){

int i, max;

if(n<2)

return;



for(i=1;max=0;i

if(data[max]

max=i;

swap(data[n-1],data[max]);



quicksort(data,0,n-2);

}




Radix to algorytm sortowania porządkujący stabilnie elementy zbioru względem konkretnych cyfr, znaków itp, kolejno od najmniej znaczących do najbardziej znaczących pozycji.
list sort(list r )

{

list head[M], tail[M];



int i, j, h;

for (i=D; i>0; i--) {

for (j=0; j

while ( r != NULL ) {

h = charac( i, r->k );

if ( head[h]==NULL ) head[h] = r;

else tail[h]->next = r;

tail[h] = r;

r = r->next;

};

/*** Concatenate lists ***/



r = NULL;

for (j=M-1; j>=0; j--)

if ( head[j] != NULL ) {

tail[j]->next = r;

r = head[j];

}

};



return( r );

};
int Partition( int d[], int left, int right) { int val =d[left]; int lm = left-1; int rm = right+1; for(;;) { do rm--; while (d[rm] > val); do lm++; while( d[lm] < val); if(lm < rm) { int tempr = d[rm]; d[rm] = d[lm]; d[lm] = tempr; } else return rm; } }



Heapsort

2 fazy: zbudowanie kopca i sortowanie


heapsort(data[],n)

przekształcić tablice data na stertę

for(i=n-1;i>1;i--)

zamień korzeń z elementem na pozycji i;

odtwórz własność kopca dla drzewa data[0],..., data[i-1]
kod:

template

void heapsort(T data[], int size){

int i;


for(i=size/2-1;i>=0;i--)

movedown(data,i,size-1);

for(i=size-1;i>=1;--i){

swap(data[0],data[i]);

movedown(data,0,i-1);

}}
template

void movedown(T data[], int first, int last){

int largest=2*first+1;

while(largest<=last{

if(largest

largest++;

if(data[first]

swap(data[first],data[largest]);

first=largest;

largest=2*first+1;

}

else largest=last+1;



}

}
void swap(int a,int b){

int pom;

pom=a;


a=b;

b=pom;


}
Drzewo poszukiwań binarnych (skrót BST, z ang. Binary Search Tree) jest dynamiczną strukturą danych w postaci drzewa binarnego.

W każdym z węzłów drzewa przechowywana jest pewna wartość, przy czym: wartość przechowywana w węźle jest większa od wartości przechowywanej w lewym synu i mniejsza od wartości przechowywanej w prawym synu (relacja może być odwrócona, to kwestia umowy). Przechodząc drzewo metodą inorder uzyskuje się ciąg wartości posortowanych rosnąco.



MergeSort - Algorytm ten jest dobrym przykładem algorytmów typu dziel i zwyciężaj (ang.) divide and conquer. Ideą działania tego typu algorytmów jest podział problemu na mniejsze części, których rozwiązanie jest już łatwiejsze. Tutaj można wyróżnić trzy podstawowe kroki:

  1. Podziel zestaw danych na dwie, równe części;

  2. Zastosuj sortowanie przez scalanie dla każdej z nich odzielnie, chyba że pozostał już tylko jeden element;

  3. Połącz posortowane podciągi w jeden.

Złożoność sortowania przez scalanie wynosi O(n log n)
MergeSort Kod:

#include #include typedef unsigned int TYP; #define OZNACZENIE_TYPU "u" // oznaczenie odpowiednio do printf(3) i TYPu TYP *tablica; void merge(unsigned long start, unsigned long srodek, unsigned long stop) { TYP tab_out[stop-start+1]; unsigned long i1, i2, io, k; i1 = start; i2 = srodek+1; io = 0; while ((i1 <= srodek) && (i2 <= stop)) if (tablica[i1] < tablica[i2]) tab_out[io++] = tablica[i1++]; else tab_out[io++] = tablica[i2++]; if (i1 > srodek) for (k = i2; k <= stop; k++, io++) tab_out[io] = tablica[k]; else for (k = i1; k <= srodek; k++, io++) tab_out[io] = tablica[k]; for (k = start; k <= stop; k++) tablica[k] = tab_out[k-start]; } void merge_sort(unsigned long start, unsigned long stop) { if (start == stop) return; else { unsigned long srodek = (start+stop)/2; merge_sort(start, srodek); merge_sort(srodek+1, stop); merge(start, srodek, stop); } } unsigned long i, licznik = 0; TYP in = 0; char *smiec; int main(void) { while (!feof(stdin)) if (fscanf(stdin, "%" OZNACZENIE_TYPU "\n", &in)!=0) { if (!licznik) tablica = (TYP *)malloc(sizeof(TYP)); else tablica = (TYP *)realloc(tablica,(licznik+1)*sizeof(TYP)); if (tablica == NULL) { fprintf(stderr, "Brak pamięci! Program nie może kontynuować działania!\n"); exit(1); } tablica[licznik++] = in; } else { fscanf(stdin, "%s\n", &smiec); fprintf(stderr,"\"%s\" nie jest liczbą! Pozycja zostanie zignorowana!\n", &smiec); } merge_sort(0, licznik-1); for(i = 0; i < licznik; i++) printf("%" OZNACZENIE_TYPU "\n", tablica[i]); return 0; }


©snauka.pl 2016
wyślij wiadomość