Іздеу және сұрыптау алгоритімдері

Іздеу алгоритмі
Сұрыптау алгоритмі
Орналастыру әдісі арқылы сұрыптау.
Сыртқы сұрыптау
Тура бірігу
Кәдімгі бірігу
Бөлу сұрыптауы (Quicksort)
Барлық әдістерді статикалық және динамикалық деп қарастыруға болады. Массивтен статикалық әдіспен іздеу кезінде оның мәндері өзгермейді. Массивтен динамикалық әдіспен іздеу кезінде оның өлшемі өзгеруі мүмкін, себебі ол қайтадан сұрыпталады. Біз көбінде статикалық әдісті қолданамыз, үйткені мәтіндік редактордағы сөздерді өзгерте алмаймыз, ал динамикалық тәсіл ойын құрғанда пайдаланылады.
Іздеу әдістерін сондай-ақ нақты кілттерді пайдаланатын және туындаушы кілттерді пайдаланатын деп екіге бөледі. Бұл жағдайда кілт деп өзіміз іздеп отырған сөзді айтады. Мәтіндік редакторға қолданылатын кілт – туындаушы болып табылады, себебі ізделінетін массив алдын-ала алфавит бойынша сұрыпталған. Бұл рет іздеуді жеңілдету үшін пайдаланылады.
Кейбір кітаптарда бұл әдіс «экстраполяция әдісі» деп аталады. Экстарполяция – берілген интервалдан тыс бірнәрсені анықтау әдісі, ал интерпояция – сол интервал аралығына анықтау әдісі. Сондықтан да «экстраполяция әдісі» деп атау қате, үйткені ізделінетін сөзді шекарадан тыс аумақта іздеу мүмкін емес.бұл әдісті сипаттамас бұрын сізге ағылшын тіліндегі «treasure» сөзінің аудармасы қажет болды дейік. Яғни сіздің алдыңызда тапсырма – осы сөзді сөздіктен іздеу. Біздің келесі іс-әркеттеріміз қандай да бір іздеу алгоритмін құрумен жалғасады. Ізделінетін сөзді алфавит бойынша сұрыпталған массивтен іздейміз, ал керекті сөз бізге белгілі. Оны тез арада тауып алуға болады. Енді осы іздеуге толығымен тоқталайық. Бізге керекті сөз «т» әрпінен басталады, яғни алфавиттің екінші бөлігінде, немесе біз ол қандай орында тұрғанында шамамен есептеп ала аламыз. Яғни қанша дым жасауға болатынын анықтап аламыз. Егер ізделінетін массив үлкен болса осы әдіс арқылы оның шекрасын көрсетіп, тек осы аралықты ғана іздеуге болады.
        
        ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ
ТҰРАР РЫСҚҰЛОВ атындағы ҚАЗАҚ ЭКОНОМИКАЛЫҚ УНИВЕРСИТЕТІ
Кафедра «Қолданбалы информатика»
Реферат
Тақырыбы: Іздеу және сұрыптау ... ... ... ИЭФ 104 - ... Жұмажанов Б.Ж.
АЛМАТЫ 2008
Іздеу алгоритмі
Барлық әдістерді статикалық және динамикалық деп қарастыруға болады.
Массивтен статикалық әдіспен іздеу кезінде оның ... ... ... ... ... кезінде оның өлшемі өзгеруі ... ол ... ... Біз ... ... ... ... мәтіндік редактордағы сөздерді өзгерте ... ал ... ойын ... ... ... ... нақты кілттерді пайдаланатын және туындаушы
кілттерді пайдаланатын деп екіге бөледі. Бұл жағдайда кілт деп ... ... ... ... ... ... қолданылатын кілт – туындаушы
болып табылады, ... ... ... ... ... ... Бұл рет іздеуді жеңілдету үшін пайдаланылады.
Кейбір кітаптарда бұл әдіс «экстраполяция әдісі» деп ...... ... тыс бірнәрсені анықтау әдісі, ал
интерпояция – сол интервал ... ... ... ... ... әдісі» деп атау қате, үйткені ізделінетін сөзді ... ... ... ... ... әдісті сипаттамас бұрын сізге ағылшын
тіліндегі «treasure» сөзінің аудармасы ... ... ... Яғни ... тапсырма – осы сөзді сөздіктен іздеу. Біздің келесі іс-
әркеттеріміз ... да бір ... ... ... ... Ізделінетін
сөзді алфавит бойынша сұрыпталған массивтен іздейміз, ал керекті сөз бізге
белгілі. Оны тез арада тауып ... ... Енді осы ... толығымен
тоқталайық. Бізге керекті сөз «т» әрпінен басталады, яғни алфавиттің екінші
бөлігінде, немесе біз ол ... ... ... ... ... ... Яғни ... дым жасауға болатынын анықтап аламыз. Егер ізделінетін
массив үлкен болса осы әдіс арқылы оның шекрасын көрсетіп, тек осы ... ... ... Ол үшін ... ек ... аламыз:
T1=M*N;
T2=2M*Log(2)N+N*Log(2)N;
N – массивтегі элементтердің саны.
M – рет іздеуге болады.
Тура ауытырудың алгоритмі жасайтын операция саны M*N-ге тең. ... ... ... ... тең, оған тағы ... ... қосамыз. T1=T2 кезінде екі алгоритм де тиімді шекарада боламыз.
Алдымен linearsearch (сызықты ... ... ... ... Оның үш ... ... Strings – ... өрнектер қптпры,
newstring – жолдың өрнек, осыны іздеу қажет және size – қаралатын қатардың
элемпенттер саны.
Біздің басты ... екі тип ... және ... ... ... ... қолданамыз:
Type StrType=String[20]
ArrayStrType=Array[1..100] Of StrType;
Енді біз шағын прогарамманың басын жаза аламыз:
Function linearsearch(Strings:ArrayStrType; NewString:String;
Size:Integer):Integer;
String қатарынынң әр ... ... – пен ... Егер ... ... ... онда табылған элементтің позийиясы (индексі)
қайтарылады. Ал егер NewString – ті барлық ... ... ... ... ... ... ... онда 0 мәні қайтарылады, бұл ... түк ... ... сөз. ... ... барлық элементтер
кезекпен салыстырылады. Сондықтан бұл әдісті сызықты ... ... ... деп ... ... Strings ... өрнегінде бір-бірден кездеседі деп
ойлайық(егер бұлай болмаса, онда ... ... рет ... ... Егер ... ... әрі қарай процесс тоқтатылады,
сондықтан логикалық Found айнымалысын енгізейік:
Var position:Integer;
Found:Boolean;
Begin
Position:=1;
Found:=False;
While (not Found) And (position=size) ... Strings ... ... {If…Then}
Position:=position+1;
End; {While циклінің соңы}
If not Found Then linearsearch:=0;
End; {linearsearch}
Егер сіз көңіл аударсаңыз, While ... мына ... ... жүре ... not Found ... ... болмағанша не position
мәні size-дан асып кетпегенше.
LinearSearch функциясының қолданылуы.
Біздің linearsearch функциямызда басты ... ... ... Мысалы, n соңды аттардан тұратын қатарда іздеу жүргізу керек
болсын, осы мақсатпен басты ... names ... ... ... ізделінді есімді сақтайтын NewName айнымалысы да баяндалған. ... ... ... ... үзіндісі былай болады:
Type StrType=String[20];
ArrayStrType=Array[1..100] Of StrType;
Var Names:ArrayStrType;
NewName:StrType;
N,location:Integer;
…….
Location:=linearsearch(names,n);
If location>0
Then WriteLn(NewName,’орны’,location)
Else WriteLn(newName,’табылған жоқ’)
Сұрыптау алгоритмі
Сұрыптаудың Шелл ... ... ... Хоар ... ... ... ... сияқты түрлері бар.
Сұрыптау дегеніміз—берілген ... ... ... ... сәйкес орналастыру. Оның негізгі көздеген мақсаты – сұрыпталған
жиыннан керек элементтерді іздеуді жеңілдету. Сұрыптауды көбіне массивтерді
және файлдарды сұрыптағанда көп ... Бұл ... ... ішкі ... ... деп ... Массивтер “ішкі” (жедел) жадыда
орналасатындықтан, ішкі сұрыптау болады. Бұл ... тез ... ... ... ... бірақ сыйымдылығы үлкендеу “сыртқы” жадыда, яғни
есте сақтау құрылғыларында (диск, лента т.б.) сақталатындықтан, оны сыртқы
сұрыптау деп ... ... де ... ... ... ... Әсіресе,
біз бинарлы әдісті, егер қатарымыз сұрыпталған болса, тинтен қолдана
алмаймыз. ... біз ... ... ... ... ... кезде қолданамыз. Ал ол кітапшадағы фамилиялар ... ... ... ... ... бар ... ... міндетті түрде болу
керек.
Тағы сұрыптаудың ... ... ... түрі бар. Бұл ... мәні алдыңғы реттелген элементтерге соңғы элементтерді бір-бірлеп
қосып отыруда. Әрине, бұл сұрыптаумен ... ... көп ... созылатын
процесс деп ойлауы мүмкін. Бірақ олай емес, өйткені алдыңғы элементтер
сұрыпталған күйде ... да, ... ... сәйкес кез-келген жерге
қоямыз.
Орналастыру әдісі арқылы сұрыптау.
Бұл әдістің негізгі мәні ... ... ... ... ... қосып отыруда. Бірінші қадамға алғашқы екі ... ... ... осы екі ... ... сәйкес орынға
үшінші элемент орналастырылады. Үш сұрыпталған элементтерге ... ... Ол жаңа ... өз ... ... Сөйтіп,
сұрыпталған n-1 элементтерге соңғы n-ші ... ... ... ... ... ... ... мына процедураны қарастырайық:
Procedure ins(var x:Array Of Integer; n:Integer);
Var i,j,t:Integer;
Begin
For i:=1 To n-1 Do
Begin
T:=x[i];
J:=i-1;
While (j>=0) And (t

Пән: Информатика
Жұмыс түрі: Реферат
Көлемі: 5 бет
Бұл жұмыстың бағасы: 300 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Бухгалтерлік есептің ақпараттық жүйесінің жалпы сипаттамасы.7 бет
Turbo Pascal-да программалау13 бет
Іздеу алгоритмі14 бет
Жоғары деңгейлі тілдерінде программалау12 бет
Лабиринт16 бет
Паскаль тілі туралы мәлімет15 бет
Санды табу11 бет
Сұрыптау және іздеу тәсілдері14 бет
„Трэк” ойыны21 бет
Excel электрондық кестесі және онымен деректер қоры ретінде жұмыс жасау12 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь