Курстық жұмыс н тарму 11/1 53-2018

алғашқы сан жолдар санын, ал екінші сан бағаналар санын көрсетеді, а жиы мы 12 элементтен тұрады. Оларға бастапқы мəнді былай береміз:

int a[4][3]={

{0,1,2},

{6,7,8},

};

ішкі жүйелі жақшаларды қоймаса да болады:

Келесі түрде сипаттау жолдардың тек бірінші элементтерін ғана анықтайды, қалған элементтер 0-ге тең болып саналады:

int a[4][3]={ {0},{3},{6},{9} };

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

int a[4][3]={ 0,3,6,9 };

мұнда бірінші жолдың 3 элементі мен екінші жолдың бірінші элементі анықталады да, қалғандары 0 болып саналады.

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

1. матрицаның барлық элементтерін өңдейтін алгоритмдер.

2. матрицаның əр жолы немесе əр бағанасы элементтерін жеке-жеке өңдейтін алгоритмдер.

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

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

Кейбір кітаптарда бұл әдіс «экстраполяция әдісі» деп аталады. Экстарполяция – берілген интервалдан тыс бірнәрсені анықтау әдісі, ал интерпояция – сол интервал аралығына анықтау әдісі. Сондықтан да «экстраполяция әдісі» деп атау қате, үйткені ізделінетін сөзді шекарадан тыс аумақта іздеу мүмкін емес.бұл әдісті сипаттамас бұрын сізге ағылшын тіліндегі «treasure» сөзінің аудармасы қажет болды дейік. Яғни сіздің алдыңызда тапсырма – осы сөзді сөздіктен іздеу. Біздің келесі іс-әркеттеріміз қандай да бір іздеу алгоритмін құрумен жалғасады. Ізделінетін сөзді алфавит бойынша сұрыпталған массивтен іздейміз, ал керекті сөз бізге белгілі. Оны тез арада тауып алуға болады. Енді осы іздеуге толығымен тоқталайық. Бізге керекті сөз «т» әрпінен басталады, яғни алфавиттің екінші бөлігінде, немесе біз ол қандай орында тұрғанында шамамен есептеп ала аламыз. Яғни қанша дым жасауға болатынын анықтап аламыз. Егер ізделінетін массив үлкен болса осы әдіс арқылы оның шекрасын көрсетіп, тек осы аралықты ғана іздеуге болады. Ол үшін келесідей ек теңдік аламыз:

T1=M*N;

N – массивтегі элементтердің саны.

M – рет іздеуге болады.

Тура ауытырудың алгоритмі жасайтын операция саны M*N-ге тең. Ал сұрыптауға кететін уақыт N*Log(2)N-ге тең, оған тағы 2M*Log(2)N дихотомия әдісін қосамыз. T1=T2 кезінде екі алгоритм де тиімді шекарада боламыз.

Алдымен linearsearch (сызықты іздеу) деген шағын порграмма құрастырайық. Оның үш параметрі болады: Strings – жолдың өрнектер қптпры, newstring – жолдың өрнек, осыны іздеу қажет және size – қаралатын қатардың элемпенттер саны.

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

Сұрыпталған тізімде - екілік іздестіру жүргізуге болады. Нақты мəнді іздестіру үшін таңдау есебін қарастыруға болады. Мұнда белгілі бір шартты қанағаттандыратын элементті табу керек. Мысалы, бізге бесінші орындағы элементті, соңынан санағанда жетінші элементті немесе орта мəні болатын элементті табу керек болатын кездерді қарастырамыз. Бұдан былай біз берілген элементті ізделетін жиынды бектлген деп есептейміз.

Біз N элементтен тұратын жиын мынадай массив түрінде берілген деп есептейміз.

A: array [0..N-1] of item;

Əдетте item типі қандай да бір кілттік epiсі бар жазуды сипаттайды. Мақсат -кілттік өрісі берілген «іздестіру аргументіне» (x) тең элементті іздестіру болып табылады. Іздестіру нəтижесінде алынған I индексі мына шартты қанағаттандырады:

A[i].key=x;

Ол табылған элементтің басқа өрістеріне қатынауды қамтамасыз етеді . Бізді іздестіру процессі қызықтыратын болғандықтан біз item типі тек кілттен тұрады деп есептейміз.

1.3 Сызықтық және екілік іздеу әдістері

do

i:=i+1

end; (1)

Логикалық өрнектегі элементтердің реті маңызды болып табылады. Индексті өсірер алдындағы шарт мынадай түрде болады:

(0<=i
Бұл шарт I ден кіші барлық к- лардың мəндері үшін ізделген элемент болған жоқ дегенді білдіреді. Осыдан жəне іздестіру шарт жалған болғанда ғана аяқталатындығынан соңғы шартты аламыз:

((i=N) or(a[i]=x)) and (A[k]: 0<= k
Əрбір қадам сайын индексті өсіріп жəне логикалық өрнекті есептеу керек. Бұл жұмысты қысқартып, іздестіруді тездету үшін - күрделі шартқа эквивалентті қарапайым шартты тұжырымдау керек. Ол үшін массив соңына х мəні бар қосымша элементті орналастыру керек.

Мұндай элементті бөгет деп атайды. өйткені ол массив сыртына шығып кетпеуді қадағалайды. Енді массив былай сипатталады:

A:array [0..N] of integer; жəне бөгеті бар сызықтық іздестіру былайша болады:

A[N]=x; i=0; While a[i] =/x do i:=i+1 end; (4)

Қорытынды шарт:

(a[i]=x) and (a[k]: 0<=k
теңдігі ізделген элементтер болған жоқ екендігін көрсетеді .
Екілік іздестіру (қақ бөліп іздестіру)

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

A [k]: 1< =k
Негізгі идея - кез- келген элементті кездейсоқ таңдау, мысалы a[m] элементін жəне оны х- іздестіру аргументімен салыстыру. Егер ол х- ке тең болса, онда іздестіру аяқталады. Егер ол х-тен кіші болса, онда индекстері m - нен кіші элементтердің барлығын іздестіруден алып тастаймыз, егер ол х-тен үлкен болса, онда m -ге тең немесе m - нен үлкен элементтердің барлығын іздестіруден алып тастаймыз. Бұл бізді мынадай алгоритмге алып келеді (оны қақ бөле отырып іздестіру деп атайды).

Мұндағы l мен k индексті айнымалылары массивінің сəйкес сол жəне оң жақ бөлігінің шетін береді, сол аралықта ізделген элемент жатуы мүмкін:

L:=0;

k:=N-1;

found:=false;

While (l<=k) and found do

M:= l жəне k аралығындағы кез келген мəн.

if a[m]=x then

found:=true else

if a[m]
l:=m+1 (6) else k:=m-1

end;

еnd.

əрбір қадам алдында орындалатын шарт мынадай:

(l<=k) and (a[k]: 0<=kx)

бұдан мынадай нəтиже шығады:

found or ((l>k) and (a[k]:0<=k x))

Бұдан шығатыны:

(a[m]=x) or (a[k]: 0<=k
m - ді таңдау кездейсоқ, бірақ m алгоритм тиімділігіне əсер етеді. Біздің мақсатымыз - əрбір қадамда келесі іздестіруден көбірек элементті алып тастау; нəтижесінде максималды салыстырулар саны logN. Бұл алгоритмді тездетуге болады, егер:

(a[k]: 0<=k
Іздестіру екі бөлікте массивті түгел қарап болғанша жүреді :

L : =0; k:=N;

(div-бүтін санды бүтін санға бөлген -While l
If a[m]
L:=m+1 else

k:=m end;

End;  

ТӘЖІРИБЕЛІК БӨЛІМ

2.1 Бағдарламалаудың алгоритмін құру
Массивтерде екілік (екілік) іздеу

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

Псевдокодта массивтерде екілік іздеу алгоритмі қалай жұмыс істейді?:

жүктеу/скачать 395,5 Kb.

Достарыңызбен бөлісу: