Қазақстан республикасының бiлiм және ғылым министрлiгi



бет5/5
Дата31.07.2017
өлшемі1,23 Mb.
#22426
1   2   3   4   5


№8 дәрістің сұрақтары


  1. Массивтерді сұрыптайтын негізгі әдістер туралы айтып беріңіз?

  2. Массивті сұрыптау кезеңінде қалай бейнелеуге болады?

  3. Массивті сұрыптау үшін қандай қосымша процедуралар мен функцияларды дайындап қою керек?



3 ПРАКТИКАЛЫҚ САБАҚТАР

Практикалық сабақ № 1. «Көпіршік әдісімен сұрыптау»

№ 1 практикалық сабақты орындауға арналған методикалық нұсқаулар



Көпіршіктік сүрыптау (көпіршік әдісімен сүрыптау) (Пузырьковая сортировка (сортировка методом пузырька); bublle sorting) — реттелетін жиымның көрші элементтерін тізбектік орын ауыстырудан тұратын сұрыптау тәсіл

Кесте 1.1. Көпіршік әдісіне мысалы


 I = 1


2

3

4

5

6

7

8

44

06

06

06

06

06

06

06

55

44

12

12

12

12

12

12

12

55

44

18

18

18

18

18

42

12

55

44

42

42

42

42

94

42

18

55

44

44

44

44

18

94

42

42

55

55

55

55

06

18

94

67

67

67

67

67

67

67

67

94

94

94

94

94

  Бағдарлама 1.1.

ПРОГРАММА 1.1. КӨПІРШІК ӘДІСІ.

 PROGRAM BS;

VAR I,J,X,N:INTEGER;

A:ARRAY[0..50] OF INTEGER;

BEGIN

WRITELN('массивтің ұзындығын беріңіз');



READ(N);

WRITELN('массив элементтерін беріңіз');

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO FOR J:=N DOWNTO I DO IF A[J-1]>A[J] THEN BEGIN

X:=A[J-1];

A[J-1]:=A[J];

A[J]:=X

END;


WRITELN('нәтиже:');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

 Бұл әдістің жақсартылған нұсқасы Шейкерлік сұрыптау деп аталады



  Кесте 1.2. Шейкерлік сұрыптауға мысалы.

 L = 2

3

3

4

4

R = 8

8

7

7

4

Dir =

 

 

 

 

44

06

06

06

06

55

44

44

12

12

12

55

12

44

18

42

12

42

18

42

94

42

55

42

44

18

94

18

55

55

06

18

67

67

67

67

67

94

94

94

 

Көпіршік және шейкерлік алгоритмдерінің анализі.

Алмастырулар саны

C = (n2n)/2,

Ал орын ауыстырулардың минималды, ортақ және максималды саны келесілерге сәйкес


M = 0, Mavg = 3*(n2 – n)/2, Mmax = 3*(n2 – n)/4

 ПРОГРАММА 1.2. ШЕЙКЕР СҰРЫПТАУЫ.

 PROGRAM SS;

VAR


J,L,K,R,X,N,I:INTEGER;

A:ARRAY[0..50] OF INTEGER;

BEGIN

WRITELN('массивтің ұзындығын еңгізіңіз’);



READ(N);

WRITELN('массивті еңгізіңіз');

FOR I:=1 TO N DO READ(A[I]);

L:=2;


R:=N;

K:=N;


REPEAT

FOR J:=R DOWNTO L DO IF A[J-1]>A[J] THEN BEGIN

X:=A[J-1];

A[J-1]:=A[J];

A[J]:=X;

K:=J


END;

L:=K+1;


FOR J:=L TO R DO IF A[J-1]>A[J] THEN BEGIN

X:=A[J-1];

A[J-1]:=A[J];

A[J]:=X;


K:=J

END;


R:=K-1

UNTIL L>R;

WRITELN('нәтиже:');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

 №1 практикалық сабаққа тапсырма



  1. Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.

  2. Бағдарламаның листингін басып шығару.

  3. Жұмысты ауызша қорғаңыз

2 практикалық жұмыс. Тікелей таңдау әдісі.

№ 2 практикалық сабақты орындауға арналған методикалық нұсқаулар

Тікелей таңдау арқылы сұрыптау - бұл сұрыптаудың ең қолайлы түрі. Әдетте бұл әдіс кестені реттеуді қажет еткен адам ойына ең бірінші келеді. Бұның мәні мынада, мысалы n элементтен тұратын А сандар массиві берілген. Оны таңдау әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет.

Әдістің алгоритмі:



  1. Өлшемі n болатын А массивін толтыру және экранға шығару;

  2. i:=1;

  3. Индекс i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;

  4. A[i] және A[j] элементтерінің орындарын ауыстыру;

  5. i:=i+1 мәні үшін i:=n болғанға дейін 3 және 4 қадамдарды қайталау;

  6. Сұрыпталған А массивін экранға шығару.

Кесте 2.1. Тікелей таңдау бойынша сұрыптауға мысалы


Бастапқы кілттер

44

55

12

42

94

18

06

67

I = 2

06

55

12

42

94

18

44

67

I = 3

06

12

55

42

94

18

44

67

I = 4

06

12

18

42

94

55

44

67

I = 5

06

12

18

42

94

55

44

67

I = 6

06

12

18

42

44

55

94

67

I = 7

06

12

18

42

44

55

94

67

I = 8

06

12

18

42

44

55

94

67
 

 БАҒДАРЛАМА 2.1. Тікелей таңдау бойынша сұрыптау.

PROGRAM SS;

VAR I,J,R,X,N:INTEGER;

A:ARRAY[0..50] OF INTEGER;

BEGIN


WRITELN('МАССИВТІҢ ҰЗЫНДЫҒЫН БЕРІҢІЗ');

READ(N);


WRITELN('МАССИВТІ ЕҢГІЗІҢІЗ');

FOR I:=1 TO N DO READ(A[I]);

FOR I:=1 TO N-1 DO BEGIN

R:=I;


X:=A[I];

FOR J:=I+1 TO N DO IF A[J]

R:=J;

X:=A[R]


END;

A[R]:=A[I];

A[I]:=X

END;


WRITELN('НӘТИЖЕ:');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

  Бұл программада берілген массив бөлігінің ең кіші элементінің индексін(рет нөмірін) табатын MinMas(j) функциясы пайдаланылған. Функцияның j параметрінің мәні массив бөлігінің бірінші элементтерінің рет нөмірін (соңғысы n) көрсетеді.



№2 практикалық сабаққа тапсырма


  1. Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.

  2. Бағдарламаның листингін басып шығару.

  3. Жұмысты ауызша қорғаңыз


Практикалық сабақ №3. Шелл әдісі.

№ 3 практикалық сабақты орындауға арналған методикалық нұсқаулар

Бұл әдіс 1959 жылы Donald Lewis Shell авторының атынан ұсынылды. Бұл алгоритмнің негізгі мәні мынада:


  • Массивтегі ретсіздіктен құтыламыз;

  • Бір-бірінен алшақ орналасқан элементтерді салыстырамыз;

  • Салыстырып отырған интервалдар бірте-бірте кемиді;

  • Соңғы қадамдарды элементтер жай ғана орые алмастырумен шектеледі.

 Кесте 3.1. Шелл әдісімен сұрыптау алгоритмі.

  

44

55

12

42

94

18

06

67

Төрт реттік сұрыптау келесіні береді

 

44

18

06

42

94

55

12

67

Екі реттік реттік сұрыптау келесіні береді

 

06

18

12

42

44

55

94

67

Бір реттік сұрыптау келесіні береді

 

06

12

18

42

44

55

67

94































 Массивтің жазбалануы келесідей болады

A: ARRAY [-h1..n] OF INTEGER

Алгоритмнің өзі t = 4 үшін жазбасы 3.1. бағдарламасында берілген

 ПРОГРАММА 3.1. ШЕЛЛ СҰРЫПТАУЫ.

 PROGRAM SHELLS;

CONST T=4;

H: ARRAY[1..4] OF INTEGER = (15,7,3,1);

VAR

I,J,K,S,X,N,M:INTEGER;



A:ARRAY[-16..50] OF INTEGER;

BEGIN


WRITELN('массивтің ұзындығын беріңіз');

READ(N);


WRITELN('массивтің элементтерін еңгізіңіз');

FOR I:=1 TO N DO READ(A[I]);

FOR M:=1 TO T DO BEGIN

K:=H[M];


S:=-K;

FOR I:=K+1 TO N DO BEGIN

X:=A[I];

J:=I-K;


IF S=0 THEN S:=-K;

INC(S);


A[S]:=X;

WHILE X

A[J+K]:=A[J];

J:=J-K


END;

A[J+K]:=X

END;

END;


WRITELN('нәтиже:');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

№3 практикалық сабаққа тапсырма


  1. Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.

  2. Бағдарламаның листингін басып шығару.

  3. Жұмысты ауызша қорғаңыз


Практикалық сабақ №4. Жылдам сұрыптау.
№ 4 практикалық сабақты орындауға арналған методикалық нұсқаулар

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

program Quitsort;
 uses
   crt;
 Const
  N=10;
 Type
  Mas=array[1..n] of integer;
var
  a: mas;
  k: integer;
function Part(l, r: integer):integer;
var
  v, i, j, b: integer;
begin
  V:=a[r];
  I:=l-1;
  j:=r;
  repeat
    repeat
      dec(j)
    until (a[j]<=v) or (j=i+1);
    repeat
      inc(i)
    until (a[i]>=v) or (i=j-1);
    b:=a[i];
    a[i]:=a[j];
    a[j]:=b;
  until i>=j;
  a[j]:=a[i];
  a[i]:= a[r];
  a[r]:=b;
  part:=i;
end;
procedure QuickSort(l, t: integer);
var i: integer;
begin
  if l    begin
      i:=part(l, t);
      QuickSort(l,i-1);
      QuickSort(i+1,t);
    end;
end;
begin
  clrscr;
  randomize;
  for k:=1 to 10 do
    begin
      a[k]:=random(100);
      write(a[k]:3);
    end;
  QuickSort(1,n);
  writeln;
  for k:=1 to n do
    write(a[k]:3);
  readln;
end.

Мысалы:
60,79, 82, 58, 39, 9, 54, 92, 44, 32


60,79, 82, 58, 39, 9, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9,79, 82, 58, 39, 60, 54, 92, 44, 32
9, 32, 82, 58, 39, 60, 54, 92, 44, 79
9, 32, 44, 58, 39, 60, 54, 92, 82, 79
9, 32, 44, 58, 39, 54, 60, 92, 82, 79
9, 32, 44, 58, 39, 92, 60, 54, 82, 79
9, 32, 44, 58, 39, 54, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 60, 39, 54, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 58, 54, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 92, 82
9, 32, 39, 44, 54, 58, 60, 79, 82, 92

№4 практикалық сабаққа тапсырма


  1. Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.

  2. Бағдарламаның листингін басып шығару.

  3. Жұмысты ауызша қорғаңыз


Практикалық сабақ №5. Қарапайым әдістің модификацияланған тәсілі

№ 5 практикалық сабақты орындауға арналған методикалық нұсқаулар



 

Сандық алгоритмдер сандармен математикалық есептеулер жүргізуге арналған, ал сандық емес алгоритмдер әртүрлі құрылымданған мәліметтермен жұмыс істейді. Ең маңызды есептеусіз алгоритмдердің бірі болып сұрыптау және іздеу табылады. Объектілердің берілген тізбегін қандай да бір анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды. Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар массивтерін сұрыптау тән. Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив. Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау). Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.

Сурет.5. Массивті қарапайым сұрыптаудың модификацияланған әдісімен іріктеудің жалрыланған алгоритмі




Кесте 5.1. Сұрыптау мысалысы


Массивті қарастыру номері i

Бастапқы массив

Минималды элемент

Орны ауыстырылатын элемент

Орын ауыстырғаннан кейінгі массив

Номер

Мәні

Номер

Мәні




 1

 (2,8,1,3,7)

 3

 1

 1

 2

 (1,8,2,3,7)

 2

 1,(8,2,3,7)

 3

 2

 2

 8

 1,(2,8,3,7)

 3

 1,2,(8,3,7)

 4

 3

 3

 8

 1,2,(3,8,7)

 4

 1,2,3,(8,7)

 5

 7

 4

 8

 1,2,3,7,8

Келесі бейнеленулерді еңгізейік  :


      К- минималды элементтің номері,
      J – массив элементінің номері,
      М және А(К)- массивтің минималды элементінің бір мәні,
      i – орны ауыстырылатын элементтің номері,
      А(i)- орны ауыстырылатын элементтің мәні.
Онда қарапайым сұрыптаудың модификацияланған әдістің циклдік алгоритмі келесі түрге ие болады.


Сурет.6. қарапайым сұрыптаудың модификацияланған әдістің циклдік алгоритмі


№5 практикалық сабаққа тапсырма


  1. Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.

  2. Бағдарламаның листингін басып шығару.

  3. Жұмысты ауызша қорғаңыз



5 СОӨЖ және СӨЖ
Кесте 1 – СОӨЖ және СӨЖ жоспары

№ п/п


СОӨЖ

СӨЖ

1

2

3

1.

Элементтерді файлда сұрыптау (бағдарлама, есеп беру).

Массивтерді сұрыптаудың жақсартылған әдістері (бағдарлама, есеп беру).




Реттелген файлдарды сұрыптау (бағдарлама, есеп беру).

Рекурсияға кіріспе (реферат).




Тізімдік құрылымдар (реферат).

Деректердің динамикалық құрылымдары (реферат).




Деректерді іздеу және сақтау(реферат).

Алгоритмдерді зерттеу әдістері (реферат).




Ағаштар және графтар (реферат).

Массивте элементті іздеу әдістері (бағдарлама, есеп беру).

Каталог: ebook -> umkd
umkd -> Мамандығына арналған Сұлтанмахмұттану ПӘнінің ОҚУ-Әдістемелік кешені
umkd -> Қазақстан Республикасының
umkd -> Қазақстан Республикасының
umkd -> Студенттерге арналған оқу әдістемелік кешені
umkd -> ПӘннің ОҚУ Әдістемелік кешені 5В011700 «Қазақ тілі мен әдебиеті» мамандығына арналған «Ұлы отан соғысы және соғыстан кейінгі жылдардағы қазақ әдебиетінің тарихы (1941-1960)» пәнінен ОҚытушыға арналған пән бағдарламасы
umkd -> «Балалар әдебиеті» пәніне арналған оқу-әдістемелік материалдар 2013 жылғы №3 басылым 5 в 050117 «Қазақ тілі мен әдебиеті»
umkd -> ПӘннің ОҚУ-Әдістемелік кешенінің
umkd -> 5 в 011700- Қазақ тілі мен әдебиеті
umkd -> 5 в 011700- Қазақ тілі мен әдебиеті
umkd -> «Филология: қазақ тілі» мамандығына арналған


Достарыңызбен бөлісу:
1   2   3   4   5




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет