Зертханалық жұмыс №1 Тақырыбы: Ақпаратты көрсету. Ақпаратты есептеу
жүктеу/скачать 0.88 Mb.
|
- Бұл бет үшін навигация:
- Бастапқы кілттер
- Тікелей таңдау сұрыптауын қолдану
- Көпіршік сұрыптауының мысалы
| Зертханалық жұмыс №10
Тақырыбы: Тізбектердегі іздестіру алгоритмдері (10 апта 2 сағ) 10.1. Жұмыс мақсаты – Тізбектердегі іздестіру алгоритмдерімен танысып, қарапайым есептерге іздестіру алгоритмдерін құрып үйрену. 10.2. Әдістемелік нұсқау 10.2.1. Сұрыптау алгоритмдері. Тікелей қосу көмегімен сұрыптау Мұндай әдіс карта ойындару үшін кеңінен қолданылады. Элементтер (карталар) “дайын” а1,…, аi-1 тізбектер және берілген тізбектерге ойша бөлінеді. Әрбір қадамда i = 2-ден бастап және i-ді әр қадам сайын бірге өсіре отырып берілген тізбектен i – ші элемент алынады және дайын тізбекке қойылады, бұл кезде ол қажетті жерге қосылады. Тікелей қосу көмегімен сұрыптау мысалы:
Б ұл 8 кездейсоқ таңдалған сандарды қосу көмегімен сұрыптау процесі. Бұл сұрыптау алгоритмі: FOR i :=2 to n DO x: = a[i]; { х-ті a[1]… a[i] тізбегінің сәйкес орнына қосу } END Нақты сәйкес орынды іздестіру процесінде тізбектер бойынша салыстыру және жүріп отыруды кезекпен ауыстырып отыру, былайша айтқанда елеп отырған ыңғайлы, яғни х кезектегіаj элементпен салыстырылады, одан кейін немесе х бос орынға қосылады, немесе аj оңға ығыстырылады (беріледі) және процесс солға “кетеді”. Елеу процесі төмендегі екі жағдайдың бірі орындалғанда аяқталуы мүмкін: кілті х-тің кілтінен кіші болатын аj элементі табылса. Дайын тізбектің сол жақ шетіне жетсе. Procedure StraightInsertion; Var i, j: index; x : item; Begin For i:=2 то n DO x: = a[i]; a[0] : = x; j : = 1; WHILE x < a[j – 1] DO a[j] : = a[j – 1]; j : = j – 1; END; a[j] : = x; END; END STRAIGHT INSERTION 10.3. Жеке тапсырмалар Тізімді тура қосу көмегімен сұрыптау алгоритмі жүргізілген барлық қадамдардың нәтижесін жазыңдар (7; 3; 9; 4; 2; 5; 6; 1; 8) (8; 6; 4; 3; 9; 7; 5; 1; 2) (1; 9; 6; 8; 4; 2; 7; 5; 3) (6; 3; 2; 8; 4; 7; 5; 9; 1) (4; 6; 8; 9; 5; 7; 3; 2; 1) (4; 7; 5; 1; 2; 9; 8; 3; 6) (8; 6; 2; 5; 9; 3; 4; 1; 7) (3; 9; 6; 8; 4; 7; 1; 5; 2) (23; 17; 21; 3; 42; 9; 13; 1; 2; 7; 35; 4) (2; 35; 8; 41;9;41;11;6;58;77; 23;7) (7;13;52;77;53;56;68;2;71;22;95;58) (51;50;52;94;15;25;38;68;15;44;84;25) (81;79;64;23;38;64;2;26;24;37;8;41) (49;10;66;3;64;36;54;49;19;1;82;77) (88;49;17;22;19;45;96;64;28;53;29;35) (1;36;49;27;77;60;11;42;50;66;57;44) (6;97;35;91;92;21;84;57;59;17;10;67) (9;5;43;76;34;20;52;39;87;51;47;1) (43;82;28;32;9;24;35;75;85;63;52;34) (16;52;83;84;62;91;20;37;81;22;30;26) Зертханалық жұмыс №11 Тақырыбы: Тікелей қосу және тікелей таңдау әдістері бойынша сұрыптау алгоритмдері (11 апта, 2 сағ) 11.1. Жұмыс мақсаты – Тікелей қосу және тікелей таңдау әдістері бойынша сұрыптау алгоритмдерін құрып үйрену. 11.2. Әдістемелік нұсқау 11.2.1. Сұрыптау алгоритмдері. Тікелей таңдау көмегімен сұрыптау Бұл тәсіл келесі принциптерге негізделген: Ең кіші кілті бар элемент таңдалады. Ол а1 бірінші элементпен орын алмастырады Одан кейін процесс қалған n –1 элементке, n –2 элементке, және т.с.с. ең үлкен бір ғана элемент қалғанға дейін қайталанады. Бұл әдіспен жұмыс процесі жоғарыдағы 8 кілт үшін құрылған алгоритм төмендегідей: FORi: = 1 ton – 1 do а[i] … a[n]-лердің ең кішісінің индексін k-ға меншіктеу; а[i] жәнеa[k]-ның орындарын ауыстыру; end Тікелей таңдау сұрыптауын қолдану
Тікелей таңдау деп аталатын бұл әдіс белгілі бір мағынада тікелей қосуға қарама-қарсы әдіс. Тікелей қосудың әрбір қадамында берілген тізбектің кезектегі бір ғана элементі және дайын тізбектің барлық элементі қарастырылады, солардың ішіндегі қосу нүктесі ізделеді; тікелей таңдау кезінде ең кіші кілті бар бір элементті іздестіру үшін берілген тізбектің барлық элементтері қарастырылады және табылған элемент дайын тізбекке кезектегі элемент ретінде орналастырылады. Тікелей таңдаудың толық алгоритмі төмендегі программа 11.1-де келтірілген. PROCEDURE StraightSelection: VAR i,j,k: intex; x: item; BEGIN FOR i: = 1 TO n - 1 DO k: = i; x: = a[i]; FOR j: = i + 1 TO n DO IF a[j] < x THEN k: = j; x: = a[k] END END; END StraightSelection Программа 11.1. Тікелей таңдау көмегімен сұрыптау. 11.3. Жеке тапсырмалар Тізімді тура таңдау сұрыптау алгоритмі көмегімен жүргізілген барлық қадамдардың нәтижесін жазыңдар (7; 3; 9; 4; 2; 5; 6; 1; 8) (8; 6; 4; 3; 9; 7; 5; 1; 2) (1; 9; 6; 8; 4; 2; 7; 5; 3) (6; 3; 2; 8; 4; 7; 5; 9; 1) (4; 6; 8; 9; 5; 7; 3; 2; 1) (4; 7; 5; 1; 2; 9; 8; 3; 6) (8; 6; 2; 5; 9; 3; 4; 1; 7) (3; 9; 6; 8; 4; 7; 1; 5; 2) (23; 17; 21; 3; 42; 9; 13; 1; 2; 7; 35; 4) (2; 35; 8; 41; 9; 41; 11; 6; 58; 77; 23; 7) (7; 13; 52; 77; 53; 56; 68; 2; 71; 22; 95; 58) (51; 50; 52; 94; 15; 25; 38; 68; 15; 44; 84; 25) Зертханалық жұмыс №12 Тақырыбы: Тікелей алмастыру әдісі бойынша сұрыптау алгоритмі (көпіршікті және Шейкерлік сұрыптау) (12 апта, 2 сағ) 12.1. Жұмыс мақсаты – Тікелей алмастыру (көпіршікті) әдісі, және Шейкерлік сұрыптау алгоритмдерін құрып үйрену. 12.2. Әдістемелік нұсқау 12.2.1. Тікелей алмастыру әдісімен сұрыптау (көпіршік әдісі). Тікелей сұрыптау алгоритмі элементтердің көршілес жұбын салыстыру және орнын ауыстыруға негізделген және бұл процесс барлық элементтер реттелгенге дейін жалғастрылады. Егер массивтерді горизонталь құрылымды емес, вертикаль деп қарастырсақ, онда элементтерді суы бар ыдыстағы көпіршік деп интерпритациялауға болады, мұнда әрбіреуінің салмағы оның кілтіне сәйкес келеді. Бұл жағдайда әрбір жүрісте бір көпіршік оның салмағына сәйкес көтеріледі. Көпіршік сұрыптауының мысалы
PROCEDURE BybbleSort; VARi,j, x: integer; BEGIN FOR i: =2 TO n DO FOR j: = n TO i DO If a[j-1]> a[j] THEN begin x: = a[j - 1]; a[j-1]:=a[j]; a[j]: = x end END; Көпіршік сұрыптауының блок-схемасы жүктеу/скачать 0.88 Mb. Достарыңызбен бөлісу:
|