AJS
AJS
Programiści na ogół wyróżniają
pięć obszarów pamięci
1. obszar zmiennych globalnych
2. wolna pamięć (sterta, stos - heap)
np. zmienne
dynamiczne
3. rejestry
do wewnętrznego zarządzania funkcjami
4. kod programu
program
5. stos procesora (stos - stack)
zmienne lokalne wraz z
parametrami funkcji
AJS
AJS
Zmienne
-reprezentują pewien obszar pamięci o ściśle
określonym rozmiarze,
-istnieją od momentu przydzielenia pamięci do momentu
jej zwolnienia,
Podział zmiennych ze względu na zasięg i widoczność:
lokalne
globalne
Podział zmiennych ze względu na czas trwania:
statyczne
pamięć przydzielana statycznie
tryby
automatyczne
pamięć przydzielana automatycznie
zarządzania
dynamiczne
pamięć przydzielana dynamicznie
pamięcią
AJS
AJS
Zarządzanie
pamięcią
automatyczne przydzielanie pamięci
–
dotyczy zmiennych
lokalnych, można użyć słów kluczowych
auto
lub
register
pamięć
przydzielana jest przez system operacyjny w momencie napotkania
definicji zmiennej i automatycznie zwalniana po zakończeniu bloku
zawierającego definicję tej zmiennej
auto
– jest przyjmowany domyślnie
register
– informuje kompilator o umieszczeniu zmiennej w rejestrach
statyczne przydzielanie
pamięci
–
dotyczy zmiennych
globalnych oraz zmiennych zadeklarowanych z użyciem słów
kluczowych
static
lub
extern
, pamięć przydzielana jest jednorazowo od
momentu napotkania definicji zmiennej do momentu zakończenia
programu
static –
zmienne są widoczne tylko w obrębie modułu,
extern
- informacja dla kompilatora że zmienna została
zadeklarowana w innym module i tam przydzielono jej pamięć
AJS
AJS
#include<iostream.h>
#include<conio.c>
int zmiana(void);
int a;
//zmienna globalna
extern int d;
main()
{
static float c;
a=1;
cout<<"wartosc zmiennej a="<<a<<endl;
a=zmiana();
cout<<"wartosc zmiennej a="<<a<<endl;
getch();
return 0;
}
int zmiana(void)
{
int b=100;
//zmienna lokalna
a+=b;
return a;
}
AJS
AJS
Zarządzanie
pamięcią
Programista nie ma bezpośredniego wpływu na
tworzenie i usuwanie zmiennych statycznych i
automatycznych
dynamiczne przydzielanie pamięci
–
umożliwia programiście
tworzenie i usuwanie zmiennych a tym samym pełne sterowanie
czasem ich istnienia. Zmienne przechowywane są w specjalnie
wydzielonym obszarze pamięci zwanym stosem zmiennych
dynamicznych (ang. heap). Do przydzielania i zwalniania służą słowa
kluczowe
new
i
delete.
new –
do
przydzielania pamięci dynamicznej
delete –
do zwalniania pamięci dynamicznej
Dostęp do zmiennych dynamicznych umożliwiają
wskaźniki
AJS
AJS
Zarządzanie
pamięcią
dynamiczne przydzielanie pamięci
Składnia
int *p;
p=new int (45);
lub
int *p=new int (45);
delete p;
deklaracja
wskaźnika
alokacja pamięci
dynamicznej na stosie
zainicjowanie wartości
zwalnianie pamięci
AJS
AJS
#include<iostream.h>
#include<conio.c>
main()
{
int *p=new int (45);
if(p==0)
//zabezpieczenie przed brakiem alokacji pamięci
{
cout<<"nie przydzielono pamieci"<<endl;
return 1;
}
cout<<"*p="<<*p<<endl;
cin>>*p;
cout<<"*p="<<*p<<endl;
delete p;
cout<<*p;
getch();
return 0;
}
AJS
AJS
Dynamiczna alokacja tablic
Zarządzanie
pamięcią
Składnia
int *p;
p=new int [10];
lub
int *p=new int [10];
delete []p;
deklaracja
wskaźnika
alokacja pamięci
dynamicznej na stosie
wymiar tablicy
zwalnianie pamięci
AJS
AJS
#include<iostream.h>
#include<conio.c>
main()
{
int i;
int *p=new int[10];
if(p==0)
//zabezpieczenie przed brakiem alokacji
pamięci
{
cout<<"nie przydzielono pamieci"<<endl;
return 1;
}
for(i=0;i<10;i++)
{
p[i]=i;
cout<<p[i]<<endl;
}
delete []p;
getch();
return 0;
}
AJS
AJS
Rekurencja
(rekursja)
pewien mechanizm rozwiązywania problemów
Rozwiązanie rekurencyjne charakteryzuje się
następującymi cechami
-zakończenie algorytmu jest jasno określone,
-"duży" problem został rozłożony na problem
elementarny (który umiemy rozwiązać) i na problem o
mniejszym stopniu skomplikowania.
AJS
AJS
Funkcje
rekurencyjne są
to funkcje, które
wywołują same
siebie.
Funkcje rekurencyjne
muszą zawsze zawierać
warunek stopu
(zatrzymania)
AJS
AJS
Problem
Znaleźć w tablicy składającej się z n liczb
całkowitych liczbę x
Jak postępować w sposób rekurencyjny:
1. Wziąć pierwszy niezbadany element tablicy n-
elementowej,
2. Jeśli aktualnie analizowany element jest równy x to:
wypisz "sukces" i zakończ;
w przeciwnym wypadku
zbadaj pozostałą część tablicy n-1-elementowej;
Warunkiem zakończenia programu jest albo znalezienie x albo wyjście
poza obszar poszukiwań.
AJS
AJS
#include <iostream.h>
#include <conio.h>
const
n=10;
int
tab[n]={1,2,3,2,-7,44,5,1,0,-3};
void szukaj(int tab[n],int lewa,int prawa,int x)
// lewa, prawa = lewa i prawa
granica obszaru poszukiwan
// tab = tablica
{
// x = wartosc do odnalezienia
if (lewa>prawa)
cout << "Element " << x << " nie zostal odnaleziony\n";
else
if (tab[lewa]==x)
cout << "Znalazlem szukany element "<< x << endl;
else
szukaj(tab,lewa+1,prawa,x);
}
void main()
{
clrscr();
szukaj(tab,0,n-1,7);
szukaj(tab,0,n-1,5);
getch();
}
Funkcja wywołuje samą
siebie
Deklaracja i
definicja funkcji
rekurencyjnej
AJS
AJS
Jak wykonują się programy rekurencyjne
1 dla n=0
n!=
n*(n-1)! dla n>=1
unsigned
long
int
silnia(int x)
{
if (x==0)
return 1;
else
return x*silnia(x-1);
}
Funkcja wywołuje samą
siebie
AJS
AJS
Drzewo wywołań funkcji silnia(4)
4*3
!
x==
0
nie!
I
3*2
!
x==
0
nie!
II
2*1
!
x==
0
nie!
II
I
1*0
!
x==
0
nie!
IV
1
x==
0
tak!
V
AJS
AJS
Niebezpieczeństwa rekurencji
-czasami
znaczna
część
obliczeń
jest
wykonywana więcej niż jeden raz,
-przepełnienie stosu (stack overflow), programy
rekurencyjne
są
zazwyczaj
pamięciożerne
(zawieszenie komputera)
:nieprawidłowe
lub
niejasne
określenie warunków zakończenia programu,
:brak pamięci
-nieskończona ilość wywołań rekurencyjnych,
AJS
AJS
#include <iostream.h>
int StadDoWiecznosci(int n)
//deklaracja i
definicja funkcji
{
if (n==1)
return 1;
else
if ((n %2) == 0) // n parzyste
return StadDoWiecznosci(n-2)*n;
else
return StadDoWiecznosci(n-1)*n;
}
void main()
{
int x;
cout<<"Podaj wartosc x:";
cin>>x;
cout << StadDoWiecznosci(x) << endl;
//wywołanie funkcji
}
Proces
upraszczania nie
doprowadzi do
przypadku
elementarnego
czyli n=1
nieskończona
ilość
wywołań
rekurencyjnych
AJS
AJS
Algorytmy sortowania
Sortowanie wewnętrzne –używanie wyłącznie pamięci
wewnętrznej komputera
sortowanie przez wstawianie (insert),
sortowanie bąbelkowe (bubble),
sortowanie szybkie (quicksort).
AJS
AJS
Sortowanie przez wstawianie (insert),
Metoda ta jest informatyczną techniką
sortowania analogiczną do techniki stosowanej
przez graczy przy układaniu kart
2
3
7
9
1
0
6
8
5
4
2
3
7
9
1
0
6
8
5
4
Karty
posortowane
Karty do
posortowania
AJS
AJS
#include <iostream.h>
#include <conio.h>
void wstawianie(int *tab);
const inst n=13;
int tab[n]={40,2,1,12,6,18,20,29,32,23,34,39,41};
void main()
{
clrscr();
cout<<"Tablica przed sortowaniem"<<endl;
for (int i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
wstawianie(tab);
cout<<"Tablica po sortowaniu"<<endl;
for (i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
getch();
}
Sortowanie przez wstawianie (insert) -
program
AJS
AJS
void wstawianie(int *tab)
{
for(int i=1; i<n;i++)
{
int j=i;
//
0..i-1 jest juz
posortowane
int tymczas=tab[j];
while ((j>0) && (tab[j-1]>tymczas))
{
tab[j]=tab[j-1];
j--;
}
tab[j]=tymczas;
}
}
Sortowanie przez wstawianie (insert) –
program cd.
AJS
AJS
Sortowanie bąbelkowe (bubble),
W sortowaniu bąbelkowym analizowane są ze sobą zawsze
dwa sąsiadujące elementy i jeśli nie są uporządkowane to
następuje ich zamiana
4
0
2
3
9
6
1
8
4
2
0
2
4
0
4
3
9
6
1
8
2
0
2
4
4
0
6
3
9
1
8
2
0
2
4
6
4
0
1
8
3
9
2
0
2
4
6
1
8
4
0
2
0
3
9
2
4
6
1
8
2
0
4
0
3
9
2
4
6
1
8
2
0
3
9
4
0
0
1
2
3
4
5
6
indeks w
tablicy
etapy sortowania
0 1 2 3 4
5 6
AJS
AJS
#include <iostream.h>
#include <conio.h>
const int n=7;
int tab[n]={40,2,39,6,18,4,20};
void babelki(int *tab);
void main()
{
clrscr();
cout<<"Tablica przed
sortowaniem"<<endl;
for (int i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
babelki(tab);
cout<<"Tablica po sortowaniu"<<endl;
for (i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
getch();
}
Sortowanie bąbelkowe (bubble) - program
AJS
AJS
void babelki(int *tab)
{
for (int i=1;i<n;i++)
{
for (int j=n-1;j>=i;j--)
if (tab[j]<tab[j-1])
{
//zamiana
int tmp=tab[j-1];
tab[j-1]=tab[j];
tab[j]=tmp;
}
}
}
Sortowanie bąbelkowe (bubble) – program
cd.
AJS
AJS
"Puste przebiegi" -
Niekorzystne konfiguracje danych
Sortowanie bąbelkowe (bubble) – wady
void ShakerSort(int *tab)
{
int lewa=1,prawa=n-1,k=n-1;
do
{
for(int j=prawa; j>=lewa; j--)
if(tab[j-1]>tab[j])
{ zamiana(tab[j-1],tab[j]);
k=j; }
lewa=k+1;
for(j=lewa; j<=prawa; j++)
if(tab[j-1]>tab[j])
{ zamiana(tab[j-1],tab[j]);
k=j; }
prawa=k-1;
}
while (lewa<=prawa);
}
AJS
AJS
Sortowanie szybkie (quicksort)
Procedura sortowania dzieli się na :
- część służącą do właściwego sortowania, która nic nie
robi tylko wywołuje sama siebie zapewniając "sklejanie"
wyników cząstkowych,
- procedurę (funkcji) rozdzielania elementów tablicy
względem pewnej komórki służącej za oś podziału
element<'P'
element
osiowy 'P'
element >='P'
Podział tablicy w metodzie
quicksort
AJS
AJS
Zasada działania procedury
quicksort
'P'
<'P'
'P'
>='P'
quicks
ort
quicks
ort
quicks
ort
ETAP I
ETAP
II
AJS
AJS
2
9
4
0
2 1 6 1
8
2
0
3
2
2
3
34 39 41
2
9
2 1 6 1
8
2
0
2
3
4
0
3
2
3
4
3
9
4
1
1
6 1
8
2
0
2
3
2
4
0
3
2
3
4
3
9
4
1
AJS
AJS
Zwięzły zapis procedury quicksort
void quicksort (int *tab, int lewa, int prawa)
{
if (lewa<prawa)
{
int m;
//podziel tablicę względem elementu osiowego;
// P=pierwszy element, czyli tab[lewa];
//pod koniec podziału element 'P' zostanie
//przeniesiony do komórki numer 'm';
quicksort(tab,lewa,m-1);
quicksort(tab,m+1,prawa);
}
}
Wywołania
rekurencyjne
AJS
AJS
#include <iostream.h>
#include <conio.h>
const int n=15;
int
tab[n]={34,56,23,40,29,2,1,6,18,20,32,34,39
,23,41};
void zamiana(int &a,int &b);
void quicksort(int *tab,int lewa, int prawa);
void main()
{
clrscr();
cout<<"Tablica przed sortowaniem"<<endl;
for (int i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl<<endl;
quicksort(tab,0,n-1);
cout<<"Tablica po sortowaniu"<<endl;
for (i=0;i<n;i++)
cout << tab[i] <<" ";
cout << endl;
getch();
}
AJS
AJS
Funkcja zamiana
void zamiana(int
&a,int &b)
{
int tymczas=a;
a=b;
b=tymczas;
}
void quicksort(int *tab,int lewa,
int prawa)
{
if (lewa < prawa)
{
int m=lewa;
for(int
i=lewa+1;i<=prawa;i++)
if
(tab[i]<tab[lewa])
zamiana(tab[+
+m],tab[i]);
zamiana(tab[lewa],tab[m]);
quicksort(tab,lewa,m-1);
quicksort(tab,m+1,prawa);
}
}
Procedura (funkcja)
quicksort
AJS
AJS
Algorytmy przeszukiwania
przeszukiwanie liniowe
przeszukiwanie binarne
AJS
AJS
#include <iostream.h>
#include <conio.h>
const int n=10;
int tab[n]={1,2,3,2,-7,44,5,1,0,-3};
int szukaj(int tab[n],int x)
{
for(int i=0;(i<n)&&(tab[i]!=x);i++);
return i;
}
void main()
{
clrscr();
cout << szukaj(tab,7) <<endl;
cout << szukaj(tab,-3) <<endl;
getch();
}
Postać iteracyjna
przeszukiwania
liniowego
Przeszukiwanie liniowe
AJS
AJS
void szukaj(int tab[n],int lewa,int prawa,int x)
{
if (lewa>prawa)
cout << "Element " << x << " nie zostal
odnaleziony\n";
else
if (tab[lewa]==x)
cout << "Znalazlem szukany element
"<< x << endl;
else
szukaj(tab,lewa+1,prawa,x);
}
Postać rekurencyjna przeszukiwania
liniowego
AJS
AJS
Przeszukiwanie binarne
Dotyczy przeszukiwania tablicy posortowanej
Łatwo można wyeliminować obszary tablicy w
których szukany element na pewno nie
wystąpi.
przeszukiwanie liniowe a przeszukiwanie
binarne
Liniowe jest bardziej czasochłonne
Np. w tablicy 20000 elementowej
- 20000 porównań -liniowe
- 14 porównań -binarne
AJS
AJS
#include <iostream.h>
#include <conio.h>
const int n=12;
int tab[n]={1,2,6,18,20,23,29,32,34,39,40,41};
int szukaj(int tab[],int x);
void main()
{
clrscr();
cout << szukaj(tab,6)<<endl;
getch();
}
Przeszukiwanie binarne
iteracyjna wersja algorytmu
AJS
AJS
int szukaj(int tab[],int x)
{
enum {TAK,NIE} Znalazlem=NIE;
int lewa=0,prawa=n-1,srodek;
while(lewa<=prawa && Znalazlem!
=TAK)
{
srodek=(lewa+prawa)/2;
if(tab[srodek]==x)
Znalazlem=TAK;
else
if(tab[srodek]<x)
lewa=srodek+1;
else
prawa=srodek-1;
}
if(Znalazlem==TAK)
return srodek;
else
return -1;
}
Przeszukiwanie binarne -
iteracja
AJS
AJS
#include <iostream.h>
#include <conio.h>
int szukaj_rec(int * tab,int x,int lewa,int prawa);
void main()
{
clrscr();
int tabl[12]={1,2,6,18,20,23,29,32,34,39,40,41};
cout << "wynik="<<szukaj_rec(tabl,23,0,11)<<endl;
getch();
}
Przeszukiwanie binarne
rekurencyjna wersja algorytmu
AJS
AJS
int szukaj_rec(int * tab,int x,int lewa,int prawa)
{
if(lewa>prawa) return -1;
// element nie
znaleziony
else
{
int srodek=(lewa+prawa)/2;
if(tab[srodek]==x) return srodek;
// element
został znaleziony!
else
if(x<tab[srodek])return
szukaj_rec(tab,x,lewa,srodek-1); else
return
szukaj_rec(tab,x,srodek+1,prawa);
}
}
Przeszukiwanie binarne
-rekurencja
AJS
AJS
Przeszukiwanie tekstów
Algorytm typu
brute-force
poszukiwanie wzorca
K O
T E L
E E K S
Z
T E L
E F O N
wzorzec w
badany
tekst t
0 j M-1
0 i
N-1
fragmenty (jeszcze)
zgodne
AJS
AJS
#include <iostream.h>
#include <conio.h>
#include <string.h>
// z
uwagi na strlen
int szukaj(char *w,char *t)
void main()
{
clrscr();
char *b="abrakadabra",*a="rak";
cout << szukaj(a,b) << endl;
getch();
}
Przeszukiwanie tekstów -
program
AJS
AJS
int szukaj(char *w,char *t)
{
int
i=0,j=0,M=strlen(w),N=strlen(t);
while(j<M && i<N)
{
if(t[i]!=w[j]) {i-=j-1;j=-1;}
i++;j++;
}
if(j==M) return i-M; else return -1;
}
Algorytm typu brute-force