Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






While, Do . while цикл операторы






Орындалу саны алдын ала белгісіз болатын циклдер қ ұ ру кезінде шарттары алдын ала немесе соң ынан тексерілетін екі цикл тү рі бар. Оның жазылуы:

while (шарт-ө рнек)

оператор;

Мұ нда шарт ретінде шартты ө рнек немесе кез келген типтегі ө рнек пайдаланылуы мү мкін. Оператор қ арапайым немесе қ ұ рама болуы мү мкін. Ол қ ұ рама оператор болса, онда операторлар жиыны жү йелі жақ шағ а алынып жазылады. While операторы орындалғ анда, алдымен жақ ша ішіндегі ө рнек есептеліп тексеріледі. Егер ө рнек мә ні ақ иқ ат болса немесе жалпы жағ дайда 0-ге тең болмаса, онда оператор атқ арылады. Содан соң жақ шадағ ы ө рнек тағ ы да есептеледі. Егер ө рнек мә ні жалғ ан болса (немесе жалпы жағ дайда 0-ге тең болса), онда while цикл операторы ө з жұ мысын аяқ тайды.

Do... while цикл операторы

Шарты соң ынан тексерілетін do … while циклінің оператордың жалпы жазылу тү рі:

Do

{

Оператор;

Оператор;

… … …

n-оператор;

}

while (ө рнек);

Цикл тұ лғ асы ретінде қ арапайым немесе қ ұ рама оператор қ олданылуы мү мкін. Жақ шадағ ы ө рнек цикл тұ лғ асынан кейін тексеріледі. Сондық тан do while цикл тұ лғ асы ең болмағ анда бір рет орындалады. Цикл тұ лғ асынан кейін жазылғ ан ө рнек ақ иқ ат болса (немесе жалғ ан жағ дайда ол 0-ге тең болмаса), цикл тұ лғ асы қ айтадан орындалады. Ал ө рнек жалғ ан болса (немесе 0-ге тең болса), цикл аяқ талады.

#include < iostream.h>

int main()

{inti;

intsum = 0;

for (i = 1; i< = 1000; i++)

{ sum = sum + i; } cout< < " Сумма чисел от 1 до 1000 = " < < sum< < endl; }

Функция. Оның программада қ олдану ерекшеліктері. Функцияны сипаттау жә не анық тау. Прототип. Рекурсия. Рекурсия механизмі. Рекурсивтік функция. Оны қ олданудың артық шылығ ы.

Функцияны сипаттау (Описание функции; function declaration) — міндетгі анық тайтын жоғ ары дең гейдегі программалау тілінің конструкциясы. Функцияғ а атау беруге (егер қ ажет болса), оның формальдық параметрлерін кө рсетуге жә не алгоритмнің жү зеге асырылатын міндетін анық тауғ а қ ызмет етеді. Функцияны сипаттау программадағ ы сипаттамалар бө лімінде (мысалы, Паскальда) немесе программалық модуль тү рінде ә зірленген бас программадан (мысалы, Фортранда) кейін орналасады. Функцияны сипаттау формасы нақ тылы тілдің синтаксисімен тағ айындалады. Ә детте, Функциялық сипаттау денесі мен функцияның бас тақ ырыбынан тұ рады. Тақ ырыпта функцияның атауы кө рсетіледі жә не формальдық параметрлері кө рсетілуі мү мкін. Ал міндеттің денесінде орындалатын алгоритм міндеттері программаланады.

Рекурсивті алгоритм қ аншалық ты тиімді? Оның тиімділігін есептей аламыз ба, егер тікелей есептеу алгоритмі квадратты, кіру мә ліметтерінің бө ліктеуі логарифмді, барлық шешімдердің бірігуі сызық ты (кіру мә ліметтерінің мө лшеріне байланысты), ал ә рқ айсысының мө лшері бастапқ ының тө рттен біріне тең болатын барлық кіру мә ліметтері 8 бө лікке бө лінетінін білетін болсақ? Бұ л есепті шеші оң ай емес, оғ ан қ алай кірісу керек екендігі де тү сініксіз. Дегенмен, «бө л де басқ ар» тү ріндегі алгоритмдерді талдау оң ай екені анық талды, егер сіздің алгоритмің іздің қ адамдары жоғ арыда келтірілген жалпы тү рдегі алгоритмнің қ адамдарына сә йкес қ ойылса: тура есептеу, кіруді бө лу, бірнеше рекурсивті шақ ырулар саны жә не алынғ ан шешімдердің біріктірілуі. Егер осы қ адамдар бір-бірімен қ алайша біріктірілетінін жә не ә р қ адамның кү рделілігін білетін болсақ, онда «бө л де басқ ар» тү ріндегі алгоритм кү рделілігін анық тау ү шін келесі формуланы қ олдануғ а болады:

мұ ндағ ы DAC — DivideAndConquer алгоритмінің кү рделілігі,

DIR — Direct Solution алгоритмінің кү рделілігі,

DIV — Divide Input алгоритмінің кү рделілігі,

COM — CombineSolutions алгоритмінің кү рделілігі.

Осы жалпы формула арқ ылы алдындағ ы абзац басында қ ойылғ ан сұ рақ ө те қ арапайым болып қ алады. Тек ә р бө ліктің белгілі кү рделіліктерін формулағ а қ ойсақ болғ аны. Нә тижесінде:

немесе кіші жиындар шамасы бірдей болғ андық тан, одан да оң ай формула:

Мұ ндай тү рдегі тең діктер рекурренті деп аталады, ө йткені функция мә ні ө з терминдері арқ ылы беріледі. Сол функцияның басқ а шақ ыруларынан тә уелсіз, тек N-нан тә уелді болатын кү рделілік ү шін ө рнекті тапқ ымыз келеді.

Факториал мысалына қ айтып оралсақ. Факториалды есептеу алгоритмінің барлық кезең дерін жалпы DivideAndConquer алгоритмімен сә йкес қ оялық. Енді осы сә йкестікті пайдаланып, жоғ арыда келтірілген жалпы формулағ а қ ою керек мә ндерді анық таймыз. Factorial функциясындағ ы тура есептеулер ешқ андай ә рекеттерді қ ажет етпейді, кіру мә ліметтерін бө лу жә не нә тижелерді біріктіру алгоритмінің ә рқ айсысы тек бір ә рекетті қ ажет етеді, ал рекурсивті шақ ыру бастапқ ы мө лшерден 1-ге кем болатын тек бір есепті шығ арады. Нә тижесінде Factorial функциясын есептеу санына келесі рекурентті қ атынасты аламыз:

8. Массивтерді сұ рыптау алгоритмдері.Таң дау ә дісі. Массивте екілік іздеу. Орын алмастыру ә дісі. Орнына қ ою ә дісі (метод вставок). Айырмашылық тары.

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

Қ арапайым таң даумен сұ рыптау ә дісі қ арапайым ә дістердің ішіндегі ең жақ сысы, алмасумен сұ рыптау – ең жаманы, ал жылдам сұ рыптау ең тезі жә не ең жақ сысы болып табылады.

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

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

Кө піршікті ә діс алгоритмі тізім бойынша бірнеше рет ө теді. Ә рбір ө ткенде кө рші элементтерді салыстырады. Егер кө рші элементтердің тізімі дұ рыс емес болса, онда олар орын ауыстырады. Ә рбір тә сіл тізім басынан басталады. Алдымен бірінші мен екінші элементтер, сосын екінші мен ү шінші, содан кейін ү шінші мен тө ртінші жә не т.с.с.; жұ пта ретсіз тұ рғ ан элементтердің орны ауыстырылады. Тізімнің ең ү лкен элементін бірінші ө ткенде тапқ ан кезде ол тізімнің соң ына жеткенге дейін барлық кезекті элементтермен орын ауыстыра береді. Сондық тан екінші рет ө ткенде соң ғ ы элементпен салыстыру қ ажет емес. Екінші рет ө ткенде тізімнің екінші элементі соң ғ ы позициядан бастап екіншіге тү седі. Процесті жалғ астыра берсек ә рбір ө ткен сайын ең болмағ анда кезекті бір элемент ө зінің орнында қ алады. Бұ л кезде ең кіші мә ндер жоғ ары қ арай жиналады. Егер қ андай да бір ө ткен кезде ешқ андай элементтердің орны ауыспаса, онда олардың барлығ ы қ ажетті ретпен тұ р, жә не алгоритмнің орындалуын тоқ татуғ а болады. Ә рбір ө ткенде бірден бірнеше элемент ө зінің орнына жақ ындай тү седі, тек біреуі ғ ана нақ ты орнында келеді.

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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.