Сызықты және бинарлы іздеу әдістері курстық жұмыс
Жоспар.
Кіріспе.............................................................................................................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
Жұмыс түрі: Курстық жұмыс
Жұмыс көлемі: 25 бет
Пәні: Соңғы қосылған курстық жұмыстар
-----------------------------------------------------------------------------------
КУРСТЫҚ ЖҰМЫСТЫҢ ҚЫСҚАРТЫЛҒАН МӘТІНІ
Жоспар.
Кіріспе.............................................................................................................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 begin
if strings [position] = newstring
linearsearch := position;
found := true end; {if…then}
position := position+1
end; {While циклініңкі}
if not found then linearsearch := 0
end; {linearsearch}
While циклі келесі екі жағдайдың бірі орындалғанынша
- не not found көрінісі жалған болады (яғни,
- не position мәні size-ден асып кетеді, бұл
Егер іздеу ойдағыдай аяқталса, онда сол жағында linearsearch
1.3 Linearsearch функциясының қолданылуы.
Бізге linearsearch функциясын басты программада қолдануды
“n” фамилиядан тұратын тізімде іздеуді жүзеге асыру
type strtype = string[20];
arraystrtype = array[1..100] of strtype;
var names: arraystrtype;
newname: strtype;
n, location: integer;
……………………..
location := linearsearch (names, newname, n);
if location > 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); {Nfor i: = 1 to
read (X);
i: = 1; {i: = 0;}
while (i{repeat i: = i+1; until
if iend.
----------------------------------------------------------------------------------------------------
Енуден кейінгі соңғы енуді іздеу барысында:
i: = N; {i: = N+1;}
while (i >= 1) and
{repeat i: = i-1; until (iif i >= 1 then
деген операторлар жүру керек.
----------------------------------------------------------------------------------------------------
2.1 Сызықты іздеудің алгоритмін талдау.
Сызықты іздеудің алгоритмі бірқатар тиімді сияқты болып көрінеді.
Бұл тиімсіздіктің себебі неде? Бәрі мәлім болу
Өнімділіктегі осы көрсеткішті арттыруға болады ма екен?
3. Бинарлы (қосарлы) іздеу.
Қосарлы іздеудің алгоритмін тек массивтердегі берілген қасиеті бар
Алгоритмнің негізгі идеясы массивтің әрқашан екіге бөлінуінде және
Бұл бірінші және соңғы енуді іздеу алгоритмінің екі
Қосарлы іздеу алгоритмінің жұмысы барысында осы іздеу жалғасатын
Мысалы1: Өсу боцынша реттелген массивте X санының
Program Poisk3a;
Var A: array [1..100] of
N, X, left, right: integer;
begin
read (N); {Nwrite (‘өсу бойынша реттелген массивті енгіз’);
for i: = 1 to
read (X);
left: = 1; right: = N;
{іздеу үшін үзіндінің оң және сол шекаралары}
while left begin
c: = (left+right) div 2;
{кіші бөлігіне қарай дөңгелектелген орта}
if X > A[c] then
{егер массив кему реті бойынша реттелген боса, онда
left: = c+1
{left-ті өзгерте отырып ортасыз оң жағын таңдаймыз}
else right: = c;
{right-ті өзгерте отырып сол жағын ортамен бірге таңдаймыз}
end;
if X = A[left] then
write (X,’санының бірінші енуі’,’A массивіне’,left,’орынға’)
else write (‘таппадық’);
end.
Мысал2: Массивте, сол массив элементтерінің сандарының сомасының өсу
program Poisk3b;
var A: array [1..100] of
N, X, left, right: integer;
{функция a локальдық айнымалының санының сомасын есептейді}
function Sum (a: integer): integer;
var s: integer;
begin
s: = 0; a: = abs (a);
while a > 0 do
begin
s: = s+a mod 10;
end;
Sum: = s;
end;
begin
read (N); {Nwrite (‘сандар сомасы өсу ретімен реттелген массивті енгізіңіз’);
{мысалы, N = 4 үшін : 122, -432,
for i: = 1 to
read (X);
left: = 1; right: = N;
{іздеу үшін үзіндінің оң және сол жақ шекаралары}
while left begin
c: = (left+right+1) div 2;
{үлкен жағына қарай дөңгелектелген орта}
if X >= 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] 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 (lowbegin
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); {Nfor i: = 1 to
read (X);
A[N+1]: = X; {барьерді қосымша элементтерге орнату}
i: = 1; {i: = 0;}
while A[i] X do
{repeat i: = i+1; until A[i]
if i end.
Program Poisk2b;
Var A: array [1..100] of
N, X, i, y: integer;
begin
read (N); {Nfor i: = 1 to
read (X);
y: = A[N]; {соңғы элементтің сақталуы}
A[N]: = X; {барьерді массивтің соңғы орнына
i: =1; {i: = 0;}
while A[i] X do
{repeat i: = i+1; until
if (i write (X,’санының бірінші енуі’, ‘A массивіне’,i,’орынға’)
else write (‘таппадық’);
A[N]: = y; {массивтің соңғы элементін қайта
end.
Қорытынды.
Менің бұл курстық жұмысымның тақырыбы “Паскаль тілінде берілгендерді
Паскаль тілінде берілгендерді іздеу Бейсикке қарағанда жеңілдеу. Бұл
Бұл жұмысты орта оқу орындарында қолдануға болады. Сонымен
Іздеудің мақсаты – берілгендерді ең тиімді және қолайлы
Мұнда тест сұрақтарын енгізетін болсақ, онда бұл жұмысты
Әдебиеттер тізімі:
Ж.Джоунс, К. Харроу, Решение задач в системе
Программирование в Turbo Pascal 7.0 и
BHV. Турбо Паскаль 7.0, Киев, 1996
О. Камардинов. Паскаль тілінде программалау, А.,
А.С. Барсов. Линейное программирование в технико-экономических задачах,
3
Қошқаров
Ізетов
Есенов
Мұратов
Қабылов
Асылов
Мәмбетов
Қошқаров
Ізетов
Есенов
Мұратов
Қабылов
Асылов
Мәмбетов
Қошқаров
Ізетов
Есенов
Мұратов
Қабылов
Асылов
Мәмбетов
Қошқаров
Ізетов
Есенов
Мұратов
Қабылов
Асылов
Мәмбетов
Қошқаров
Ізетов
Есенов
Мұратов
Қабылов
Асылов
Мәмбетов
Қошқаров
Ізетов
Есенов
Мұратов
Қабылов
Асылов
Мәмбетов
