«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері»



бет6/8
Дата05.06.2017
өлшемі1,51 Mb.
#18191
1   2   3   4   5   6   7   8

Көршілестік матрицасы

Көршілестік матрицасы дегеніміз - өлшемі nМ болатын және егер i-ші төбесі j-ші төбесімен көршілес болса мәні бірге тең болатын, әйтпесе 0-ге тең болатын матрица.

Бағытталмаған графтар үшін х, у қабырғасы у,х қабырғасына тең болады. Сондықтан олар үшін көршілестік матрицасы әрқашан симметриялы. Оларда алдыңғы граф үшін матрица мынадай:

1 2 4 5

3 6


Бағытталмаған граф үшін көршілестік матрица:

2 4


1 6

5

3 5



Көршілес матрица симметриялы болып табылады, сондықтан ЭЕМ-ға енгізіп, өңдеуге қолайлы.


3 Зертханалық сабақтар

Зертханалық жұмыс №1

Тақырыбы: Сызықты байланысқан мәліметтер құрылымдарын ұйымдастыру және олармен жүргізілетін амалдар.


Жалпы мәлімет

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



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

Есепті шешу этаптары:

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

  2. Программаның паскальда жазылуы:

  3. program маs_1;

var

V: array[1..100,1..100] of integer;

m,n, i,j, c: integer;

flag: boolean;

begin

<массив өлшемін енгізу m*n>

<массив ұяшықтарын толтыру>

for i:=1 to m do

repeat

flag:= true;

for j:=1 to n-1 do

if (v[i,j]=0) and (v[i,j+1]<>0) then begin



<олардың орынын ауыстыру>

flag:= false;

end;

until flag;



<массивты басып шығару>

readln;



end.
4. Алгоритмнің блок-схемасы


Бірінші жолды реттейміз:




Блок-схеманың алгоритмы бүтіндей:




5. Паскальдағы программа:

program mas_1;

var


V:array[1..100,1..100] of integer;

m,n, i,j, c: integer;

flag: boolean;

begin


write('Массив өлшемін енгіз m-n> '); readln(m,n);

for i:= 1 to m do

for j:= 1 to n do begin

write('V[',i,',',j,']= '); readln(V[i,j]);

end;

for i:=1 to m do



repeat

flag:= true;

for j:=1 to n-1 do

if (v[i,j]=0) and (v[i,j+1]<>0) then begin

c:=v[i,j]; v[i,j]:=v[i,j+1]; v[i,j+1]:=c;

flag:= false;

end;

until flag;



for i:= 1 to m do begin

for j:= 1 to n do write(V[i,j]:2);

writeln

end;


readln;

end.


Бақылау сұрақтары:


  1. Массив типті айнымалылар қалай анықталады?

  2. Бір өлшемді, екі өлщемді массивтің жекелеген элементіне кіру қалай жүзеге асырылады?

  3. Массивтың элементтері экранға қалай шығарылады?

  4. Екі өлшемді массивты экранға матрица түрінде шығаратын программа фрагментін келтір.

  5. X : Array[0..1, 0..1, 0..1, 0..1, 0..1, 0..1] of Integer алты өлшемді массивына неше сан жазуға болады?



Тапсырмалар:

  1. а1,а2,а3 бұтін сандары берілген. Бүтін санды [bij]i,j=1,2,3 матрицасын алу керек, мұнда bij=ai-3aj.

  2. [aij]i=1,…10; j=1,…12 – бүтін санды матрицасын алу керек, aij=i+2j.

  3. N өлшемді квадрат матрица берілген. Бас диагональдан жоғары, төмен орналасқан нольдік элементтер санын тап.

  4. n * m өлшемді матрица берілген. b векторын алу керек, онда элементтер былай есептеледі: - сәйкес жолдардың элементтерінің көбейтіндісі; - сәйкес бағандардың арифметикалық ортасы; сәйкес жолдардың ең үлкен және ең кіші элементтерінің айырмасы; - бағандағы алғашқы теріс элементтердің мәндері.

  5. A[1..m,1..n] екі өлшемді массив берілген. Элементтері тең болатын B[1..m] бір өлшемді массивын жасау: - жолдардың элементтер қосындысына; - жолдардың элементтер көбейтіндісіне; - жолдардың элементтерінің арифметикалық орталарынына.

  6. Берілген массивте жұп орында тұрған элементтерді тақ орында тұрған элементермен орынын ауыстыру.

  7. Берілген массивтің элементтерін кері ретпен орналастыр (бірінші элементті соңғымен, екіншісін оның алдыңғысымен, т.с.с., егер, массив элементтерінің саны тақ болса, ортаңғысы өзгеріссіз қалады).


Зертханалық жұмыс №2

Тақырыбы:Ағаш типті мәліметтер құрылымдарын ұйымдастыру.


Жалпы мәлімет

Тармақ дегеніміз – иеархиялық құрылым құратын элементтер мен қатынастардың жиынтығы.

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



0-деңгей 1-деңгей 2-деңгей 3-деңгей

Мұнда ағаштың түбірі дегеніміз – ары қарай түбірі болмайтын төбесі, яғни мұндағы А. Әрбір тармақтың бір ғана түбірі болады. Тармақтың ең төменгі түйіндері E, F, G, H жапырақ деп аталады. Егер тармақтың элементі жапырақ болмаса, онда оны тармақтың ішкі түйіні немесе төбесі деп аталады. Бос тармақ дегеніміз – ешқандай төбесі жоқ тармақты атаймыз. Балалық төбесі деп – тармақта орналасқан өзінің ата-аналық төбесінен төмен қарай тұрған және онымен тікелей байланысқан төбені атаймыз. Мысалға, егер i төбесі F төбесіне қатысты балалық төбесі болса, онда F төбесі I төбесіне қатысты ата-аналық төбе деп аталады.

Балалық түйіндер және олардың балалық түйіндері ұрпақ деп аталады. Мысалға, E, F және I, J B – түйінінің ұрпақтары.

Тектері бұл түйіннің ата-аналары немесе ата-әжелері.

Тармақтың әрбір түйіні осы түйіннен және барлық ұрпақтарынан тұратын бұтақтың түбірі болып табылады. Мысалы, В төбесі E,F,I,J деңгейінің түйіні. Мысалға, F түйіні F,I,J түйіндерінен тұратын бұтақтың түбірі болып табылады. G түйіні ұрпақсыз бұтақтың түйіні. А түйіні өзі тармақ болып табылатын бұтақтың түбірі.

Кез келген түйіннен түйіннен бастап оның ұрпақтарына қарай жүру белгілі бір жол бойымен жүзеге асады. Мысалға, А түбірінен бастап F түйініне дейінгі жол A,B,F төбелерінен өтеді. Кез келген түйіннен оның ұрпақтарына баратын жол жалғыз ғана болады. Түйіннің деңгейі дегеніміз – ол түбірден осы осы түйінге дейінгі жолдың ұзындығы. Мысалға, А түбірінің деңгейі 0-ға тең. Түбірдің әрбір баласының деңгейі 1-ге тең. Мысалға F түйіні 2 деңгейдегі ұзындығы 2-ге тең түйін болып табылады.

Тармақтың тереңдігі дегеніміз – оның кез келген түйінінің максимальды деңгейі немесе тармақтың тереңдігі дегеніміз ол түбірден бастап түйінге дейінгі ең ұзақ жолдың ұзындығы.
Тармақ тәрізді құрылымды беру әдістері

Тармақтарды берудің 4 түрлі әдісі бар:



  1. графтар

  2. кірістірілген жақшалар

  3. кірістірілген жиындар

  4. кесінді тізбектер.


1. Графтар. Бәрі А түйінінен тарайды


2. Кірістірілген жақшалар:
(A(B(E,F(I,J)), C(G),D(H)))


  1. Кірістірілген жиындар.



4. Кесінді тізбек.
A B E I

F J


C G

D H


Көбінесе тармақтарды бейнелеу үшін графтар қолданылады.
Тапсырмалар: Реттелген екілік тармақ жасап, оны экранға шығаратын бағдарлама құру керек.
Зертханалық жұмыс №3

Тақырыбы: Граф типті мәліметтер құрылымдарын ұйымдастыру.
Жалпы мәлімет

Граф дегеніміз – G= жұбы. Мұндағы V-төбелердің құр емес жиыны. E - қабырғалар жиыны. Яғни, төбелер жұбы немесе қабырғалары жиыны деп аталатын мәліметтер элементтері жиынынан тұрады. Төбелер қалаларды көрсететін болса, қабырғалар арасындағы жолдарды көрсетеді.

1250 900

450
Егер е жұптары реттелмеген болса, яғни жолдардағы қозғалыс екі бағытта да жүретін болса, онда граф бағдарланбаған әйтпесе бағдарланған деп аталады. Егер қабырғалардың бір бөлігі бағытталған немесе бағдарланған болса, мұндай графтар аралас графтар деп аталады.

V1, V2, ..., Vn төбелерінің тізімі жол деп аталады. Мұндағы барлық i үшін 1<=i<=n, Vi,Vi+1 қабырғалары болады.

Бағдарланған графта V1, V2, ..., Vn төбелердің тізімі.

V1V2, V2 V3,...,Vn-1 Vn бағытталған доға түрінде болады. Графтардағы жол қарапайым деп аталады, егер графтардың төбелері әртүрлі болса. Жолдың ұзындығы осы жолды құрайтын қабырғалардың санына тең болса.

Vi және Vj төбелері байланған деп аталады егер, осы төбелер үшін Vi+1,Vi+2,.., Vj жолы бар болса. Граф байланысшы граф деп аталады егер, оның кез келген төбелер жұптары үшін оларды қосатын қарапайым жол болса.

Цикл дегеніміз - ұзындығы бірден кем болмайтын бір төбеден басталып сол төбеден аяқталатын қарапайым жол.

Графтардағы тармақ дегеніміз – бұл циклсыз графтар. Графтар өлшенген деп аталады егер, графтың әрбір қабырғасына мәні немесе салмағы жазылса.

Мысалға, салмақ ретінде қалалардың арасындағы арақашықтық немесе қандай да бір жұмыстың жүргізілу уақыты алынады.

Графтарды берудің келесідей әдістері бар:


  1. Инцидиенттік матрицасы.

  2. Көршілестік матрицасы.

  3. Салмақтық матрицасы.

  4. Қабырғалар тізімі.

  5. Көршілестік тізімі.

Қандай да бір нақтылы есепті шығару үшін қолдану қолайлылығына қарай осы әдістердің кез келгенін пайдалануға болады.



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




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

    Басты бет