Э. А. Абдыкеримова информатиканың теориялық негіздері
Массив элементтерін сұрыптау
жүктеу/скачать 476,55 Kb.
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
- Бұл бет үшін навигация:
- Тікелей қосу көмегімен сұрыптау
- Тікелей таңдау кӛмегімен сҧрыптау әдісі
- Рекурсивті алгоритмдер
Массив элементтерін сұрыптауМассив элементтерін сҧрыптауда қойылатын негізгі шарт: массив элементтерін сҧрыптаудың таңдалған әдісі жадыны тиімді пайдалануда болып табылады. Тікелей қосу көмегімен сұрыптауБҧл әдіс карта ойынында кеңінен пайдаланылады. Элементтер ойша a1,…,aі-1 «дайын» тізбек және aі,…,an алғашқы тізбек болып бӛлінеді. Әрбір қадамда і=2 бастап, і-дің мәнін 1-ге арттыра отырып, алғашқы тізбектен і-ші элемент шығарылып тасталынады да, дайын тізбекке барып орналасады. Сӛйтіп, ол жаңа орынға қойылады. Сегіз кездейсоқ таңдалынған сандарды тікелей жалғау кӛмегімен сҧрыптаудың мысалы тӛмендегідей:
Бҧл сҧрыптаудың алгоритмі тӛмендегідей: For і:=2 To n Do X:=a[і]; {x-ті a[1],…,a[і] арасындағы сәйкес орынға қою} End; Шынайы іздеу процесінде тізбектегі салыстырулар мен жылжуды алмастыра отырып, електен ӛткізу болып табылады. Х кезекті aj элементімен салыстырылады, одан кейін х не бос орынға қойылады, не aj оңға қарай жылжиды, ал процесс солға қарай жҥреді. Електен ӛткізу процесі тӛмендегі шарттардың бірі орындалғанда аяқталады: х-тің кілтінен кіші кілтті aj элементі табылған жағдайда; тізбектің сол жақ шетіне жеткен жағдайда. Сонымен, бҧл алгоритм фрагменті тӛмендегідей: … For і:=2 to n do begіn X:=a[і];a[0]:=x; j:=І; Whіle x … Мҧндай алгоритм орнықты сҧрыптау процесін сипаттайды: кілттері бірдей элементтер реті ӛзгеріссіз қалады. Тікелей жалғау алгоритмін оңай жетілдіруге болады: дайын тізбекке жаңа элемент қойылғаннан кейін ӛзі реттеледі. Ал, екілік іздеуде салыстыру дайын тізбектің ортасынан басталады, одан кейін қақ бӛлу процесі жалғау нҥктесі табылғанша жалғаса береді. Мҧндай тҥрлендірілген сҧрыптау алгоритмі екілік жалғау әдісі деп аталады. Тікелей таңдау кӛмегімен сҧрыптау әдісіБҧл әдіс тӛмендегідей принцитпке негізделген: Кілті кіші элемент таңдалады; ол бірінші элемент а1-мен алмастырылады; осы процес қалған n-1 элементпен, n-2 элементпен және т.с.с. қайталанып, бір ең ҥлкен элемент қалғанша жалғаса береді. Бҧл әдіспен жҧмыс істеу процесі алдыңғы мысалдағы 8 кілтпен жҥргізіледі.(2.2-сурет).
Оның алгоритмі тӛмендегідей: For і:=1 to n-1 do a[і]..a[n] аралығынан ең кіші индексті к-ға меншіктеу; a[і] мен a[к]-ны орындарымен алмастыру; End; Мҧндай әдіс тікелей таңдау деп аталады, бҧл әдіс қандай да бір мағынада тікелей жалғауға қарама-қарсы. Тікелей жалғауда әрбір қадамда алғашқы тізбектің тек бір ғана элементі, ал дайын тізбектің қосу нҥктесі ізделінетін барлық элементі қарастырылады. Ал, тікелей таңдауда ең кіші кілтті бір элементті іздеу ҥшін алғашқы тізбектің барлық элементтері қарастырылып, табылған элемент кезекті элемент ретінде дайын тізбекке орналасады. «Тікелей таңдау» әдісімен сҧрыптау алгоритмі тӛмендегідей. Program suruptau2; Uses crt; var c:array[1..100] of word; і,j,n,r,k:іnteger; Begіn wrіte('n='); {массивтің ӛлшемін енгізу} readln(n); {массивті толтыру} Randomіze; for і:=1 to n do c[і]:=random(100); for і:=1 to n do {алғашқы массивті шығару} wrіteln('c[',і,']=',c[і],' '); {массив элементтерін сҧрыптау} for і:=1 to n-1 do begіn k:=і; r:=c[і]; {массив элементтерінің қалған бӛлігінен ең кіші элементін іздеу} for j:=і+1 to n do іf c[j] r:=c[j]; end; c[k]:=c[і]; c[і]:=r; end; {сҧрыпталған массив элементтерін шығару} wrіteln('suruptalgan massіv'); for і:=1 to n do wrіteln('c[',і,']=',c[і]); repeat untіl keypressed; end. Рекурсивті алгоритмдерРекурсия – ішкі программаны оның ӛз ішінде тҧрып шақыру. Паскаль тілінде рекурсияны қолдануға рҧқсат етілген. Рекурсиялық алгоритм, қойылуының ӛзі рекурсиялық сипатта болатын кейбір математикалық есептерді шешкенде ӛте тиімді. Бҧл жағдайда есеп кіші ӛлшемді шағын есептер жиынтығына бӛлінеді. Классикалық мысал - N>0 және 0!=1!=1 шарттары ҥшін N!=N*(N-1)! факториалын есептеу. Мҧнда N ӛлшемді бастапқы есеп N кӛбейтінді мен N-1 шағын есебін шешуге бӛлінген. Рекурсиялық алгоритм қҧру ҥш этапты қамтиды: Есепті параметрлеу; Тривиалдық жағдай іздеу және оны шешу; Жалпы жағдайды бейнелеу. Ішкі программа әрбір орындалған сайын оның жергілікті айнымалылары мен ішкі программадан қайту адресі жадының арнайы облысы – стекте сақталады. Ішкі программа аяқталып, одан шығу кезінде жадының бҧл бӛлігі босайды. Рекурсиялық шақыру кезінде локалдық жады босамайды, "қысқы ҧйқыға" кетеді, стекте жергілікті айнымалылардың жаңа мәндеріне жаңа облыс және жаңа қайту адресі бӛлінеді. Стекке қатынас жасау "соңынан келу – бірінші кету" (Last Іnput, Fіrst Output - LІFO) қағидасы бойынша жҥреді, сондықтан ішкі программадан шығу кезінде қайту нҥктесі – соңғы шақыру нҥктесі болады. Яғни стекті ҧйымдастыру рекурсияның жҥзеге асырылуын қамтамасыз етеді. Рекурсия – жанама болуы мҥмкін: A ішкі программасы B ішкі программасын, ал ол ӛз кезегінде A ішкі программасын шақырады. Ал бҧл Паскальдың қатаң типтендірілген - ішкі программа оған сілтеме жасалмас бҧрын сипатталуы тиіс деген принципін бҧзады. Бҧл жағдайда тӛменде анықталған ішкі программа тақырыбын алғашқы ішкі программадан жоғары шығару керек, ал ішкі программа денесінің орнына тақырыптан кейін forward қызметші сӛзін кӛрсетеді; (нҥктелі ҥтір - міндетті). Рекурсия деп ӛзін ӛзі анықтайтын немесе қҧрайтын объект. Рекурсия тек қана математика да ғана емес, кҥнделікті ӛмірде де жиі кездеседі. Рекурсия анықтамасы математикада ӛте ҥлкен қуатты аппарат. Бірнеше мысалдарға тоқталайық. Натурал сан, ағаш және анықталған функция. Натурал сан: а) 0 натурал сан, б) натурал саннан кейінгі сан да натурал. Ағаш: а) 0 ағаш (оны "бос ағаш " деп атайды), б) егер t1 және t2 — ағаш болса, онда оның тӛбесін қҧрайтын екі тӛменгі орналасқан ағашта ағаш болады 3 "факториал" п! функциясы (теріс емес бҥтін сан): а) 0! = 1, б) п >0: п ! = п *(п- 1)! Рекурсивті алгоритмнің артықшылығы ақырғы тҧжырым кӛмегімен объектілердің шексіз жиынын анықтауға кӛмектеседі. Сәйкесінше соңғы рекурсивтік программа кӛмегімен шексіз есептеулер жҥргізуге болады және программада бірдей қайталаулар кездеспейді. Алайда рекурсивті алгоритмдерді негізінен шығарылатын есепте, есептелетін функцияда немесе ӛңделетін берілгендер қҧрылымында нақты анықталған рекурсия бар болса. Жалпы жағдайда Р рекурсивті программасын S операторлар жиынынан (Р-ны қамтымайтын) және Р-ның ӛзінен тҧратын қандай да бір Р композициясы ретінде ӛрнектеуге болады: P=P[S,Р]. Рекурсивті программаларды ӛрнектеу ҥшін процедура немесе ішкі программа ҧғымын білу қажетті және жеткілікті, себебі олар кез-келген операторға оған қатынайтын ат қоюға мҥмкіндік туғызады. Егер қандай да бір Р процедурасы ӛз ӛзіне нақты сілтеме жасаса, онда оны тура рекурсия деп аталады, егер Р процедурасы Р-ға тура немесе жанама сілтеме жасайтын басқа Q процедурасына сілтеме жасаса, онда Р жанама рекурсия деп аталады. Сондықтан программа мәтіні бойынша рекурсиялық әрқашан айқын кӛрінбейді. Негізінен, прохедтрамен сек оры прохедтрада анықсалған және одан сыр жерде мағынары болмайсын локальді объексілер жиыны, эғни айнымалылар, конрсансалар, сипсер және прохедтралар жиыны байланырсырылады. Ондай прохедтралардың әрбір ректрривсі орындалты кезінде байланырқан локальді айнымалылардың жаңа жиыны құрылады. жүктеу/скачать 476,55 Kb. Достарыңызбен бөлісу:
|