Сызықты іздеудің алгоритмін талдау

Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 22 бет
Таңдаулыға:

Жоспар.

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... .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
Қорытынды ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ..2 4
Әдебиеттер
тізімі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ...25

Кіріспе

Жоғары деңгейлі программалау тілдерінің бірі – бұл Паскаль тілі. Оның
алғашқы нұсқасын 70-ші жылдары Швейцария университетінің ғұлама ғалымы
Н.Вирт жарыққа шығарған болатын. Қазіргі кезде осы Паскаль тілінің
кеңейтілген ондаған түрлері (диалектісі) бар, оның ішінде IBM PC-ге
үйлесімді дербес компьютерлер жұмыс істей алатын Турбо Паскаль түрінің
(диалектісінің) нұсқалары да жеткілікті. Бұл нұсқа Турбо Паскальдың алғашқы
нұсқаларымен де үйлесімді. Паскаль тілін де, Бейсик тілі сияқты, оқып-
үйрену жнңіл. Түрлі салалық информациямен жұмыс істеуде нәтижелі
болғандықтан, бұл тіл дүние жүзіне көп тараған тілдердің бірі болып
табылады. Оның ыңғайлылығы мынада:
- тіл алгоритм құрылымын сақтап құрылған. Мұнда программаны
бірте-бірте дамыту арқылы жеке блоктар түрінде (модульді)
құруға болады. Ол программалаудың тәсілдерін үйрену үшін де
өте колайлы;
- тілге дамытылған берілгендер типтері енгізілген. Олар
өңделетін берілгендер элементтерін толық сәйкестендіріп
сипаттауға және жаңа берілгендер типтерін енгізуге мүмкіндік
береді;
- мұнда кішігірім жеңіл программалармен бірге күрделі құрылымды
программаларды құру да мүмкін;
- тіл синтаксисі қиын емес, тура Бейсиктегідей; операторлардың
саны мүмкіндігінше азайтылған, т.б.
Паскаль тілінде құрылған программаны мәшинелік кіріспе тілге аудару
үшін компилятор пайдаланылады.
Турбо Паскальда программалау тәсілдері өте көп және жиі кездесетін
қызметші сөздер мен стандартты атаулар арқылы информацияны өңдеу
программаларын құру мүмкіншілігі де бар. Паскаль тілінің алфавиті негізінен
Бейсик тілінің алфавитімен бірдей. Оның тек Бейсиктен кейбір
айырмашылықтары:
- меншіктеу белгісі “ := “ түрінде жазылады;
- санды дәрежелеу белгісі жоқ. Оның орнына санды өзіне-өзін
көбейту арқылы беріледі;
- мәтіндер, символдар тырнақшаның ішіне емес дәйекшелердің ішіне
жазылады, т.б.
Паскаль тілі программалау тілі үшін қолайлы болғандықтан оны
дүние жүзінің көпетеген программалаушылары да қолданысқа енгізіп келеді.
Бұл тіл программалау тілін енді жаңадан бастап үйреніп келе
жатқан бастаушыларға оны тез меңгеріп алу үшін де өте қолайлы. Бұл тілмен
көптеген мүмкіншіліктерді жүзеге асыруға болады.

Негізгі бөлім

1. Іздеу әдістері – сызықты және бинарлы.

1.1 Іздеу алгоритмдері.

Іздеу алгоритмдері, мысалы, массивтен бізге керек қасиеттері бар
элементті табу үшін қолданылады. Әншейінде, бірінші және соңғы элемент ену
үшін іздеу тапсырмаларын орнату ажыратылады.

Іздеуге арналған қарапайым тапсырма.

Есептегіш машиналарды тиімді пайдаланудың айбынды болар-болмас
демонстрациясы, ішіне кейбір тізімдерде информайияны іздеу жүзеге
асырылатын, тапсырмалар болып табылады. Дәл осындай жұмыспен біз қазір осы
бөлімде айналысамыз, бірақ, алдымен келесі қарапайым тапсырманы қарастырып
шығамыз.
Мысал ретінде, бізге n фамилиядан тұратын тізім бар болсын деп
шамалайық және бізге тағы да жаңа фамилиялар сериясынан тұратын тағы да бір
тізім ұсынылсын. Бізге осыдан, бастапқы тізімде қайта келіп түскен әр
фамилия құрамында бар ма екенін анықтау қажет. Егер ондай болса, онда оның
бастапқы тізімдегі позициясын баспаға шығару керек. Егер жаңа фамилия
тізмде жоқ болса, онда ондай фамилия жоқ деген хабарлама баспаға
шығуы қажет. Мейлі онда, мысалы, бастапқы тізімде: Оспанов, Құрбанов,
Тоқтаров және Сапаров – деген төрт фамилия берілсін. Ал, жаңасында: Аманов
және Асанов – деген екі фамилия берілсін. Тоқтаров деген фамилия бастапқы
тізімде, үшінші позицияны ала отырып, орналасқан (бар); ал, Асанов ол жерде
жоқ.
Біз солай қойылған тапсырмалардың барлығын шешетін, аяқталған Паскаль
программасын қолданбаймыз. Өйткені, біз тек тізімдегі берілген стрингті
іздеуді жүзеге асыратын және оның орналасу орнын анықтайтын (егер бізге
керек стринг табылған (анықталған) болса), бір ғана подпрограмманы жазумен
шектелеміз.
Бұл жерде өте қажет бір ескерту жасау өте орынды болатын шығар. Біз
қалайда әрі қарай көретініміздей, керек стрингтің тізімінді іздеу (немесе
сандар, өйткені дәл сондай мүмкіндікпен сандық информацияны да іздеуді
жүзеге асыруға болады) тездетілген түрде өтіп жатыр, егер тізім алдын ала
(шамалап) сортталған болса. Алайда, іздеуді (операцияны) бастаудың алдын
тізімді әрқашан да сорттап тұру деген түсінік тумау керек. Егер біз бір-екі
элементті ғана іздеуді ойласақ, онда сорттаумен айналысу тіптен мақсатқа
сәйкес келмейді. Ал, егер мәселе жүздеген, мыңдаған, тіптім миллиондаған
объектілер жайында болса (мысалыға, толефон кітапшасындағы фамилияларды
қарап шығу неге әкеліп соғады), онда тізімді алдын ала жөндеу шығыны
ақталынған болып шығады. Жалпы, біздің іздеу туралы әңгімемізді біз
сортталған тізімді тіптем қажет етпейтін әдістен бастаймыз.

1.2 Linearsearch подпрограммасы.

Біздің бірінші іздеу әдісіміз подпрограмма түрінде іске асырылады және
біз оны “linearsearch”(сызықты іздеу – бұл сөздің мағынасы жайлы кейінірек
қарастырамыз) деп атаймыз. Бұл подпрограмма үш параметрді алып отырады:
1) strings – стрингтер қатары;
2) newstring – іздеудің объектісі болып табылатын стринг;
3) size – қарастыруға жарамды, қатардың элементтерінің саны;
Солайша, подпрограмманың нәтижесінің орындалуы strings ішінде
newstring позициясымен бір ғана бүтін санды мәнмен көрсетілуі (айтылуы)
қажет. Өйткені, біз linearsearch-ті функция түрінде жазылуын қалаймыз. Егер
linearsearch функцияларын төрт фамилиядан тұратын бізге мәлім тізімді
беретін болсақ және Тоқтаров деген фамилияны іздеуді талап етсек, онда ол
3 деген мәнді қайтарып береді. Ал, Асанов жайлы сауалға қандай жауап
беріледі? Әрине, біз мұндай фамилия тізімде жоқ деген сигнал алуымыз
қажет. Бұл қандай сигнал? Сірә, бұл бағыт үшін 0 деген санды алған жөн
болар (бірақ, не үшін сигнал, айталық, бульдік мәнмен емес, міндетті түрде
санмен алынуы тиіс?). Біз алда linearsearch формальді параметрлердің
баяндамаларында қолданылатын, негізгі программада екі құрылым анықталған
деп есептейік:

type strtype = string[20];

arraystrtype = array[1..100] of strtype;

Енді біз подпрограмманың басын жаза аламыз:

function linearsearch (strings: arraystrtype;

newstring: strtype;

size: integer): integer;

{---------------------------------- ----------------------------------- -
-------------------}
{ Сызықты іздеу әдісін қолдана отырып, strings; қатарының бірінші }
{ size элементтерінен newstring стрингісінің позициясын қайтару
}
{ керек, егер newstring табылмаса 0-ді қайтару керек.
}
{---------------------------------- ----------------------------------- -
-------------------}

Іздеудің принципі келесі жағдайдан тұрады. Strings қатарының әр стринг-
элементі newstring параметрімен жүйелі түрде салыстырылады. Сәйкес мән
болған жағдайда табылған стрингтің позициясы (индексі) қайтарылады. Егер де
newstring барлық элементтермен салыстырылғаннан кейін керек стринг
табылмаған болса, онда сәтсіз ізделгені туралы куәландырылатын 0 саны
қайтарылады. Көрсетілген процесте барлық элементтер бірінен соң бірі
тексерілетіні туралы түртіп немесе белгілеп қояйық. Сол себептен де бұл
іздеу әдістерін “сызықты” немесе “жүйелі” деп атайды.
Strings қатарындағы әрбір стринг бірегей (өте сирек) деп есептейік,
яғни, бір ғана дана түрінде қатысады (алайда, бұл олай болмаса, онда ең
бірінші пайда болғанды тіркеп отырамыз). Осыдан кейін, яғни, мәндердің
сәйкестігі дәл келген жағдай табылғаннан кейін, одан ары іздеу керек болмай
қалады. Көруді алдын ала тоқтату кезеңін белгілеп отыру үшін found
(табылды) деген бульдік айнымалыны енгіземіз. Подпрограмма денесінің үлкен
бөлігін қатардың барлық элементтерін newstring стрингімен салыстыратын
while циклін құрайды. (Біз іздеудің түбіне жеткеннен кейін бірден циклден
шығып кету үшін for циклін әдейі қолданбай отырмыз)

var position: integer;

found: Boolean;

begin

position := 1;

found := false;

while (not found) and (position = size) do

begin

if strings [position] = newstring then begin

linearsearch := position;

found := true end; {if...then}

position := position+1

end; {While циклініңкі}

if not found then linearsearch := 0

end; {linearsearch}

While циклі келесі екі жағдайдың бірі орындалғанынша жұмыс
істейтініне назар аударыңыз:
- не not found көрінісі жалған болады (яғни, found true-мен тең
болады) – бұл ізделінді срингтің табылғанын білдіреді;
- не position мәні size-ден асып кетеді, бұл іздеудің барлық
диапазонының таусылғанын білдіреді;
Егер іздеу ойдағыдай аяқталса, онда сол жағында linearsearch
функциясының аты тұратын, ал, оң жағында құрамында newstring мәні бар
қатардың ағымдық позициясы тұратын тағайындалған ұсыныс орындалады. While
циклінен шығарда found белгісі тексеріледі: егер керек стринг табылмаған
болса, онда linearsearch, сондай-ақ, іздеудің сәтсіз аяталғандығы туралы
сигнал бере отырып 0 мәнін алады.

1.3 Linearsearch функциясының қолданылуы.

Бізге linearsearch функциясын басты программада қолдануды қалай
ұйымдастыруға болады?
“n” фамилиядан тұратын тізімде іздеуді жүзеге асыру керек делік және
бұл бағыт үшін басты прораммада names болжанған (айтылған). Сонымен қатар,
жаңа стрингті – ізделінді нәрсені сақтауға арналған newname айнымалысы
алынған делік. Онда linearsearch-қа назар аударатындайы бар программаның
үзіндісі, келесі түрге ие болады:

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,’позициясында табылды’,
location)

else writeln(newname,’табылмады’);

Бізге мәлім фамилиялардың тізімін өңдеу барысынды location (позиция)
айнымалысы Тоқтаров деген фамилияны іздеп боған соң 3 деген мәнді алады;
ал, Асанов деген фамилияны табу үшін әрекет жасаған соң бұл айнымалы 0
деген мәнді алады.

2. Сызықты іздеу.

Сызықты іздеу екі шарты бар циклдің көмегімен (while немесе repeat-
until) жүзеге асырылады. Бірінші шарт индекстің массивке қатыстығын
тексереді, мысалы, (i=N). Екінші шарт – ол іздеудің шарты. Біздің жағдайда
бұл шарт while циклінде іздеудің жалғасы: (A[i] X), ал, repeat-until
циклінде бұл шарт іздеудің соңы: (A[i] = X). Әншейінде, цикл денесінде бір
ғана оператор жазылады: массивте индекстің өзгеруі.

Циклден шыққаннан кейін шарттың қайсысынан шыққанымызды тексеру керек.
If операторында, әншейінде, циклдің бірінші шартын тексереді. Осы шарттың
орындалуы кезінде while циклімен іздеу ойдағыдай болғаны туралы айтуға
болады, ал, repeat-until циклімен оның бұзылуы жайлы айтуға болады.

Мысалы: Сызықты іздеу.

Program Poisk1;

Var A: array [1..100] of integer;

N, X, i: integer;
begin

read (N); {N = 100}

for i: = 1 to N do read (A[i]);

read (X);

i: = 1; {i: = 0;}

while (i= N) and (A[i] X) do i: = i+1;
{repeat i: = i+1; until (iN) or (A[i] = X);}

if i= N then write (X,’санының бірінші болып енуі’,’A массивіне’,
i,’орынға’) else write (‘таппадық’)ж

end.

----------------------------------- ----------------------------------- ------
------------------------

Енуден кейінгі соңғы енуді іздеу барысында:

i: = N; {i: = N+1;}

while (i = 1) and (A[i] X) do i: = i-1;

{repeat i: = i-1; until (i1) or (A[i] = X);}

if i = 1 then write (X,’санының бірінші енуі’,’A
массивіне’,i,’орынға’) else write (‘таппадық’);

деген операторлар жүру керек.

----------------------------------- ----------------------------------- ------
------------------------

2.1 Сызықты іздеудің алгоритмін талдау.

Сызықты іздеудің алгоритмі бірқатар тиімді сияқты болып көрінеді.
Өйткені, берілген тізімдегі әрбір элемент онымен іздеу барысында анықталған
мән бір ақ рет қана тексерілмейді емес пе. Егер бізде бастапқы тізім жайлы
ешқандай қосымша информация болмаса, онда бұл іздеу әдісі басқалары сияқты
өте жақсы болуы мүмкін. Бірақ, кейде элементтердің дұрыс ретпен реттелгені
туралы мәлімет алдын ала белгілі болады, яғни, оның алдында ақ алдын ала
сортталып қойылған. Міне, осындай кездердің бірінде, бірқатар басқа
әдістермен салыстырғанда, сызықты іздеудің тиімсіздігі көрініс береді.
Бұл тиімсіздіктің себебі неде? Бәрі мәлім болу үшін біз сызықты іздеу
алгоритмінің жұмысын талдауымыз қажет. Анықтау үшін бізге 100 элементтен
тұратын орын берілген, мысалы, адам есімдері, деп ойлайық. Егер біздің
ізделінді есіміміз осы қатарда орналасқан болса, онда оны анықтау үшін орта
есеппен 50 рет салыстыру қажет болады (неге?). Егер де ізделінді есім
қатарда жоқ болса, онда бұл фактті орналастыру үшін бізге барлық 100
элементті қарап шығу керек. 1000 элементтен тұратын қатардан керек (немесе
бар) есімді анықтау үшін сәйкес қатарды 500 (орта есеппен) рет салыстыру
қажет. Ал, оның жоқ екендігіне көз жеткізу үшін 1000 рет салыстыру жүргізу
керек. Сонымен, жалпы жағдайда n элементтің ішінен сызықты іздеген кезде
(нәтижелі іздеу кезінде) орта есеппен n2 рет және нәтижесіз (жаман)
іздеу кезінде n рет салыстыру қажет болады. Бұл жағдайдың ең мәндісі
болып оның бастапқы тізімдегі элементтердің орналасу ретінен тәуелсіз болуы
(неге?).
Өнімділіктегі осы көрсеткішті арттыруға болады ма екен? Алдын
қарастырғанда да іздеуден бұрын тізімді алдын ала сорттаған ешқандай да
басымдылықты (тиімділікті арттыру кезінде) берегн жоқ. Бірақ, егер бастапқы
тізім, білгендей-ақ, сортталғандығы жайлы мәлім болса, онда бұл – маңызды
қосымша информация және оны іздеуді тездету үшін қолданбаған да орынды
болмас еді. Осылайша, алдын ала реттелген тізімде қажет элементтің
“жоқтығы” тез анықталады: қалай тексерілетін мән ізделіндіден үлкен немесе
көп екендігі туралы мәлім болса, солай біздің іздеу циклінен ойланбастан
шығуымызға болады және қатардың қалған элементтерін тексерумен айналыспай-
ақ іздеудің сәтсіздігі туралы сигналды қайтаруымызға болады.

3. Бинарлы (қосарлы) іздеу.

Қосарлы іздеудің алгоритмін тек массивтердегі берілген қасиеті бар
және осы қасиетке байланысты реттелген элементті іздеу үшін қолдануға
болады. Осылайша, берілген мәні бар санды іздеу барысында элементтердің
мәндері кему немесе өсу ретімен реттелген массив болу керек. Ал, мысалы,
сандардың берілген сомасы бар санды іздеу кезінде массив элементтері
сандарының сомасы бойынша өсу немесе кему ретімен реттелуі керек.

Алгоритмнің негізгі идеясы массивтің әрқашан екіге бөлінуінде және
қажет элемент орналасуы мүмкін бөлігінің алынуында жатыр. Бөлу іздеуге
арналған массив бөлігі бір элементтен көп (немесе жоғары) болғанынша
жалғасады. Содан соң осы қалған элементті іздеу шартының орындалуын тексеру
керек.

Бұл бірінші және соңғы енуді іздеу алгоритмінің екі модификациясы бар.
Барлығы орта элемент қалай алынатындығына байланысты: кіші немесе жоғарғы
жағына қарай дөңгелектеумен. Бірінші жағдайда орта элемент массивтің сол
жағына қатысты болады, ал, екінші жағдайда оң жағына қатысты болады.

Қосарлы іздеу алгоритмінің жұмысы барысында осы іздеу жалғасатын
үзіндінің (фрагменттің) көлемі, әр іздеу кезінде шамамен екіге кемиді. Бұл
N лагорифмінің 2негідігі бойынша реттік алгоритмінің есептеу қиындығын
қамтамасыз етеді. Мұндағы, N – массив элементтерінің саны.

Мысалы1: Өсу боцынша реттелген массивте X санының бірінші енуін
іздеу.

Program Poisk3a;

Var A: array [1..100] of integer;

N, X, left, right: integer;

begin

read (N); {N= 100}

write (‘өсу бойынша реттелген массивті енгіз’);

for i: = 1 to N do read (A[i]);

read (X);

left: = 1; right: = N;

{іздеу үшін үзіндінің оң және сол шекаралары}

while left right do

begin

c: = (left+right) div 2;

{кіші бөлігіне қарай дөңгелектелген орта}

if X A[c] then

{егер массив кему реті бойынша реттелген боса, онда if X A[c]}

left: = c+1

{left-ті өзгерте отырып ортасыз оң жағын таңдаймыз}

else right: = c;

{right-ті өзгерте отырып сол жағын ортамен бірге таңдаймыз}

end;

if X = A[left] then {бұл жерде left = right, бірақ әрқашан с-ға
(=c) тең бола бермейді}

write (X,’санының бірінші енуі’,’A массивіне’,left,’орынға’)

else write (‘таппадық’);

end.

Мысал2: Массивте, сол массив элементтерінің сандарының сомасының өсу
реті бойынша реттелген, соңғы санның Х-ке тең санның сомасын іздеу.

program Poisk3b;

var A: array [1..100] of integer;

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); {N= 100}

write (‘сандар сомасы өсу ретімен реттелген массивті енгізіңіз’);

{мысалы, N = 4 үшін : 122, -432, 88, 593}

for i: = 1 to N do read (A[i]);

read (X);

left: = 1; right: = N;

{іздеу үшін үзіндінің оң және сол жақ шекаралары}

while left right do

begin

c: = (left+right+1) div 2;

{үлкен жағына қарай дөңгелектелген орта}

if X = Sum (A[c]) then left: = c

{left-ті өзгерте отырып оң жағын ортамен бірге таңдаймыз }

else right: = c-1;

{right-ті өзгерте отырып ортасыз сол жағын таңдаймыз}

end;

if X = Sum (A[left]) then {мұнда left = right, бірақ с-ға (=c)
әрқашан тең емес}

write (‘сандар сомасы бар соңғы сан=’,X,’тең’,A[left],’A массивінде
орналасқан’,left,’орында’)

else write (‘таппадық’);

end.

3.1 Екіге бөлу арқылы (Бинарлы) іздеу.

Массив элементтерін реттеп орналастыру үшін қосарлы іздеу түсініледі.
Массивке қатысты мысал қарастырайық (vector [i] = vector [i+1]).
Қосарлы іздеу принципі:
Массивті екіге бөлу және салыстыру үшін орта элемент таңдап аламыз.
Егер ол сәйкес болмаса, онда іздеу тоқтатылады. Егер орташа элемент сәйкес
келмесе және аз болса, онда барлық сол жақ элементтері сол сияқты аз
болады. Негізінен оларды алыс іздеу зонасынан қарастыруға болады, яғни,
массивтің оң бөлігін қалдыра отырып. Қосарлы іздеудің алгоритмін
қарастырайық:
1 ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.