Паскаль тілінің көмегімен сұрыптау және іздеу алгоритмдерін құрастыру

 

Мұнда ұяшықтарда масситвің  элементтерінің мәндері жазылып, төменде  индекстері көрсетілген, яғни M4(I)=31, M4(II)=28, …, M4(XII)=30.

Егер массивтің базалық  типі массивтік болса, онда қарастырылып отырған массивтің өлшемі жоғарылайды.

Мысал.

    Type vektor=array[1..5] of integer;

matr=array[1..5] of vector;

Var   A: matr;

 

Мұндағы А- екі өлшемді  массив, элементтері А[1] [2] немесе А[1,2] түрлерінің бірімен көрсетіледі.

А массивін былайша сипаттауға болар еді:

 

Var   A: array[1..5, 1..5] of integer

Сөйтіп кез келген өлшемді массивтерді сипаттауға болады. Паскальда массивтің өлшеміне шек қойылмаған, ол тек пайдаланылатын компьютер жадының сыйымдылығымен шектеледі.

Іс жүзінде, бір және екі өлшемді массивтер жиі  қолданылады. Жалпы бір өлшемді  массив математикадағы вектор, ал екі өлшемді массив матрица ұғымдарымен пара-пар.

 

МАССИВТЕРДІ ӨҢДЕУ  МЫСАЛДАРЫ

Массивтердің программада  қолдану тәсілдерін көрсету мақсатымен бірнеше мысалдар келтірейік.

1-мысал. Жиырма нақты  сан берілген. Осы сандардың арифметикалық ортасын табатын программа құру керек.

Осы 20нақты сандар тобын  а массиві деп қарастырсақ, массивтің  элементтері а[1], а[2], …, а[20] нақты сандар болады.

 

Program M_1;

Var   a: array [1..20] of real;

i: integer;

s: real;

Begin

for i:=1 to 20 do read(a[i] );

s:=0;

for i:=1 to 20 do s:=s+a[i];

s:=s/20;

write(s);

End.

 

Бұл программада 20 тұрақтысы  төрт рет қайталанады, ал егер массив элементтерінің саны өзгеретін болса, программаға да бірнеше өзгеріс  енгізуге тура келеді, сондықтан массив элементтерінің санын тұрақтылар тарауында анықтап алу тиімді, бұл жағдай жоғарыда келтірілген программа төмендегі түрге көшеді.

 

Program M_1;

const n=20;

Var   a: array [1..n] of real;

i: integer;

s: real;

Begin

read(n);

for i:=1 to n do read(a[i] );

s:=0;

for i:=1 to n do s:=s+a[i];

s:=s/n;

write(s);

End.

 

Бұл жағдайда массив элементтерінің саны өзгеретін болса, онда программада  бір ғана өзгеріс жасалады: n тұрақтысы қайта анықталады.

 

2-мысал. Берілген х₁, х₂, …, х_n сандық массивін өспелі етіп реттейтін программа құру керек.

Программа құру үшін таңдау әдісімен реттеу алгоритмін қолданайық. Бұл алгоритмде біртіндеп салыстырып жылжыту арқылы массивтің ең кіші элементін бірінші орынға шығарамыз, қалғандарының ішінен тағы да ең кіші элементін екінші орынға шығарамыз, т.с.с осы әрекетті соңғы элементке дейін қайталаймыз.

Осы алгоритмнің 5 элементі массивпен орындалу схемасын келтірейік.

 

i=1        i=2       i=3        i=4

x[1]=5                   3           3      3       3         3       3      3        3      3

x[2]=45                 45        45     21     5         5       5      5        5      5

x[3]=21                 21        21     45    45        45     21    17      17    17

x[4]=3                   5           5       5      21       21     45    45      45    21

x[5]=17                 17        17     17    17        17     17    21      21    45

 

Program M_2;

const n=5;

Var i, j, min: integer;

x: array [1..n] of integer;

Begin

{*Массивтің элементтерін  көрнекті түрде енгізу керек*} 

{*………………………………………………………….*}

    For i:=1 to n do

Begin

Write(‘x[‘,i,’]=,);

Readln(x[i] );

End:

{*…………………………………………………………………*}

{*Массивтің элементтерін біртіндеп салыстырып алмастыру*}

{*………………………………………………………………*}

For i:=1 to n do

Begin

For j:= i+1to n do

if x[j]<x[i] then

  Begin min:=x[j]; x[j]:=x[i]; x[i]:=min End;

Write(x[i], ‘   ’);

End.

 

    x[1]=5                  

    x[2]=45                

    x[3]=21                

    x[4]=3                  

    x[5]=17    

   3   5   17   21  45

 

Бұл мысалда көрнекті түрде массив элементтерінің мәндерін енгізу ұйымдастырылған және элементтерді алмастыру тәсілі көрсетілген.

3-мысал. Нақты сандардан  тұратын n жолды және n бағаналы квадрат матрица берілсін. Осы матрицаны соңғы жолының элементтерін басқа жолдарының сәйкес элементтерінен алып, өзгерту керек.

Программада n=5 деп алайық.

 

Program M_3;

const n=5;

Var a: array [1..n] of integer;

         i, j: integer;

Begin

 

{*Матрицаның элементтерін көрнекті түрде енгізу керек*} 

{*……………………………………………………………..*}

   

For i:=1 to n do

   For j:=1 to n do

 

       Begin

Write(‘a[’,i, ‘,’,j,‘]=’,);

Readln(a[i,j] );

End;

 

{*Матрицаның жаңа элементтерін табу*}

{*………………………………………………………………*}

 

For i:=1 to n-1 do

     For j:=1 to n do

a[i,j]:=a[i,j]-a[n,j];

{*………………………………………………………………*}

{*Матрицаның элементтерін экранға беру*}

{*………………………………………………………………*}

For i:=1 to n do

   Begin

 For j:=1 to n do

Write(a[i,j]:4);

Writeln;

     End;

{*………………………………………………………………*}

End.

 

Жоғарыдағы мысалдарда массив элементтерінің бүтін (integer) және нақты (real) типті болған, ал элементтер индекстерінің өзгеру аралығы бүтін сандармен көрсетілген түрлері қарастырылған.

 

4-мысал. Арнайы белгілеулер  енгізу арқылы бейнеленген шахмат  кестесінің алғашқы позициясын экранға шығаратын программа жазу керек

 

A B C D E F G H

8 ҚЛ ҚА ҚС ҚФ ҚК ҚС ҚА ҚЛ

7 ҚП ҚП ҚП ҚП ҚП ҚП ҚП ҚП

6 .. .. .. .. .. ..   ..  ..

5 .. .. .. .. .. ..   ..  ..

4 .. .. .. .. .. ..   ..  ..

3 .. .. .. .. .. ..   ..  ..

2 АП АП АП АП АП АП АП АП

1 АЛ АА АС АФ АК АС АА АЛ

 

Шахмат тақтасын бағаналары А..Н, жолдары 1..8 аралықтарында жататын  екі өлшемді массив ретін қарастырамыз.

 

Program M_4;

Type

f=(‘ҚП’, ‘ҚЛ’,‘ҚА’,‘ҚС’,‘ҚФ’,‘ҚК’,‘АП’,‘АА’,‘АС’,‘АФ’,‘АК’,‘АЛ’)

Var tt: array [‘a’..‘h’..‘i’..‘B’ ] of  f;

             i: integer;  c:char;

Begin

{*2 және 7 жолдарының фигураларын  орналастырамыз*} 

For i:=‘a’ to ‘h’ do

       Begin

tt[c, 7]:=‘ҚП’;

tt[c, 2]:=‘АП’;

          End;

{*басқа фигураларды орналастырамыз*}

tt[‘a’, 8]:=‘ҚЛ’;  tt[‘a’, 1]:=‘АЛ’;

tt[‘b’, 8]:=‘ҚА’; tt[‘b’, 1]:=‘АА’;

tt[‘с’, 8]:=‘ҚС’;  tt[‘c’, 1]:=‘АС’;

tt[‘d’, 8]:=‘ҚФ’; tt[‘d’, 1]:=‘АФ’;

tt[‘е’, 8]:=‘ҚК’;  tt[‘e’, 1]:=‘АК’;

tt[‘f’, 8]:=‘ҚС’;  tt[‘f’, 1]:=‘АС’;

tt[‘g’, 8]:=‘ҚА’;  tt[‘g’, 1]:=‘АА’;

tt[‘h’, 8]:=‘ҚЛ’; tt[‘h’, 1]:=‘АЛ’;

{*бос орындар*}

For i:=6 downto 3 do

     For c:=‘a’ to ‘h’ do tt[‘c’, 1]:=‘..’;

{*Тақтаны экранға шығарамыз*}

For с:=‘A’ to ‘H’ do Write(c:4);

Writeln;

 For i:=8 downto 1 do

Begin

Write(i:2);

For c:=‘A’ to ‘H’ do Write(tt[c,1]);

Writeln;

     End;

End.

Бұл мысалда массив элементтерінің индекстерінің аралығы символдық  тұрақтылармен көрсетілген, ал элементтерінің типі аталу типімен берілген.

 

ІІ. Паскаль тілінің көмегімен сұрыптау және іздеу алгоритмдерін құрастыру

2.1 Іздеу алгоритмі

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

 

2.1.1 Сызықтық іздеу

Сызықтық іздеу қосақтасқан  шартты (while-do, repeat-until) циклдер бойынша жүргізіледі. Бірінші шарт массивке қатысты индексті қадағалайды, мысалы, (i<=N). Екінші шар – бұл іздеу шарты. Біздің жағдайда while-do бұл іздеуді жалғасыру шарты: (A[i]<>X), ал repeat-until бұл іздеуді тоқтату шарты (A[i]=X). Цикл денесінде көбінесе әдетте тек бір ғана оператор жазылады: массивтегі индекстердің өзгеруі.

Циклдан шыққан соң, біздің қандай шарт бойынша шыққандығымыз  туралы тексеруіміз қажет. if операторы бойынша бірінші цикл шарты қайталанылады. Егер бұл шарт орындалса, онда while-do циклында іздеудің сәтті аяқталғандығы, ал repeat-until циклының сәтсіз аяқталғандығы туралы айтуға болады.

 

Мысал: Сызықтық іздеу

program Poisk1;

var  A:array[1..100] of integer;

N, X, i:integer;

begin

read(N); {N<=100}

for i:=1 to N do read(A[i]);

read(X);

i:=1; {i:=0;}

while (i<=N) and (A[i]<>X) do i:=i+1;

{repeat i:=i+1; until (i>N) or (A[i]=X);}

if i<=N then write(X,' санының

A массивінің ',i,' орнына алғашқы енгізілуі')

else write('табылмады');

end.

 

Соңғы енгізілу бойынша іздеу кезінде енгізуден кейін келесі операторлар орындалуы керек:

 

i:=N; {i:=N+1;}

while (i>=1) and (A[i]<>X) do  i:=i-1;

{repeat i:=i-1; until (i<1) or (A[i]=X);}

if i>=1 then write(X,' санының

A массивінің ',i,' орнына соңғы енгізілуі')

else write('табылмады');

 

 

2.1.2 Шектеу қою арқылы іздеу

Шектеу қою арқылы іздеудің мақсаты, массивтің санына байланысты циклде бірнеше рет шартты тексеру арқылы іздемеу. Мұны массивке шектеу қою арқылы жасауымызға болады: іздеу шартын қанағаттандыратын  кез келген элемент. Осыған байланысты индекстің өзгеруіне шектеу қойылады.

Циклдан шығу, яғни іздеу  шарты элемент табылған соң немесе шектеу қойылған жерде аяқталады. Осыған байланысты, циклдан шыққан соң біздің тақанымыз шектеу қойылған элемент  пе екендігі тексеріледі?

 

МЫСАЛ: Шектеу қойып іздеу

program Poisk2a;

var  A:array[1..101] of integer;  

N,X,i:integer;

begin

read(N); {N<=100}

for i:=1 to N do read(A[i]);

read(X);

A[N+1]:=X; {қосымша элемент арқылы барьер орнату}

i:=1; {i:=0;}

while A[i]<>X do i:=i+1;

{repeat i:=i+1; until A[i]=X;}

if i<=N then write(X,' санының

A массивінің ',i,' орнына алғашқы енгізілуі')

else write('табылмады');

end.

 

 

program Poisk2b;

var  A:array[1..100] of integer;  

N,X,i,y:integer;

begin

read(N); {N<=100}

for i:=1 to N do read(A[i]);

read(X);

y:=A[N]; {соңғы элементті сақтау}

A[N]:=X; {қосымша элемент  арқылы барьер орнату} 

i:=1; {i:=0;}

while A[i]<>X do i:=i+1;

{repeat i:=i+1; until A[i]=X;}

if (i<N) or (y=X) then

write(X, ' санының A массивінің ' ,i, ' орнына соңғы енгізілуі')

else write('табылмады');

A[N]:=y; {массивтің соңғы элементін қайта қалпына келтіру}

end.

2.1.3 Екілік немесе қақ бөліп (бинарлы) іздеу

Екілік іздеу алгоритмін элментті массивке берілген қасиет бойынша ғана, яғни сол қасиеті бойынша реттелген кезде пайдалануымызға болады. Берілген мән бойынша санды іздеу кезінде массив өспелі немесе кемімелі түрде реттелген болуы керек. Мысалы, берілген қосында бойынша санды іздеуде массив цифры элементтер қосындысы цифры бойынша өспелі немесе кемімелі бағытта реттелген болуы қажет.

Алгоритмнің негізгі мақсаты массивті әрбір кезде дәл екіге бөліп қажет элементі бар бөлігін ғана қарастырады. Екіге бөлу массивтің бөлігінде іздейтін бір элемент қалғанға дейін жүргізіледі, содан соң осы қалған элементті іздеу шартымен тексеріледі.

Бұл алгоритмде екі түрлендіру бар, олар бірінші және соңғы еңгізулерді іздеу үшін. Барлығы орта элементтің қалай таңдалатындығына байланысты: аз немесе көп жағына дөңгелектеу. Бірінші жағдайда орта элемент массивтің сол жақ бөлігіне жатады, ал екіншісінде – оң жақ.

Екілік іздеу алгоритмі жұмыс жасағанда ізделінетін бөлік, мысалы әрбір айналымында екі есе азайып отырады. Бұл N ретті 2-негізді логарифмдік реттегі алгоритмдік күрделі есептеулермен қаматасыз етеді, мұнда N - массив элементтерінің саны.

 

МЫСАЛ: Өсу бағыты бойынша реттелген массивте Х санының алғашқы енгізілуін іздеу.

program Poisk3a;

var  A:array[1..100] of integer;  

N,X,left,right:integer;

begin

read(N); {N<=100}

write('өсу бағыты бойынша реттелген массивті енгізіңіз');

for i:=1 to N do read(A[i]);

read(X);

left:=1; right:=N;

{іздеу бөлігінің оң және теріс шекаралары}

while left<right do

begin

c:=(left + right) div 2;

{аз бағыты бойынша дөңгелектеген ортасы}

if X>A[c] then

{егер массив кемімелі түрде реттелген болса, онда if X<A[c]}

left:=c+1

{ортасын қоспай оң жақ бөлігін таңдаймыз, left ауыстыра отырып}

else right:=c;

{ ортасын қоспай сол жақ бөлігін таңдаймыз, right ауыстыра отырып}

end;

if X=A[left] then {мұнда left = right, бірақ үнемі = c емес}

write('A массивінің ',left,'жағына',X,'санының алғашқы енуі')

else write('табылмады');

end.

 

 

 

МЫСАЛ: Өсу бағыты бойынша реттелген массив элементері сандарының қосындысынан, Х-ке тең соңғы қосынды элементін іздеп, табу.

 

program Poisk3b;

var  A:array[1..100] of integer;  

N,X,left,right:integer;

{функция а саны цифрларының қосындысын есептейді, мұнда a – жеке белгісіз}

function Sum(a:integer):integer;

var  s:integer;

begin

s:=0; a:=abs(a);

while a>0 do

begin

s:=s + a mod 10;

a:=a div 10;

end;

Sum:=s;

end;

begin

read(N); {N<=100}

write('цифрларының қосындысы өспелі бағытта орналасқан массивті енгізіңіз');

{мысалы, N=4 : 122, -432, 88, 593}

for i:=1 to N do read(A[i]);

read(X);

left:=1; right:=N;

{іздеу бөлігінің сол және оң шекарасы}

 

while left<right do

begin

c:=(left+right+1) div 2;

{үлкен бөлігіне байланысты дөңгелектеген орта}

if X>=Sum(A[c]) then  left:=c

{left ауыстыра отырып, ортасын алмай оң жақ бөлігін таңдаймыз}

else right:=c-1;

{ right ауысттыра отырып, ортасын алмай сол жақ бөлігін таңдаймыз}

end;

if X=Sum(A[left]) then {мұнда left = right, бірақ үнемі= c емес}

write('соңғы сан цифрларының қосындысы=',X,'тең',A[left], ' А массивінің ',left,' жағында орналасқан')

else write('табылмады');

end.

2.2 Сұрыптау алгоритмі

Сұрыптаудың ең қарапайым есебіне массив элементтерін өспелі немесе кемімелі бағытта реттеу жатады. Есептердің бұдан басқа  түріне кейбір талаптарға сәйкес массив элементтерін реттестіру жатады. Көбінесе мұндай талаптарға массив элементі ретінде белгілі бір функция аргументтері алынады. Мұндай фугкцияны реттеуші функция деп атайды.

Сұрыптаудың әр түрлі әдістері бар. Осы әдістердің әрқайсысын N бүтін сандардан тұратын массивті өсу бағыты бойынша сұрыптау есебінің мысалдарында қарастырамыз.

 

2.2.1 Таңдау бойынша сұрыптау

Бұл әдістің негізгі маңызы ең үлкен массив элементін тауып, оны соңғы тұрған элемент орнымен ауыстыру (N нөмірімен). Содан соң, бірінші элемент пен соңғы элемент аралығындағы ең үлкен элемент ізделіп N-1 орынға қойылады, сол сияқты жалғаса береді. N-1 ең үлкен санын табу қажет. Кейде ең үлкен емес, ең кішісін тауып оны бірінші, екінші және тағы сол сияқты орындарға қойылады. Сонымен қатар бір мезгілде ең үлкені мен ең кішісін табу сияқты түрлендіру әдісін қолдануға болады. Бұл жағдайда ішкі цикл қадамдарының саны N div 2 болады.