Іздеу алгоритмдері
Жоспар.
Кіріспе.............................................................................................................3
Негізгі бөлім...................................................................................................4
1. Іздеу әдістері – сызықты және бинарлы..........................................
1.1 Іздеу алгоритмдері.........................................................................4
1.2 Linearsearch подпрограммасы......................................................5
1.3 Linearsearch функциясының қолданылуы...................................7
2. Сызықты іздеу......................................................................................8
2.1 Сызықты іздеудің алгоритмін талдау.............................9
3. Бинарлы (қосарлы) іздеу....................................................10
3.1 Екіге бөлу арқылы (Бинарлы) іздеу...............................13
3.2 Бинарлы іздеу әдісі..........................................................13
3.3 Бинарлы іздеу алгоритмі.................................................17
3.4 Бинарлы іздеу алгоритмін программа түрінде іске асыру..18
3.5 Бинарлы іздеудің алгоритмін талдау..............................20
4. Барьермен іздеу.......................................................................21
Қорытынды.....................................................................................................24
Әдебиеттер тізімі.............................................................................................25
Кіріспе
Жоғары деңгейлі программалау тілдерінің бірі – бұл Паскаль
тіл алгоритм құрылымын сақтап құрылған. Мұнда программаны бірте-бірте
тілге дамытылған берілгендер типтері енгізілген. Олар өңделетін берілгендер
мұнда кішігірім жеңіл программалармен бірге күрделі құрылымды программаларды
тіл синтаксисі қиын емес, тура Бейсиктегідей; операторлардың
Паскаль тілінде құрылған программаны мәшинелік кіріспе тілге аудару
Турбо Паскальда программалау тәсілдері өте көп және жиі
меншіктеу белгісі “ := “ түрінде жазылады;
санды дәрежелеу белгісі жоқ. Оның орнына санды өзіне-өзін
мәтіндер, символдар тырнақшаның ішіне емес дәйекшелердің ішіне жазылады,
Паскаль тілі программалау тілі үшін қолайлы болғандықтан оны
Бұл тіл программалау тілін енді жаңадан бастап үйреніп
Негізгі бөлім
1. Іздеу әдістері – сызықты және бинарлы.
1.1 Іздеу алгоритмдері.
Іздеу алгоритмдері, мысалы, массивтен бізге керек қасиеттері бар
Іздеуге арналған қарапайым тапсырма.
Есептегіш машиналарды тиімді пайдаланудың айбынды болар-болмас демонстрациясы, ішіне
Мысал ретінде, бізге « n » фамилиядан тұратын
Біз солай қойылған тапсырмалардың барлығын шешетін, аяқталған Паскаль
Бұл жерде өте қажет бір ескерту жасау өте
1.2 Linearsearch подпрограммасы.
Біздің бірінші іздеу әдісіміз подпрограмма түрінде іске асырылады
1) strings – стрингтер қатары;
2) newstring – іздеудің объектісі болып табылатын
3) size – қарастыруға жарамды, қатардың элементтерінің
Солайша, подпрограмманың нәтижесінің орындалуы strings ішінде newstring позициясымен
type strtype = string[20];
arraystrtype = array[1..100] of strtype;
Енді біз подпрограмманың басын жаза аламыз:
function linearsearch (strings: arraystrtype;
newstring: strtype;
size: integer): integer;
{-----------------------------------------------------------------------------------------}
{ Сызықты іздеу әдісін қолдана отырып,
{ size элементтерінен newstring стрингісінің позициясын
{ керек, егер newstring табылмаса 0-ді
{-----------------------------------------------------------------------------------------}
Іздеудің принципі келесі жағдайдан тұрады. Strings қатарының әр
Strings қатарындағы әрбір стринг бірегей (өте сирек)
var position: integer;
found: Boolean;
begin
position := 1;
found := false;
while (not found) and (position 0 then writeln(newname,’позициясында
else writeln(newname,’табылмады’);
Бізге мәлім фамилиялардың тізімін өңдеу барысынды location (позиция)
2. Сызықты іздеу.
Сызықты іздеу екі шарты бар циклдің көмегімен (while
Циклден шыққаннан кейін шарттың қайсысынан шыққанымызды тексеру керек.
Мысалы: Сызықты іздеу.
Program Poisk1;
Var A: array [1..100] of integer;
N, X, i: integer;
begin
read (N); {N< = 100}
for i: = 1 to
read (X);
i: = 1; {i: = 0;}
while (i 0 do
begin
s: = s+a mod 10;
end;
Sum: = s;
end;
begin
read (N); {N= Sum (A[c]) then
{left-ті өзгерте отырып оң жағын ортамен бірге таңдаймыз
else right: = c-1;
{right-ті өзгерте отырып ортасыз сол жағын таңдаймыз}
end;
if X = Sum (A[left]) then
write (‘сандар сомасы бар соңғы сан=’,X,’тең’,A[left],’A массивінде орналасқан’,left,’орында’)
else write (‘таппадық’);
end.
3.1 Екіге бөлу арқылы (Бинарлы) іздеу.
Массив элементтерін реттеп орналастыру үшін қосарлы іздеу түсініледі.
Қосарлы іздеу принципі:
Массивті екіге бөлу және салыстыру үшін орта элемент
1
1 4 7 11 14 19 20
L = 1
i:=(L+R) div 2 = 8
Vector[i] > x
1
1 4 7 11 14 18 20
L = 1
i: =(L+R) div 2 = 4
vector [i] < x
L: = i+1 = 5
14 18 20
5
L = 5
i: = (L+R) div 2 = 6
vector [i] > x
R: = i-1 = 5
5
14
L = R = 5
i:= (L+R) div 2 = 5
vector [i] = x
3.2 Бинарлы іздеу әдісі.
Сызықты іздеудің алгоритмі, тездетілген шығудың механизмін жаңа ғана
Үлкен қалалардың тұрғындары өздерінің телефон кітапшасымен қолдана алатындары
Бізде strings атты сортталған стрингтердің қатары
Іздеудің объектісі ретінде Қабылов атты фамилия алынған. Оны
Егер элемент көрсетілген позицияда newstring-пен сәйкес келсе,
Strings
low 1
2
3
4
5
6
high 7
low = 1
high = 7
test = 4
strings[4] = ‘Мұратов’
(а)
strings
1
2
3
low 4
5
high 6
7
low = 5
high = 5
test = 5
strings[5] = ‘Қабылов’
(в)
1-сурет. Бинарлы іздеу алгоритмінің жұмысы (Қабылов фамилиясын
Егер де ол newstring-тен де үлкен болса, онда
Сонымен, кез келген жағдайда алдағы өңдеудің бірінші қадамынан
Өзіміздің мысалымызға қайта оралайық және келесі қадамды қарастырайық
Әрине, strings қатарындағы элементтердің ішінде newstring
Осыған сәйкес мысал 2-суретте көрсетілген. Ендігі жолы іздеудің
Strings
low 1
2
3
4
5
6
high 7
low = 1
high = 7
test = 4
strings[4] = ‘Мұратов’
(а)
low
1
high 2
3
4
5
6
7
low = 1
high =1
test = 1
strings[1] = ‘Қошқаров’
(в)
2-сурет. Алмасов фамилиясын бинарлы іздеу әдісімен іздеу.
Келтірілген жағдайдың қайшылығы іздеудің диапазонының бітуі жайлы айтылады.
3.3 Бинарлы іздеу алгоритмі.
Бізге таныс белгілерді қолдана отырып, біз бинарлы іздеу
Low мен high-дың аралығының дәл ортасында
3.4 Бинарлы іздеу алгоритмін программа түрінде іске
Бинарлы іздеу әдісін іске асыратын біздің подпрограммамыз Паскаль
Function binarysearch (strings: arraystrtype;
newstring: strtype;
size: integer): integer;
{-----------------------------------------------------------------------------------------}
{
{ Бинарлы
{ тарының
{ позициясын
{ Егер
{
{-----------------------------------------------------------------------------------------}
Іздеудің ағымдық шекаралары – low және high
var low, high, test: integer; found:
begin
{бастапқы мәндердің тапсырмалары}
low: = 1;
high: = size;
found: = false;
{іздеу циклі}
while (not found) and (low< = high) do
begin
test: = (low+high) div 2;
if strings[test] = newstring
{newstring test позициясында табылды}
then found: = true;
{іздеу диапазонының тарылуы}
if strings[test] > newstring then
end; {While}
{циклдің аяқталуының себебін анықтайық}
if found then binarysearch: =
end; {binarysearch}
Подпрограмманы қадаммен тексеруді біз оқырманға өзіндік жұмыс ретінде
3.5 Бинарлы іздеудің алгоритмін талдау.
Бинарлы іздеудің алгоритмінің тиімділігін сипаттайтын кейбір сапалы бағалауларды
Жайлылық үшін қатардың элементтерінің санын n
Бірақ, неге әр жағдайда да үш рет тексеру
Барлық айтылған нәрселер математикалық формада қысқаша былай айтылады:
Қатар үшін 7 элементті тексерулер саны: 3 =
Қатар үшін n элементті тексерулер саны:
Log28 – бұл 8-ді алу үшін 2-ге арттырылатын
n
Сызықты іздеу – табуға арналған қажетті салыстырулардың орта
Бинарлы іздеу – табуға арналған қажетті салыстырулардың максимум
Элементтің бар болуы.
Элементтің жоқ болуы.
Элементтің бар болуы.
Элементтің жоқ болуы.
7
100
1000
1000000
4
50
500
500 500
7
100
1000
1000 000
3
7
10
20
3
7
10
20
Егер n+1 саны екінің дәрежесі болса, онда
Бинарлы іздеудің алгоритмі n-нің өте үлкен мәндерінде өзін
Іздеу әдістерінің 2 түрінің салыстырмалы сипаттамалары.
4. Барьермен іздеу.
Барьермен іздеу әдісі циклдегі массив шекараларымен тығыз байланысқан
Іздеу шартында ғана қалған циклден шығу не табылған
Барьерді орнатудың екі әдісі бар:
массивтің қосымша элементтеріне орнату әдісі;
соңғы элементтің орнына орнату әдісі;
Мысалы: Барьермен іздеу.
Program Poisk2a;
Var A: array[1..100] of integer;
N, X, i: integer;
begin
read (N); {N
Графиктерді іздеу алгоритмдеріне және жолдарды іздеу алгоритмдеріне бөлу
Информатика пәнінен лекциялық сабақтардың тезистері
Массивтерді сұрыптаудың қарапайым алгоритмдері
Сұрыптау алгоритмдері
АЛГОРИТМДЕР ТЕОРИЯСЫН ИНТЕЛЛЕКТУАЛДЫ ЖҮЙЕЛЕРДЕ ҚОЛДАНЫЛУЫНА ҚАТЫСТЫ ТЕРМИНДЕРГЕ ШОЛУ
„Трэк” ойыны
Хоной башнясы
Програмистің библотекасын ұйымдастыру технологиясы
Сұрыптау есептері, сұрыптау алгоритмдері туралы ақпарат
Интерпол картотекасы