|
Реферат: Алгоритмы (Программирование)
PAIE?KA PAPRASTAME S?RA?E
1.1. Nuosekli paie?ka
Tegu ?ra?ai i?d?styti atsitiktinai kaip buvo ?ra?yti. Reikia surasti duot?
?ra?? pagal rakt?. Nuosekliai ie?kant reikia per?i?r?ti visus ?ra?us
nuosekliai.Vid.per?i?r?? ?ra?? sk. ie?kant yra Lap =L/2. Jei ?ra?o n?ra
teks per?i?r?ti visus ?ra?us L. Tarkim ie?komo ?ra?o su tikimybe p0 n?ra
s?ra?e, tada vid. per?i?r?t? ?ra?? sk. Lap=L*p0+(i(1L (i*pi ); pi=1-p0/L.
Ie?kant ?ra?o sutvarkytame faile(?ra?ai i?d?styti pagal rakt?) reikia
per?i?r?ti i? eil?s, tod?l vid. per?i?r?t? ?ra?? sk. tas pats: Lsp=L/2. Jei
ie?komo ?ra?o n?ra, tai paie?ka nutraukiama kai eilinis raktas bus didesnis
u? u?duot?. Atliekant k ?ra?? paie?k? nesutvarkytame faile vid. per?i?r?t?
?ra?? sk. Lkap = k * L / 2.
1.2. Paie?ka interpoliavimas
Jei s?ra?ai sur??iuoti ir ?inomas pirmo ?ra?o raktas K(1) ir paskutinio
K(n) tai galima apskai?iuoti p=X-K(1)/K(n)-K(1). X-ie?komo ?ra?o
raktas.Paie?k? pradedam nuo ?ra?o kurio numeris p*n.
1.3. Binarin? paie?ka
Naudojama sur??iuotame masyve. Jis dalinamas pusiau ir ie?komas raktas
lyginamas su vidurio raktu ir t.t.. Idealus masyvo dydis 2n-1.Jei 31 ?ra?as
reik?s 5 ?ingsni?, kad surasti ?ra?? 31(25-1. Bendru atveju 2n-1-1< N ( 2n-
1. Kai ?ra?? sk. bet koks, tai naudojami tokie alg.:
1) Pos?ra?io rib? nustatymo metodas. I?kiriame 2 markerius: V vir?utiniam
adresui ir A apatiniam adresui. Vidurinio ?ra?o adresas F(( (V+A) / 2 (.
Ie?komas ?ra?o raktas k palyginamas su F. Jei k(Fk, tai ?ra?as surastas,
jei k Fk, tai imam apatin? dal?, tada V(F+1, o A i?lieka tas pats ir t.t..
Toks dalinimas atliekamas tol, kol nepasidaro A(V. Rekurentin? lygtis
apra?anti max palyginim? sk. binarin?je paie?koje yra:
f(n)({1, n(1 f( ( n/2 ( )+1, n>1. Sprend?iant rekurentin? formul? galim
u?ra?yti: f(n) ( f( (n/2( ) + 1 ( f( (n/21( ) + 1(( f( (n/22( )+1) +
1 ( f( (n/22( )+2 (...( f( (n/2i( ) + i, kol
( n/2i ((1; i((logn(. f(n)((logn(+1 arba f(n) ( (log (n+1)( . Vid.
palyginim? sk. ideliu atveju kai n ( 2k-1:
f(n)(1* 1/n + 2*2/n + 3*4/n +...+ ((log n( + 1)*2k-1/n ( 1/n * (i(1(log
n(+1 (i * 2i-1). 2k-1-11 dideliems n).
Balansavimas (skaidymas ? vienodas dalis). Reikia sur??iuoti n ilgio masyv?
did?jimo tvarka. 1.surandam min, kur? sukei?iam su pirmu, po to i? (n-1)
elemento surandam min ir sukei?iam su antru ir t.t.. Rekursyvin? lygtis
apra?anti palyginim? sk.: T(n) ( {0, n(1T(n-1)+n-1, n>1 ;
T(n) ( n(n-1)/2, o algoritmo sud?tingumas ((n2). ?ia skaldymas ? dvi
nelygias dalis: ? vieno elemento ir (n-1).2. Gaunamas suskald?ius u?davin?
? dvi lygias dalis ( n/2. Tarkim, kad n ( 2k. Viena dalis nuo x1 iki xn/2 ,
o kita nuo xn/2+1 iki xn. ?ias dalis sur??iuojam ir sujungiam palyginant
minimalius elementus. Sujungimui reiks maksimum n-1 palyginim?. Tok?
skaidym? galima rekursyviai t?sti toliau, kol lieka dalyse po 1 element?.
Rekursyvin? lygtis apra?anti tok? algoritm? yra:
T(n) ( {0, n(1 2T(n/2) + n - 1, n>1.
?io algoritmo sud?tingumas (( n log n).
Dinaminis programavimas.
Kartais galima efektyvius algoritmus gauti naudojant dinamin? programavim?.
?iuo b?du reik?t? skai?iuoti visus dalinius u?davnius, bet sprend?iami nuo
ma?? prie dideli?. Atsakymai prisimenami lentel?je ir u?daviniai jungiami,
kad b?t? i?spr?stas visas u?davinys ir gautas optimumas. Pvz. sudauginant n
matric? yra labai svarbus daugybos eili?kumas, kuris nulemia bendr? veiksm?
skai?i?. Pa?ymim mi j minimalus veiksm? sk. dauginant matricas:
Mi*Mi+1*...*Mj, kur 1 ( i < j ( n. Kai M ( M1*M2*...*Mn, tai j? mati?kumas
yra r0*r1*r2*...*rn.
mi j ( {0, i(j MIN( mik + mk+1, j + ri-1 rk rj ),
j > i, i ( k < j (1).
M` (Mi*Mi+1*...*Mk, [ri-1*rk]. Min vei-ksm? sk. mi,k.
M``(Mk+1 *Mk+2 *... * Mj, [rk*rj].
Atliekant ?i? daugyb? min veiksm? sk. mk+1, j, o sudauginant M` su M``,
min veiksm? sk. ri-1 rk rj. Tai atliekam tol kol negaunam m1n.1-a lygtis
ya dinaminio programavimo rekurentin? lygtis. mi,j reik?m?s skai?iuojamos
tvarka, kai did?ja indeks? sk. I? prad?i? skai?iuojam mi,i( 0 (visiem i),
toliau mi, i+1, po to mi, i+2, kol neprieinam m1n.
R??IAVIMO ALGORITMAI
K-ma?i? korte?? r??iavimas
Tegul mes turime sek? A1 A2 ... An k-ma?i? korte??, t.y., A erdvinis Ai
elementas, sudarytas i? ai1 ai2 ... aik.Reikia ?i? sek? r??iuoti taip: B1
B2 ... Bn, kad visiem i Bi ( Bi+1. R??iavimas atliekamas k kart? pereinant
per duot? sek?. Pirm? kart? atliekamas r??iavimas pagal k-?j? komponent?.
Antr? kart? pagal (k-1) komponent? ir t.t. Pr?jus pagal i-?j?, tur?sim
s?ru?iuot? sek?. Kiekviena skiltis ai j yra nuo 0 iki m-1. Reikia
organizuoti m pagalbini? eili? Q(j), kur j ( 0,...,m-1, kurios i? prad?i?
turi b?ti tu??ios. Duomenis A1 A2 ... An i? prad?i? sura?om ? s?ra?? EIL?.
Paimam eilin? korte?? Ai i? EIL?S ir patalpinam ? pagalbin? eil? Q(j) pagal
analizuojamos komponent?s reik?m?. Taip darom tol, kol bendra EIL?
i?tu?t?ja. Visi korte?ai atsiduria pagalbin?se eil?se. Po to jie suduriami:
Q(0) Q(1)...Q(m-1) ir jie sudaro vien? bendr? eil? EIL?. Kai praeinam pro
visas komponentes, tai EIL? bus sur??iuota. Algoritmo sud?tingumas yra
tiesinis ([(n+m)/k]. Naudoti ?? metod? neverta, kai n yra ma?as.
Nevienodo ilgio korte?? r??iavimas
Kad suvienodinti korte?? ilgius galima priekyje prira?yti nulius, ta?iau
tai ne efektyvu, nes bus bereikaling? daug per?i?r?jim?. Tuomet tegul lmax-
korte?? maksimalus ilgis, tai reikia i? prad?i? sur??iuoti maksimalaus
ilgio korte?us pagal l max paskutin? komponent?. Reik?s lmax kart? r??iuoti
visus korte?us.Antr? kart? reikia r??iuoti korte?us, kuri? ilgis lmax -1 ir
jau sur??iuotus pagal paskutin? komponent?, kuri? ilgis lmax. Ir paskutin?
kart? lmax per?jus per vis? s?ra??, bendram s?ra?e bus sur??iuota seka.
Pastabos: 1. Prie? naudojant ?? algoritm?, visi korte?ai turi b?ti
i?skirstyti pagal ilgius. Tam formuojami s?ra?ai ILGIS(l), kur l (
1,...,lmax, kuriuose sura?yti atitinkamo ilgio korte?ai. Pirmame ?ingsnyje
r??iuojamas tik s?ra?as ILGIS(lmax) pagal paskutin? komponent?. 2. Be to
matom, kad pra?jus kart? pro vien? komponent? gali b?ti daug pagalbini?
eili? Q(i) (kur i ( 0,1,...,m-1) tu??ios. Ne?i?rint to jas visas reikia
jungti ? bendr? s?ra??, tod?l naudinga b?t? i? prad?i? nustatyti kurios
pagalbin?s eil?s bus netu??ios ir tik jas jungti ? vien? bendr? s?ra??.
R??iavimas lyginant elementus
“Burbuliuko” metodas. Paprastai elementai r??iuojami pagal raktin? ?od?.
Tarkim turim K1..K16 element? ir lyginame K1 >K2. Jeigu daugiau sukei?iam
vietom. Jeigu ne nieko nedarom ir t.t. Paskutinis palyginimas bus Km > Kn.
Po 1 iteracijos did?iausias skai?ius atsiranda pabaigoje. Sekanti iteracija
vyksta su n-1 elementu, nes paskutinio neimame ir t.t.
Pirmoje iteracijoje bus (n-1) palyginim?. Antroje iteracijoje (n-2), i-
tojoje iteracijoje (n-i).
Tuomet bendras palyginim? skai?ius bus
[pic]
Kadangi ne visuomet elementai sukei?iami, tuomet jeigu i?r??iuota seka bus
0 pakitim?, o atvirk??iai i?r??iuota seka - n(n-1)/2 pakeitim?. Tada
vidutinis pakeitim? sk. bus n(n-1)/4.
Jeigu yra n element? seka, tai i? jos gali b?ti padaryti n! sek?. Mes
laikome kad bet kuri seka gali pasitaikyti su vienoda tikimybe 1/n!.
Kiekvienai sekai galima para?yti inversi?k? sek?. Jeigu turime tokias 2
sekas, ir jas sur??iuosime, tai sumalinis pakeitim? sk. bus n(n-1)/4.
Algoritmo sud?tingumas ((n2).
Iterpimo metodas.
?ia eilinis elementas yra ?terpiamas ? jau sur??iuot? elemet? sek?. Tegul
turime n element? i? viso ir turime jau i sur??iuot? element?. Mums reikia
?terpti i+1 element? Ki+1. Ki+1 atsidurs tarp Kj < Ki+1 < Kj+1 element?.
?statant i+1 element? mums reik?s max palyginim? (su 1, su 2…).Max
palyginim? sk. b?t?:
[pic]Pagal tai ir algoritmo sud?tingumas bus ((n2).Vidutini?kai bus ma?iau
palyginim?.?iuo b?du r??iuojant masyvus (paprastus) patogiau prad?ti elemt?
lyginim? nuo sur??iuotos sekos pabaigos. Tai yra nuo i-tojo elemento.
Panagrin?kime koks ?iame algoritme yra vidutinis palyginim? sk. Tegul
turime i sur??iuot? elemt? ir reikia ?statyti I+1 element?. Pirmiau
lyginsime su 1 elememtu. Yra i+1 pozicijos, ? kurias galima ?statyti i+1
element? ir priekyje ir gale. Laikome, kad i+1 elementas ? bet kuri?
pozicij? gali patekti su vienoda tikimybe 1/(i + 1). Vidutinis palyginim?
sk. ?statant element? bus:
[pic]jei patenka ? paskutin?
prie? pirm?j? pozicij?
element? (gale)
=1/(i+1)(1+2+…+i+i) = 1/(i+1)*((i+1)/i ) /2 + i / ( i + 1 ) = i / 2 + i / (
i + 1 )
Tiek pagal max,tiek pagal vidutin? palyginim? skai?i? ?io algoritmo
sud?tingumas yra ((n2)
Ekspermentinis statistinis algoritm? tyrima.s ?iuo metodu pvz. tiriant
r??iavimo algoritmus mums reikia para?yti atitinkam? program?, paiimti
atsitiktin? sek? i? n duomen? ir atlikti skai?iavimus, pvz.: fikstuoti
laik? t1, po to paimame kit? sek? ir gauname laik? t2 po to paimame kit?
sek? taip pat i? n duomen? ir gauname laik? t3 ir tokius bandymus kartojame
k kart?. Gauname atsitiktini? dyd?i? imt? t1, t2, …. tk. Vidurkis bus ( =
1/K(i(1K (ti), vidurkis - atsitiktinis dydis.
Dirpersija bus : S2(t)=[pic]i-t)2= =[pic]ti2-2(t ti +(t2) = =[pic] ti2-
2t[pic]ti+K(t2]= =[pic][pic]ti2-2([pic][pic]ti)* *[pic]ti + K/K2
([pic]ti)2] = [pic]* *[ [pic]ti2 - [pic]( [pic]ti)2]
?i dispersijos fomul? patogesn? ma?ininiuose skai?iavimuose, nes su
kiekvienu nauju atsitiktiniu dyd?iu ti mes kaupiame tik dvi sumas : (ti ir
(ti2.(t - atvirk?tinis dydis ir jis vertina tam tikr? matematin? vilt?.(t
dispersija yra tokia: D((t )= D [[pic][pic]ti] = 1/K2[pic] D(ti) =
1/K*D(t); D - tikroji dispersija;S-?vertinimas.S2((t)=S2(t)/K arba
i?traukus ?akn?: S(t) = S(t)/[pic]; |(t - m| a2
Jei a6 < a3, tai reikia palyginti ir ar a3 > a6
Radom max per 2 palyginimus. Pirami-d?je radom per n-1 palyginim?. Tai yra
sekantis randamas per (log n( -1 palygi-nim?. Gauname, kad ?iuo metodu
palygi-nim? sk. yra optimalus: n + (log n( - 2 .
Geriausio (max) ir blogiausio (min) elemento i?rinkimas
Galima si?lyti suskaidyti sek? n ? 2 dalis ir sura?yti ?iose dalyse max ir
min elementus. Palyginus max-ius elementus gaunamas max-is elementas, min-
ius -min-is. Rekursyviai galima suskaidyti iki 1,2 element?. Palyginant 2
elementus tarpusavyje i? karto gauname max ir min elementus. Rekurentin?
lygtis, apra?anti tok? akgoritm?:
f(n)=[pic]
Bendras ?ios srities sprendinys:
|[pic|(n-2(log |
|] |n()/2, kai|
| |n =k, tai imame S1, kuriame yra (i-
1) ele-t?. Jei iBitmap);
ToImage->Visible = false;
ToImage->Visible = true;
}
//----------------------------------------------------------------------
-----
Листинг 4. Модуль выделения контуров.
Файл заголовка:
//----------------------------------------------------------------------
-----
#ifndef GraphicUnitH
#define GraphicUnitH
//----------------------------------------------------------------------
-----
#include
extern void AlgorithmBeatle(Graphics::TBitmap* FromImage,
Graphics::TBitmap* ToImage);
extern void AlgorithmScan(Graphics::TBitmap* FromImage,
Graphics::TBitmap* ToImage);
#endif
cpp файл:
//----------------------------------------------------------------------
-----
#include
#pragma hdrstop
#include "GraphicUnit.h"
//----------------------------------------------------------------------
-----
#pragma package(smart_init)
#include
/*
Отслеживающий алгоритм выделения контуров
"Алгоритм жука"
*/
void AlgorithmBeatle(Graphics::TBitmap* FromImage,
Graphics::TBitmap* ToImage)
{
typedef enum {North, East, South, West} TDirectional;
int X,Y; // Координаты первой встречи с объектом
int cX,cY; // Текущие координаты маркера
Byte *Line, *ToLine; // Обрабатываемые линии
Byte B; // Значение текущего пиксела
TDirectional Direct; // Направление движения жука
// Идем до тех пор, пока не встретим черную область
for (Y = 0; Y < FromImage->Height; Y++)
{
Line = (Byte*)FromImage->ScanLine[Y];
for (X = 0; X < FromImage->Width; X++)
{
B = Line[X];
if (B < 255)
break;
}
// Если встречен объект, отличающийся от цвета фона (255 - белый)
// прервать поиск
if (X != FromImage->Width)
break;
}
// Если не нашли ни одного черного пиксела, то выходим из процедуры
if ((X == FromImage->Width) && (Y == FromImage->Height))
return;
// Если все нормально, начинаем обход по алгоритму жука
ToLine = (Byte*)ToImage->ScanLine[Y];
ToLine[X] = 0;
// Поворачиваем налево (новое направление - север)
cX = X;
cY = Y - 1;
Direct = North;
Line = (Byte*)FromImage->ScanLine[cY];
// Пока не придем в исходную точку, выделяем контур объекта
while ((cX != X) || (cY != Y))
{
// В зависимости от текущего направления движения жука
switch (Direct)
{
// Север
case North:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)
{
ToLine = (Byte*)ToImage->ScanLine[cY];
ToLine[cX] = 0;
Direct = West;
cX--;
}
// Иначе поворачиваем "направо"
else
{
Direct = East;
cX++;
}
}
break;
// Восток
case East:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)
{
ToLine = (Byte*)ToImage->ScanLine[cY];
ToLine[cX] = 0;
Direct = North;
cY--;
Line = (Byte*)FromImage->ScanLine[cY];
}
// Иначе поворачиваем "направо"
else
{
Direct = South;
cY++;
Line = (Byte*)FromImage->ScanLine[cY];
}
}
break;
// Юг
case South:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)
{
ToLine = (Byte*)ToImage->ScanLine[cY];
ToLine[cX] = 0;
Direct = East;
cX++;
}
// Иначе поворачиваем "направо"
else
{
Direct = West;
cX--;
}
}
break;
// Запад
case West:
{
B = Line[cX];
// Если элемент "черный", поворачиваем снова "налево"
if (B < 255)
{
ToLine = (Byte*)ToImage->ScanLine[cY];
ToLine[cX] = 0;
Direct = South;
cY++;
Line = (Byte*)FromImage->ScanLine[cY];
}
// Иначе поворачиваем "направо"
else
{
Direct = North;
cY--;
Line = (Byte*)FromImage->ScanLine[cY];
}
}
}
}
}
// ---------------------------------------------------------------------
------
void AlgorithmScan(Graphics::TBitmap* FromImage,
Graphics::TBitmap* ToImage)
{
// Тип ветви (левая или правая)
typedef enum {bLeft, bRight} TBranchType;
// Структура, описывающая ветвь
struct TBranch
{
TBranchType BranchType; // Тип ветви
TBranch* Branch; // Парная ветвь
};
// Структура, описывающая строку
struct TString
{
int BeginX; // Начало черной серии
int EndX; // Конец черной серии
TBranch* Branch; // Указатель на структуру ветви
};
// Возможные ситуации
typedef enum {
sBegin, // Начало
sNext, // Продолжение
sBranch, // Ветвление
sFusion, // Слияние
sEnd // Конец
} TSituation;
// Сканируемая полоса
struct TLine
{
Byte* L1; // Верхняя линия
Byte* L2; // Нижняя линия
};
int Y; // Текущая координата Y
int X; // Текущая координата X
int cX; // Временная координата X для сканирования
TLine Line; // Сканируемая полоса
TSituation CurrentSituation; // Текущая ситуация
for (Y = 0; Y < FromImage->Height; Y++)
{
Line.L1 = (Byte*)FromImage->ScanLine[Y];
Y++;
Line.L2 = (Byte*)FromImage->ScanLine[Y];
// Пробуем выявить ситуации:
// Ищем первый черный элемент во второй линии сканируемой полосы
for (X = 0; X < FromImage->Width; X++)
{
if (Line.L2[X] < 255)
{
// Если черный элемент найден, пытаемся уточнить ситуацию
CurrentSituation = sBegin;
for (cX = X; cX < FromImage->Width; cX++)
{
}
}
}
}
}
| |
