Twoim problemem jest to, że powszechną NICOŚĆ mylisz z osobistą PUSTKĄ
POTEGA M Do K
main()
{ int k;
long m, potega;
cin >> m >> k;
potega = 1;
while (k>0) {
if (k % 2==1) potega = potega*m;
m = m*m;
k = k / 2;
}
cout << potega;
}
SORTOWANIE PRZEZ ZLICZANIE
main()
{
int T[10];
int i,j;
for( j = 1; j < 10; j++ ) T[j] = 0;
do {
cin >> i;
if (i != 0) T[i]++;
} while ( i != 0 );
for( j = 1; j < 10; j++ )
for ( i = 1; i <= T[j]; i++ )
cout << j << „\n”;
}
SCHEMAT HORNERA
wynik = 0; potega =1;
for(i=0; i <= n; i++)
{ wynik += A[i] * potega;
potega = potega * x;}
PRZESZUKIWANIE TABLICY Z WARTOWNIKIEM
#include <stdio.h>
#define n 10
main()
{ int a[n+1];
int k, x;
FILE *input;
input=fopen(“dane”,”r”);
for (k=0; k<n; k++)
fscanf(input,”%d”,&a[k]);
fscanf(input, “%d”, &x);
a[n] = x;
for(k=0; a[k]!=x; k++);
if (k<n) printf(“Element %d wystepuje\n”, x);
else printf(“Element %d NIE wystepuje\n”, x);
fclose(input);
}
PRZESZUKIWANIE BINARNE
int znajdz(int a[], int x)
{ int s, p, r;
p=0; r=n-1;
while(p<r)
{ s=(p+r)/2;
if (a[s]==x) return s;
if (a[s]>x) {r=s;} else
if (p==s) {p=r;} else {p=s;}
}
if (a[p]==x) return p;
else return -1;
}
SORTOWANIE PRZEZ WSTAWIANIE
void sortowanie_przez_wstawianie (int tab[], int n)
{
int i,k,elem;
for (i=1; i<n; i++)
{
elem = tab[i];
k=i-1;
while (k>=0 && tab[k] > elem)
{
tab[k+1] = tab [k];
k— –;
}
tab[k+1] = elem;
}
}
ALGORYTM EUKLIDESA
#include <iostream.h>
int nwd(int n, int m)
{ if (m==0) return n;
if (m>n) return nwd(m, n);
return nwd(m, n%m);
}
main()
{int n, m, wynik;
cin >> n >> m;
wynik = nwd(n, m);
cout << wynik;
}
LICZBA FIBONNACIEGO ITER
#include <stdio.h>
long fib(int k)
{ long f0, f1,x;
f0=f1=1;
for (i=2; i; i++)
{ x=f1; f1+=f0; f0=x;}
return f1;
}
main()
{int n, i;
cin >> n;
cout << fib(n) << endl;
}
LICZBA FIBONNACIEGO REK
#include <iostream.h>
long fib(int i)
{ return i<=1? 1 : fib(i-1)+fib(i-2);
}
main()
{int n;
cin >> n;
cout << fib(n) << endl;
}
MAX MIN TABLICY MET DZIEL I ZWYCIEZAJ
main()
{ int b[]={1, 2, 1,-3,7,-14};
int mx,mn;
maxmin(b,6,&mn,&mx);
printf("\n%d %d\n",mn,mx);
}
maxmin(int *a, int l,int p, int *min, int *max)
{ int mi1,mi2,ma1,ma2;
if (l==p) *min=*max=a[l];
else if (p-l==1){
if (a[l]<a[p]) {*max=a[p]; *min=a[l];}
else {*max=a[l]; *min=a[p];}
}
else
{ maxmin(a,l,(l+p)/2, &mi1,&ma1);
maxmin(a,(l+p)/2+1,p, &mi2,&ma2);
*min=mi1<mi2? mi1 :mi2;
*max=ma1>ma2? ma1 :ma2;
SORTOWANIE PRZEZ SCALANIE REK
mergesort(int *a, int l, int p)
{ int s,j,k;
if (p-l>0)
{ s=(l+p-1)/2;
mergesort(a,l,s+1);
mergesort(a,s+1,p);
merge(a,l,s+1,p);
}
}
SORTOWANIE PRZEZ SCALANIE ITER
sort(int b[], int l, int p)
{ int j,k,i;
for (i=1; l+i<p; i=i+i)
for (j=l; j+i<p; j=j+2*i)
{ k=(j+2*i<p)? j+2*i:p;
merge(b,j,j+i,k);
}
}
SORTOWANIE QUICKSORT REK
qsort(int d[],int l,int p)
{ int s;
if (l<p) {s=partition(d,l,p);
qsort(d,l,s);
qsort(d,s+1,p);}
}
partition(int d[], int l, int p)
{ int x,y;
x=d[l];
l--;
p++;
do
{ while (d[--p]<x);
while (d[++l]>x);
if (l<p) {y=d[p]; d[p]=d[l]; d[l]=y;}
else return p;
} while (1);
}
SORTOWANIE QUICKSORT ITER
qsort(int d[],int l,int p)
{ int s, stosl[n], stosp[n], pos;
pos=0;
do { if (l==p)
{ pos--;
if (pos>=0)
{ l=stosl[pos]; p=stosp[pos];}
}
else
{ s=partition(d,l,p);
stosl[pos]=s+1;
stosp[pos++]=p;
p=s;
}
} while(pos>=0);
}
PRZESZUKIWANIE DRZEWA WGLAB DFS
SEARCH_DEPTH (A,V)
{
DLA i:= 1, 2, ..., n {
V[i] := 0;
}
DLA i:= 1,2, ...,n {
JEZELI ( V[i] = 0 ) {
VISIT (A,V,i);
}
}
}
VISIT (G,V,i)
{
V[i] :=1;
DLA k:= 1,2,...,n {
JEZELI ( A[i,k] ≠ 0) {
JEśELI (V[k] = 0) {
VISIT (A,V,k);
}
PRZESZUKIWANIE DRZEWA WSZERZ BFS
SEARCH_BREADTH (A,V,s)
{
ENQUEUE (s,Q);
DOPOKI (! EMPTY(Q)) {
i:= DEQUEUE (Q);
V[i]:=1;
DLA kaŜdego k∈V {
JEśELI (A[i,k] ≠0) {
JEśELI (V[k]=0) {
ENQUEUE (k, Q)
V[k]:=1;
}
PRZEGLADANIE DRZEW BST
POPRZECZNE
INORDER (x)
{
JEśELI (x≠nil) {
INORDER (x.left);
P(x);
INORDER (x.right);
}
Metoda inorder
Dane wejściowe
L[ ]: - tablica list sąsiedztwa. Każda lista zawiera numery trzech wierzchołków: rodzica, lewego i prawego dziecka
v - numer węzła wejściowego
Lista kroków
inorder(v)
K01: Jeśli L[v].left > 0, wywołaj rekurencyjnie inorder(L[v].left)
K02: Przetwórz węzeł v
K03: Jeśli L[v].right > 0, wywołaj rekurencyjnie inorder(L[v].right)
K04: Zakończ
WZDLUZ
PREORDER (x)
{
JEśELI (x≠nil) {
P(x);
PREORDER (x.left);
PREORDER (x.right);
}
Metoda preorder
Dane wejściowe
L[ ]: - tablica list sąsiedztwa. Każda lista zawiera numery trzech wierzchołków: rodzica, lewego i prawego dziecka
v - numer węzła wejściowego
Lista kroków
preorder(v)
K01: Przetwórz węzeł v
K02: Jeśli L[v].left > 0, wywołaj rekurencyjnie preorder(L[v].left)
K03: Jeśli L[v].right > 0, wywołaj rekurencyjnie preorder(L[v].right)
K04: Zakończ
WSTECZ
POSTORDER (x)
{
JEśELI (x≠nil) {
POSTORDER (x.left);
POSTORDER (x.right);
P(x);
}
Metoda postorder
Dane wejściowe
L[ ]: - tablica list sąsiedztwa. Każda lista zawiera numery trzech wierzchołków: rodzica, lewego i prawego dziecka
v - numer węzła wejściowego
Lista kroków
postorder(v)
K01: Jeśli L[v].left > 0, wywołaj rekurencyjnie postorder(L[v].left)
K02: Jeśli L[v].right > 0, wywołaj rekurencyjnie postorder(L[v].right)
K03: Przetwórz węzeł v
K04: Zakończ
inorder : < 4 2 8 5 9 1 6 3 10 7 11 >
preorder : < 1 2 4 5 8 9 3 6 7 10 11 >
postorder : < 4 8 9 5 2 6 10 11 7 3 1 >
WYSZUKIWANIE W DRZEWIE BST REK
SEARCH_BST (x,v) // v-wyszukiwana wartość
// x wskaźnik do korzenia drzewa
{
JEśELI ((x=nil) ∪ (v=x.key) {
ZWROC (x);
}
JEśELI (v < x.key) {
ZWROC (SEARCH_BST (x.left,v));
} WPP {
ZWROC (SEARCH_BST (x.right, v));
}
WYSZUKIWANIE W DRZEWIE BST ITER
ITERATIVE_SEARCH_BST (x,v) // v - wyszukiwana wartość
// x wskaźnik do korzenia drzewa
{
DOPOKI (x≠nil) ∩ (v ≠x.key) {
JEśELI (v < x.key) {
x:= x.left;
} WPP {
x:= x. right;
{
ZWROC (x);
}
WSTAWIANIE X DO DRZEWA BST
INSERT_BST(v, x) // v - wstawiana wartość;
// x – korzeń drzewa;
{
JEśELI ( v < x.key ) {
left[x] := INSERT_BST(v, x.left);
} WPP {
JEśELI ( v > x.key ) {
x.right := INSERT_BST(v, x.right);
}
ZWROC (BST);
}
WYSZUKIWANIE V W DRZEWIE AVL, V- WSK do ROOT
SEARCH_AVL (x,v) // v-wyszukiwana wartość
// x wskaźnik do korzenia drzewa
{
DOPOKI (x≠nil) ∩ (v ≠x.key) {
JEśELI (v < x.key) {
x:= x.left;
} WPP {
x:= x. right;
{
ZWROC (x);
}
WYSZUKIWANIE WZORCA BRUTEFORCE
ALG_N (T,P,n,m)
{
DLA i:=1,2,…,n-m+1 {
j:=0;
DOPOKI (P[j+1]=T[i+j]){
j:=j+1;
}
JEZELI(j=m){
ZWROC (i)
}
} //przesunięcie;
}
WYSZUKIWANIE WZORCA ALG K_R
ALG_R-K (T,P,n,m,r,q)
{
hP:= h(P[1..m]); // inicjalizacja funkcji dla wzorca P
hT:= h(T[1..m]); // inicjalizacja funkcji dla tekstu T
rm1:= rm-1;
DLA i:=1, 2, … ,n-m+1 {
JEZELI (hP = hT) {
JEZELI (P[1..m]= T[i..i+m-1]){
ZWROC (i);
}
}
hT:=((hT-T[i]* rm1)*r+T[i+m])mod q;
METODA SHELLA
Dane wejściowe
n - liczba elementów w sortowanym zbiorze, n Î N
d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.
Dane wyjściowe
d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.
Zmienne pomocnicze
i - indeks elementu listy uporządkowanej, i Î N
j - zmienna sterująca pętli, j Î N
h - odstęp pomiędzy kolejnymi elementami podzbiorów, h Î N
x - zawiera wybrany ze zbioru element
Lista kroków
K01: h ← 1
K02: Powtarzaj h ← 3h + 1, aż h ≥ n
K03: h ← h div 9
K04: Jeśli h = 0, to h ← 1
K05: Dopóki h > 0: wykonuj kroki K06...K10
K06: Dla j = n - h, n - h - 1, ..., 1: wykonuj kroki 7...9
K07: ...