Сұрыптау және іздеу тәсілдері

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
1.Сұрыптау тәсілдері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
1.1 Хоар тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
1.2 Пузырек тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
2.Іздеу тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
2.1 Бинарлық іздеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
3.Теориялық мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
3.1 Паскаль тіліндегі файл типінің баяндалуы ... ... ... ... ... ... ... ..
4. Есептің алгоритімі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
5. Программаның Паскаль тілінде баяндалуы ... ... ... ... ... ... ... ... ... ...
6. Жалпы мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
7. Функционалдық қолдану ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
8. Логикалық құрылымның баяндалуы ... ... ... ... ... ... ... ... ... ... ... ... ...
9. Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
Пайдаланған әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .

Жаңа реттеулер енгізуден қиын, сәттілігі жағынан күдікті, жүзеге
асыруы жағынан қауіпті жұмыс жоқ .
Никколо Макьявелли (1513)

«Біз барлық автомобильдердің нөмірін қарастырып үлгермейміз»,- деді Дрейк. «Ал бізге оны істеп қажеті жоқ, Пол. Біз тек ғана оларды реті бойынша қойып,олардың бірдейлерін іздейміз».
“The Case of Angry Mourner” (1951)
Бұл айтылған пікірлердің барлығы программалаудың ең бір қажетті мүмкіндіктері сұрыптау мен іздеуге арналған. Сұрыптау мен іздеуді кез-келген программада қолдануға болады.олардың мүмкіндіктері шексіз. Осы мүмкіндіктерді пайдалана отырып, программа алгоритімін қарапайым жолмен жеңілдетуге болады. Негізінен сұрыптау мен іздеудің түрлері өте көп.
Кез-келген күнделікті жағдайда біз сұрыптау және іздеу үрдістерімен жұмыс жасаймыз. Әр адамда неліктен деген сұрақ туады. Жауап өте қарапайым. Себебі бұл үрдістермен жұмыс жасау өте ыңғайлы. Тіпті өзіміздің күнделікті қолданып жүрген персоналды компьютерімізде сол принциппен жұмыс істейді. Олар сіз енгізген мәліметтерді сұрыптап қояды да сіз оларды іздегенде лезде тауып бере қояды. Сұрыптау мен іздеу тәсілдерін кеңінен қолданады. Бұл тәсілдерді қарапайым студентте кәсіпқой программистте қолдана алады. Жалпы алғанда кез-келген программа сұрыптаудан басталады. Ал тез сұрыптап қажет элементті табу үшін сұрыптау және іздеу тәсілдерін жетік білген жөн. Сондықтан сұрыптау мен іздеу тәсілдерін қарастырып көрейік.

1. «Программалар мен алгоритмдердің анализдері және құрылымдары»
А.Ө. Муртазина, Б.Б. Тусупова Алматы 2001

2. «Программирование на языке Си» В.В. Подбельский , С.С. Фомин
Москва , «Финансы и статистика» 1998

3. «Работаем на языке СИ» В.К. Потоцкий Москва , «Малип» 1992

4. «Основы Turbo Pascal 7.0» В.В. Фаронов Москва 2000

5. «Введение в язык Pascal » В.Г. Абрамов Москва , Наука 1992

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 21 бет
Таңдаулыға:

Мазмұны

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... .
1.Сұрыптау
тәсілдері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ..
1.1 Хоар
тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... .
1.2 Пузырек
тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
... ... ...
2.Іздеу
тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
... ... ... ... ... ... ..
2.1 Бинарлық
іздеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ...
3.Теориялық
мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... .
3.1 Паскаль тіліндегі файл типінің баяндалуы
... ... ... ... ... ... ... ..
4. Есептің
алгоритімі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ... ..
5. Программаның Паскаль тілінде
баяндалуы ... ... ... ... ... ... ... ... ... ...
6. Жалпы
мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... .
7. Функционалдық қолдану
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
8. Логикалық құрылымның
баяндалуы ... ... ... ... ... ... ... ... ... ... ... ... ...
9.
Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
Пайдаланған
әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ...
КІРІСПЕ

Жаңа реттеулер енгізуден қиын, сәттілігі жағынан күдікті,
жүзеге
асыруы жағынан қауіпті жұмыс жоқ .
Никколо
Макьявелли (1513)

Біз барлық автомобильдердің нөмірін қарастырып
үлгермейміз,- деді Дрейк. Ал бізге оны істеп қажеті жоқ, Пол. Біз тек
ғана оларды реті бойынша қойып,олардың бірдейлерін іздейміз.
“The Case
of Angry Mourner” (1951)

Бұл айтылған пікірлердің барлығы программалаудың ең бір
қажетті мүмкіндіктері сұрыптау мен іздеуге арналған. Сұрыптау мен іздеуді
кез-келген программада қолдануға болады.олардың мүмкіндіктері шексіз.
Осы мүмкіндіктерді пайдалана отырып, программа алгоритімін қарапайым
жолмен жеңілдетуге болады. Негізінен сұрыптау мен іздеудің түрлері
өте көп.
Кез-келген күнделікті жағдайда біз сұрыптау және іздеу
үрдістерімен жұмыс жасаймыз. Әр адамда неліктен деген сұрақ туады. Жауап
өте қарапайым. Себебі бұл үрдістермен жұмыс жасау өте ыңғайлы. Тіпті
өзіміздің күнделікті қолданып жүрген персоналды компьютерімізде сол
принциппен жұмыс істейді. Олар сіз енгізген мәліметтерді сұрыптап қояды да
сіз оларды іздегенде лезде тауып бере қояды. Сұрыптау мен іздеу тәсілдерін
кеңінен қолданады. Бұл тәсілдерді қарапайым студентте кәсіпқой
программистте қолдана алады. Жалпы алғанда кез-келген программа сұрыптаудан
басталады. Ал тез сұрыптап қажет элементті табу үшін сұрыптау және іздеу
тәсілдерін жетік білген жөн. Сондықтан сұрыптау мен іздеу тәсілдерін
қарастырып көрейік.

1. Сұрыптау тәсілдері

Практикалық тұрғыдан алғандағы сұрыптаудың қиындықтары:
Төрт түрлі сұрыптау тәсілдерінің жетістіктері мен жетіспеушіліктері.
Сұрыптау тәсілдері программалаудың барлық саласында қолданылады. Ол
математикалық программаларда және де база құруда да қолдарылады.
Сұрыптау алгоритімін практикалық тұрғыдан үш бөлікке бөліп
қарастыруға болады.
− салыстыру, элементтің жұбының ретін анықтайды;
− алмастыру, элемент жұптарының орнын ауыстырады;
− өздігінен сұрыпталатын алгоритм, ол жиынның барлық элементі
реттелгенше салыстыру мен алмастыруды жалғастыра береді;
Төменде қарастырылған сұрыптаудың төрт түрі де сондай қасиеттерге
ие. Бұл сұрыптау тәсілдерін жалпы түрде атап өтейік. Бұл тәсілдерді
басқалардан бөліп алған себебіміз,олар біріншіден-өте жиі қолданылады,
екіншіден- басқа алгоритмдер осы жерде қарастырылатын тәсілдердің
модификациясы болып табылады.

1.1 Хоар тәсілі

Бұл тәсіл лездік сұрыптау деп аталады. Ол 1962 жылы
құрастырылған. Оның қрастырушысы Charles Antony Richard Hoare.
Бұл тәсілдің басты мақсаты жиынның сұрыптауға келетін элементін
табу керек және осы элемент жиынды екі кіші элементке бөледі.

Жалпы алғанда сұрыптаудың түрлері өте көп. Оларды түгел
қарастырып шығу мүмкін емес. Сонда да мен осы курстық жобамда маңызды
деген бірнеше түрлерін қарастырып өтуді жөн көрдім. Яғни, жоғарыда аталып
өткен сұрыптау тәсілдерін толығырақ қарастырып өтейік.
Лездік сұрыптау немесе Хоар тәсілі. Сұрыптау алгоритімінің ең
тамаша бірі болып лездік сұрыптау (quicksort) болып табылады. Оның
құрастырушысы Чарльз Хоар, осы сұрыптау тәсілін 1962 жылы жарыққа
шығарды. Лездік сұрыптау арқылы қажет емес немесе артық есептеулерден
арылуға болады.сұрыптаудың осы түрімен жұмыс істегенде массивті екіге
бөлуге болады. Яғни, үлкен элементтерін бөлек, кіші элементтерін
бөлек. Содан кейін екі топты рекурсивті түрде сұрыптайды. Ал осы
үрдіс аяқталған кезде массив сұрыпталып бітеді. Хоар тәсілінің
алгоритімі өте қарапайым және өте тиімді. Оның бірнеше түрлері бар.
Төменде қарастырылатын түрі қолдануы жағынан өте жеңіл.
Біздің quicksort функциясы бүтін санды массивті сұрыптайды:

* quicksort : сұрыптайды v[ ]..v[n-1]
өсу бойынша * void quicksortClrrt
v[ ], int n)
➢ {
int i, last;
if (n=1) * ешнәрсе жасамау *
return;
swap (v, 0,rand() % n);
last=0;
for (i=1; in; i++) * бөліктегіш *
if (v[i] v[0])
swap (v, ++last, i);
swap ( v, 0, last ); * бөліктегішті сақтау *
quicksort ( v, last ) ; * рекурсивті
түрде сұрыптау*quicksort (v+last+ 1, n-last-1);
* барлық бөлігін * }

swap операциясы quicksort функциясында үш рет кездеседі, сондықтан оны
бөлек функция ретінде жазамыз.
* swap:
v[i] and v[j] * орындарын алмастырамыз *
void swap(int v[ ], int i , int j)
{ int temp;
temp =v[i]; v[i]=v[j]; v[j]=temp;

Массивті екіге бөлгенде біріншіден, оны бөлетін элемент таңдалады.
Ол уақытша массивтің басына қойылады да, массивтің қалған элементтері
қарастырылады. Массивті бөлетін элементтен кіші элементтер (яғни,
кішкентай элементтер ) массив басына қарай жылжытылады (last
позициясына). Ал үлкен элементтер массив соңына қарай жылжытылады (і
позицияға). Үрдістің басында бөлетін элемент орнын ауыстырғанан кейін
last=0 және i=1 ден n-1 ге дейінгі элементтер әлі қарастырылмаған
болады. Басында 1 ден last қа дейінгі элементтер бөлетін элементтер
қатаң түрде кіші, ал last+1 ден i-1 ге дейінгі элементтер оған тең
немесе үлкен. Ал і ден n-1 ге дейінгілер әлі қарастырылмаған. V[i] ='
V[0] шарты бірінші рет орындалғанша, алгоритм [i] элементін өз-өзіне
ауыстыра береді.
Барлық элементтер қарастырылып болған соң бөлетін элемент өзінің
соңғы позициясына жету үшін, о элемент last позиясына қойылады. ЕНді
массив мына түрде болады:
Осы үрдіс массивтің оң жағына да сол жағына да қолданылады.
Үрдіс аяқталғанда массив толық сұрыпталған болады.Бұл лездік
сұрыптау қаншалықты тез жұмыс атқарады десек,оған келесі түрде жауап
беруге болады.Әдетте n элементтен тұратын массив n2 элементтен
тұратындай етіп 2 ге бөлінеді, одан әрі n2 элементтен тұратын 2 топ
әрқайсысы n4 элемент болатындай етіліп 4 топқа бөледі,содан соң әр
біреуінде n8 элемент болатындай етіп 8 топқа бөлінеді, т.с.с.Үрдіс
шамамен log2 n рет қайталанады.

1.2 Пузырёк тәсілі

Бұл тәсілдің басты мақсаты оның атауында. Яғни, массивтің ең “жеңіл”
элементтері көтеріледі, ал ең “ауыр” элементтері төмен түседі.
Алгоритмдік түрде оны келесі жағдайда көрсетуге болады:
Ол үшін массивті астынан үстіне қарай түгел қарастырамыз. Егер қарастыру
барысында “астынғы” элемент “үстінгі” элементке қарағанда кіші болса,
онда оларды ауыстырамыз. Осындай әдіспен массивтің ең ”кіші” элементін
жоғарыға шығарамыз. Содан кейін барлық үрдісті массивтің қалған
сұрыпталмаған N-1 элементтері үшін қайталаймыз (яғни, бірінші
элементтен төменгі элементтер үшін). Бұл сұрыптау тәсілінің алгоритімі
өте қарапайым болғандықтан өте тиімді..
Пузырек тәсілі. Сұрыптаудың пузырек тәсілінің алгоритімінде екі
шектес элемент салыстырылады. Егер олар кері ретпен орналосқан болса,
онда олардың орындары ауыстырылады. Осылай барлық шектес элементтер
салыстырылып шығып , қажет болса алмастырылады. Бұл үрдіс барлық
элементтер реттелгенше жалғаса береді. Сұрыптау алгоритімі келесі
қадамдардан тұрады: олардың мәндерін ауыстыру.
1. Бірінші және екінші элементтерді салыстыру. Қажет жағдайда
элементтердің мәндерін ауыстыру.
2. Екінші және үшінші элементтерді салыстыру. Қажет жағдайда
элементтердің мәндерін ауыстыру.
3. Осы үрдіст басқа да элементтер жұбы үшін қайталанады.
4. 1-3 қадамдарды басқа элементтер реттеліп біткенше қайталау.
Сұрыптау барысында мәні кіші элементтер судағы ауа тәрізді жоғарыға
көтеріледі. Егер тізім N элементтен тұратын болса, толық сұрыпталу үшін
N-1 рет қайталануы қажет . ал өсу ретімен сұрыпталу келесі түрде
болады:

Repeat
Sorted:=true;
For i :=1 to n-1 do begin
If data [i] data[i+1] then begin
Temp:=data[i];
Data[i]:=data[i+1];
Data[i+1]:=temp;
Sorted:= жалған.
End;
End;
Until sorted;

2 Іздеу

Бинарлық іздеу .Енді біз іздеудің 2 түрлі алгоритімін
қарастырамыз.Олар: тізбектік іздеу және бинарлық іздеу. Тізбектік іздеудің
алгоритімінде атының айтуы бойынша іздеу берілген элементтердің
біріншісінен басталады, және де ол бүтін элемент табылғанша жалғаса
береді. Осындай іздеу түрін мысалы телефондық анықтамаларда кеңінен
қолдануға болады.
Пузырек тәсілімен сұрыптау тәрізді тәрізді тізбекті іздеуді үлкен
мәліметтер үшін қолдану тиімді емес. Мысалы телефондық анықтамадан
Оналбаева деген фамилияны табу керек болса іздеу барысында
программаға бүкіл анықтаманы қарастырып шығуға тура келеді. Улкен
мәліметтер үшін тізбектей іздеуге қарағанда, бинарлық іздеу тиімді
болып келеді. Бірақ бинарлық іздеу алгоритімі жұмыс істеу үшін
мәліметтер алдын - ала сұрыпталу қажет. Ал тізбектей іздеу сұрыптауды
қажет етпейді. Бинарлық іздеу принципін толық түсіну үшін санды тап
ойынын елестетейік. Мысалы сіздің қарсыласыңыз 1 мен 100 арасында бір
санды ойлайды. Сіз табу үшін бірнеше сандарды айтасыз, ал сіздің
қарсыласыңыз өзі ойлаған саннан үлкен немесе кіші екендігін айтады. Сол
арқылы сіз сандар диапазонын қысқартасыз. Міне, осы үрдісті бинарлық
іздеу деп аталады.
Өсу реті бойынша сұрыпталған, N элементтен тұратын Data
массивіндегі бинарлық іздеудің псевдокодын келесі түрде көруге
болады:

Бинарлық іздеу псевдакоды:
Target:= бүтін сан;
First:=1;
Last:=N;
Found:=false:
While (first =last ) and not (found) to begin
Middle:= (first+last) div 2;
If target data[middle] then begin
Last:=middle-1;
End;
Else if target data[middle] then begin
First:=middle+1;
End;
Else begin
Found:=true;
End;
End;
If found then begin
{бүтін элемент middle индексті позициядан табылды}
Else begin
{бүтін элемент табылған жоқ}
End;

3. Теориялық мағлұматтар
Курстық жұмысты жүзеге асыру үшін программа барысында файл типі
кеңінен қолданылады. Сондықтан Паскаль тіліндегі файл типінің баяндалуы,
файл типінің түрлері және Си тіліндегі файл типінің баяндалуын қарастырып
өтеміз.

3.1 Паскаль тіліндегі-file типінің баяндалуы

Кез-келген типті деректер тобын файл деп атауға болады. Программаға
қажетті деректерді де файл деп атауға болады.есептелген нәтиже және
программаның өзінде файл болып табылады.Паскаль тілінде бірдей типті
(қарапайым немесе күрделі) тізбектерді де атайтын болғандықтан файл
массивке ұқсас болады. Файлдың массивтен айыриашылығы:
а) мұнда жазылатын ақпарат саны көрсетілмейді.
б) әр элементтің өз индексі бойынша анықталмайды,сондықтан қажетті
элементті оның алдындағы элементті алып болғаннан кейін ғана алынады.
Программаның type бөлімінде файл типі келесі жалпы түрде
баяндалады: TYPE NTYPE = FILE OF TC
Мұнда ntype файл типінің идентификаторы, type of tc –ол базалық тип,
файлдық базаның типі ретінде кез-келген қарапайым немесе күрделі тип
баяндалады (type типінен басқа). Файлдың типі немесе файлдың типті
айнымалысы келесі үш әдістің біреуі арқылы анықталады:
NTYPE=FILE OF TC;
NTYPE=TEXT ;
NTYPE=FILE;
Мұнда Text тексттік файлдың стандартты типінің аты. Текст типі
type бөліміне жазылиаса да болады.
Баяндау әдісіне байланысты Pascal 7.0 де файлдың үш түрі бар:
1) типтелген
2) текстік
3)типтелмеген
Паскальда мәліметтің типінің бірі болып сыртқы жады құрылғысында
орналасқан бірдей типті компоненттер тізбек құрастыратын файлдық
айнымалылар ақпаратты енгізу-шығару үшін қолданылады. Енгізу-шығару
әрекетін орындамас бұрын файлдық айнымалысы Assign стандартты процедура
көмегімен нақты қандай да бір сыртқы файлмен байланысуы керек. Файлдармен
жұмыс жасау үшін келесі жалпы стандартты функциялар мен процедураларды
қолдануға болады:
1) ASSIGN (f, name)
2) RESET (f)
3) REWRITE(f)
4)APPEND(f)
5) EOF(f)
6) CLOSE(f)
Типтелген файлдар. Типтелген файлдың кез-келген ұзындығы тұрақты болады.
Сондықтан типтелген файлдың компоненттері олардың реттік нөмірі бойынша
өңдеуге болады. Енгізу-шығару процедураларына бірінші рет қатынас жасағанда
файлдың көрсеткіші файлдың басында тұрады және ол файлдың бірінші
компонентіне сілтейді.Енгізу-шығару процедураларына қатынас жасағанда
файлдың көрсеткіші файлдың келесі компонентіне жылжиды. Енгізу-шығару
стандартты процедуралары енгізу-шығару тізіміндегі айнымалының типтері
файл компоненттерінің типтерімен бірдей болуы керек. Келесі
стандартты функциялар мен процедуралар типтелген файлдармен жұмыс істеуге
көмектеседі:
1) READ
2) WRITE
3) SEEK
4) FILESIZE
5) FILEPOS
Текстік файл. Текстік файл ... жалғасы

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