Тақырыбы: Іздеу алгоритмі
Мазмұны
Кіріспе
Есептің қойылымы
Теориялық мағлұматтар
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. программаның соңы.
Программаға енгізілген мәліметтер мен алынған нәтиже