Іздеу және сұрыптау алгоритмдері: теориясы мен Паскаль тіліндегі жүзеге асырылуы

Тақырыбы: Іздеу алгоритмі Мазмұны Кіріспе Есептің қойылымы Теориялық мағлұматтар 3.1.1 Интерполяциялық іздеу әдісі 3.1.2 Сызықты іздеу әдісі. 3.1.4 Қарапайым алгоритм. 3.2.1 Сұрыптау тәсілі 3.2.2 Сұрыптау алгоритмі 3.2.3 Орналастыру әдісі арқылы сұрыптау. 3.2.4 Көпіршік тәсілі 4 Программаның жазылуы Қорытынды КІРІСПЕ Техниканың даму жетістіктеріне сай ЭЕМ – Программист мұндай программаларды жасаған кезде барлық Іздеу алгоритмі – барлық қолданбалы програмаларда Мәтіндік редактормен жұмыс жасау - өте Есептің қойылуы. Тапсырма: Жол берілген. Барлық «de» жалғауын Мысалы: mende erten mamamen birge bolamin Іздеу алгоритмі Барлық әдістерді статикалық және динамикалық деп Іздеу әдістерін сондай-ақ нақты кілттерді пайдаланатын Интерполяциялық іздеу әдісі Кейбір кітаптарда бұл әдіс «экстраполяция әдісі» T1=M*N; T2=2M*Log(2)N+N*Log(2)N; N – массивтегі элементтердің саны. M – рет іздеуге болады. Тура ауытырудың алгоритмі жасайтын операция саны Сызықты іздеу әдісі. Алдымен linearsearch (сызықты іздеу) деген шағын Біздің басты программамызда екі тип анықталған формальді параметрін баяндауда қолданамыз: Type StrType=String[20] ArrayStrType=Array[1..100] Of StrType; Енді біз шағын прогарамманың басын жаза Function linearsearch(Strings:ArrayStrType; NewString:String; Size:Integer):Integer; {……………………………………………………………………….} {Сызықты іздеу әдісін қолдана отырып, String String қатарынынң әр элементі NewString – әр элемент Strings жодың өрнегінде бір-бірден 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 циклі LinearSearch функциясының қолданылуы. Біздің linearsearch функциямызда басты программада қалай 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,’табылған жоқ’) Қарапайым алгоритм. Алгоритмді қарау үшін бір мысалды қарастырайық. Біз m символы мәтіннің жолының қай Program SimpleSearch; Var T:array[1..40000] of char; {мәтін ролін анықтайды} S: array[1..10000] of char; {жолдың ролін i, j:longint; m, n:longint; begin {программа денесін баяндау} Қарапайым түрде жаздық, енді осы программаның Сұрыптау алгоритмі Сұрыптаудың Шелл әдісі бойынша сұрыптау, Хоар Сұрыптау дегеніміз—берілген жиынның элементтерін белгілі бір Іздеу әдістерінің де әдістері бір-бірімен қатты Тағы сұрыптаудың орналастыру арқылы сұрыптау түрі Орналастыру әдісі арқылы сұрыптау. Бұл әдістің негізгі мәні алдыңғы реттелген 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 (tT[i+1].f3 then begin switch:=true; temp:=T[i]; T[i]:=T[i+1]; T[i+1]:=temp end until not(switch) end Бұл тәсіл ауыстыру тәсілімен сұрыптауды пайдаланады. {Көпіршік тәсілімен сұрыптаудың басталуы} procedure Bubble(var item: DataArray; count:integer); var i,j: integer; x: DataItem; begin for i := 2 to count begin for j := count downto i if item[j-1]>item[j] then begin x := item[j-1]; item[j-1] := item[j]; item[j] := x; end; end; end; { Көпіршік тәсілімен сұрыптаудың аяқталуы Бұл мысалда берілген «item» «Dataitem» элементінің program SortDriver; {бұл программа «test.dat» дисктік файлынан 80 type DataItem = char; DataArray = array [1..80] of char; var test: DataArray; t, t2: integer; testfile: file of char; { Көпіршік тәсілімен сұрыптау} procedure Bubble(var item: DataArray; count:integer); var i,j: integer; x: DataItem; begin for i := 2 to count begin for j := count downto i if item[j-1]>item[j] then begin x := item[j-1]; item[j-1] := item[j]; item[j] := x; end; end; end; begin Assign(testfile, 'test.dat'); Reset(testfile); t := 1; { сұрыптауға кететін символдарды оқу} while not Eof(testfile) do begin read(testfile, test[t]); t := t+1; end; t := t-2; {есептелген элементтердің санын Bubble(test, t); { массивті сұрыптау} { сұрыпталған сиволдық массивтің шығарылуы } for t2 := 1 to t WriteLn; end. Көпіршік тәсілімен сұрыптауының бір ерекшелігі бар: Қорытынды Осы курстық жұмысты жасай отырып мен Қазіргі уақытта компьютерлік технологиялардың мүмкіндіктері өсті. Іздеу және сұрыптау алгоритмінің тиімділігі – Қорыта айтқанда іздеу алгоритмі – ЭЕМ-ның Студенттер үшін Паскаль тілдерінде осындай курстық Қолданылған әдебиеттер тізімі Фаронов В. В. Turbo Pascal 7.0 – Москва, издат. Turbo Pascal – Интернет-руководство. Чинер Р. Язык Турбо Си. «Мир», Немнюгин С. Pascal: Учебный курс. Санкт-Петербург: Рюттен Т., Франкен Г. Turbo Pascal Уэйт М., Прата С., Мартин Д. Программаның листингісі PROGRAM IZDEU; uses crt; VAR SOILEM:STRING; COZ:STRING; K,K1:INTEGER; BEGIN clrscr; WRITELN('MATINDI ENGIZ'); READLN(SOILEM); COZ:='de'; REPEAT K:=POS(COZ,SOILEM); IF K0 THEN BEGIN DELETE(SOILEM,K,2); END; UNTIL K=0; REPEAT K:=POS('an',SOILEM); IF K0 THEN BEGIN DELETE(SOILEM,K,2); INSERT('en',SOILEM,K); END; K1:= POS('ol',SOILEM); IF K10 THEN BEGIN DELETE(SOILEM,K1,2); INSERT('alar',SOILEM,K1); END; UNTIL (K=0) AND (K1=0); WRITELN(SOILEM); readkey; END. Логикалық структураның баяндалуы программаның аты; crt модулін шақыру; 3-5. айнымалыларды баяндау бөлімі: 3. енгізілетін сөйлемнің типі; 4. жойылатын сөздің типі; 5. көмекші бүтін типті айнымалылар, k, 6. программаның негізгі денесінің басталуы; 7. экранды тазалау; 8. «мәтінді енгіз» сөзін экранға шығару; 9. енгізілетін мәтінді экранға шығару немесе 10. меншіктеу операторын қолдану арқылы жойылатын 11. циклдің басталуы; 12. жойылатын создің сөйлемдегі орнын, яғни 13. егер жойылатын сөз табылса, онда 14. жақшаның ашылуы 15. сөйлемнен k позициясынан бастап 2 16. жақшаны жабу; 17. циклдің шарты: позиция 0-ге тең 18. циклдің басталуы; 19. ‘an’ сөзін сөйлемнен іздеп, оның 20. егер k позициясы 0-ге тең 21. жақшаның ашылуы; 22. сөйлемнен k позициясынан бастап 2 23. сөйлемнің k позициясынан бастап ‘en’ 24. жақшаның жабылуы; 25. ‘ol’ сөзін сөйлемнен іздеп, оның 26. егер k1 позициясы 0-ге тең 27. жақшаның ашылуы; 28. сөйлемнен k1 позициясынан бастап 2 29. сөйлемнің k1 позициясынан бастап ‘alar’ 30. жақшаның жабылуы; 31. циклдің шарты: k және k1 32. өзгертілген мәтінді экранға шығару; 33. нәтижені ‘Enter’- ді басқанда бірден 34. программаның соңы. Программаға енгізілген мәліметтер мен алынған нәтиже