Рекурсия. Рекурсивті алгоритмдер

Й тапсырмалары №1

  1. «Программаны сапасы тсінігі – тиімділігі жне німділігі. Программалау тілдеріні жіктемесі. Программалау ортасы, программаны тесттілеу принциптері, тзету ралдары» таырыбыптарына конспектіні толытырып жазу.
  2. Сызыты алгоритмдерді программалауа арналан тапсырмалар: Апаратты Мб лшем бірлігінде берілген клемін Гб-а айналдыру программасын рыыз.
  3. ASCII кодында терілген текстті символдар саны берілген. Апаратты ДК жадысынан алатын клемін килобайтпен анытаыз.

Й тапсырмалары №2

Сызыты жне тадау алгоритмдерін программалауа арналан тапсырмалар:

  1. Тарматалу жне тадау алгоритмдеріне з бетіізше бір-бір мысал келтірііз.
  2. «DOS, SYSTEM стандарты кітапханалары» таырыбында конспект жазу.
  3. ДК жйесіндегі аымды уаыт, аымды мерзімдерді мндерін программада олдануа мысал келтірііз. Программасын экранда ялы телефонны экранын кескіндеп, соны экранында алауыызша орналастырып, демонстрациялаыз.

Й тапсырмалары №3

  1. « Стандартты кітапхана: CRT рамындаы клавиатура мен экранды басару ралдары» конспект жазу.
  2. Циклдарды йымдастыру таырыбына тапсырмалар:

Есеп 1. N натурал саны берілген. осындысын есептеу блок-схемасы рыыз

 

;

 

Есеп 2. а наты саны, n натурал саны берілген.

.

Кбейтіндісін есептеу алгоритмін жазыыз.

Есеп 3.х наты саны, n натурал саны берілген. Есептеіз:

;

Й тапсырмалары №4

  1. «Іштестірілген циклдар» таырыбында іздену.
  2. Іштестірілген циклдара мысалдар келтірііз.

Й тапсырмалары №5

Таырыбы: Бір лшемді массивтер.

1. Студентті 8-ші семестрдегі 5 трлі пн бойынша алан баалары берілген. Студенті лгерімін анытайтын программа жазыыз.

2. Бір лшемді массивті та нмерлі элементтеріні жп мнділеріні санын анытау программасын жазыыз.

Й тапсырмалары №6

Таырыбы: Екі лшемді массивтер.

3. Студенттерді 2-ші семестрдегі 7 трлі пн бойынша алан баалары берілген. Студенттерді лгерімін анытайтын программа жазыыз.

4. Екі лшемді квадрат массив берілген. Оны бас диогоналыны элементтеріні осындысын экрана шыаратын программа жазыыз.

Й тапсырмалары №7

Таырыбы: Срыптау жне іздеу алгоритмдері

  1. Берілген бір лшемді массивті кпіршікті срыптау дісімен су ретімен срыптаыз.
  2. Екі лшемді массивтегі соы теріс элементін іздеу алгоритмін рыыз.
  3. Оытушы анытаан срыптау жне іздеу дісі бойынша конспект жасау жне ОСЖ-де талдау.

 

Й тапсырмалары №8

Таырыбы: Жолды типті мліметтерді деу.

1. Бір жабылатын жне бір ашылатын жашалары бар литерлер тізбегі берілген. Экрана осы жашаларды ішіндегі литерлерді шыару.

2. Нктелі тір(;)литерімен блінген сздер тізбегі берілген. Тізбек ос нктемен (:) аяталады. 'a' ріпімен аяталатын анша сзді бар екендігін анытау.

 

Й тапсырмалары №9

Таырыбы: Жиынды типті мліметтерді деу.

1. Бір жабылатын жне бір ашылатын жашалары бар литерлер тізбегі берілген. Экрана осы жашаларды ішіндегі литерлердден тратын жиын рып, жиынды экрана шыару.

2. Клавиатурадан енгізілген сандарды екіге еселілерін бір жиына, жай санждарын келесі жиына топтастырыыз. ай жиында элементтеріні кп екендігін сипаттаыз.

Й тапсырмалары №10

Таырыбы: Ішкі программалар

1. Сыныптаы рбір оушыны бойы мен салмаы белгілі. райсысыны салмаы бойынан аншалыты ауытитынын, яни аншаа арты не кем екенін анытаыз.

2. Екі блшекті осу керек. Е лкен орта блгішін табуды функция трінде жаз.

3. Автопаркте белгілі госномерлі 5 машина жмыс жасайды. рбір жргізуші кнде тскен табысты автошаруашылыа тапсырады. Бір аптадаы кнделікті тсіп отыран табыс млшері белгілі. ай машина осы аптада е кп табыс тсіргенін анытаыз.

Й тапсырмалары №11

Таырыбы:Рекурсивті алгоритмдер.

1. «Рекурсия тсінігі. Рекурсия трлері. Рекурсивті алгоритмдерді ке тараан трлері» таырыбында конспект жазу.

2. Шахмат татасындаы атты жрісін тексеруге арналан рекурсивті алгоритм рыыз.

Й тапсырмалары №12

Таырыбы: Жазбаларды деу.

1. Информатикадан олимпиадаа атысан студенттерді мліметтері белгілі. 30 баллдан жоары алан студенттерді тізімін шыару.

2. Кітапхананы оырмандары туралы мліметтер белгілі: фамилиясы, мекен-жайы, жмыс орны, кітапты алан уаыты, кітапты тапсыру уаыты. Кітапханаа арыз оырмандарды фамилиясын, мекен-жайын жне жмыс орнын крсету.

3. Тіс дрігеріне келушілерді тізімінен фамилиясыны бас рпі "Б"-дан "Л"-а дейінгі аралыта жатан адамдарды жасы мен диагнозын шыару программасын рыыз.

Й тапсырмалары №13

  1. «Типтелмеген файлдарды ру жне олдану тсілдері, ралдары» таырыбында конспект жасау.
  2. Бір тексттік файлдаы мліметтерден екі тексттік файл рыыз. Та жне жп нмірлі жолдарды бліп жазыыз.
  3. Бтін сандар файлын рып, файлдаы та сандарды осындысын, жп сандарды санын анытаыз.

Й тапсырмалары №14

1.«Модулдер. Модулдік программалау принциптері» таырыбында тереірек іздену.

2.Модулдерді компиляциялау жне пайдалану принциптерін сатай отырып ру мысалдарын келтіру.

Й тапсырмалары №15

  1. «Pascal тілдеріні графиктік ммкіндіктері» таырыбында конспект жасау.
  2. Наты бір таырыпты тадап, оытушымен есепті ойылымын натылап, сол таырыптаы графикалы мліметтерді деу(суретін салу) программасын рыыз.

Баылау жмысы №1

Нса І

1. ш санны е кішісі мен е лкеніні осындысын анытаыз.

2. 1 мен 20-ны аралыындаы та сандарды арифметикалы ортасын есептеіз.

3. Студенттерді 8-ші семестрдегі 5 трлі пн бойынша алан баалары берілген. Студенттерді лгерімін анытайтын программа жазыыз.

Нса ІІ

1. Телефон желісіні ызметі келесі трде тленеді: А минутке дейін сйлескені шін айына – В тенге, одан арты болса – С тенге тленеді. Бір айда сйлескен уаыт шін анша тенге тленетіндігін есептейтін программа рыыз.

2. мнін есептеу программасын жазыыз.

3. Бастауыш сыныпты оушылары сыныптары бойынша бой – бойымен сапа трызылан. рбір сынып бойынша оушыларды орташа бой крсеткішін анытайтын программа жазыыздар.

Баылау жмысы №2

Баылау жмысы жолды мліметтерді деу жне ішкі программаларды ру таырыбын мегергендігін тексеруге арналан.

Нса І

Жол берілген. Жолдаы тыныс белгілер санын есептеу.

«азателеком» телефон станциясыны абоненттері туралы мліметтер белгілі: абонентті аты-жні, мекен-жайы, телефонды ондыран жылы, телефон номері. Соы 5 жыл ішінде телефон ондыран абоненттерді санын анытап, экрана аты-жнін жне мекен-жайын шыару.

Нса ІІ

1. Жол берілген. Осы жолдаы «a» ріптерін «b» ріптеріне ауыстыратын программа жазу.

2. уежай кассасында тмендегідей мліметтер белгілі: рейсті номері, баратын жері, шу уаыты, шатын кндері (кн сайын, жп кндері, та кндері). Клавиатурадан енгізілген кні Лондон аласына шатын рейсті номері мен шу уаытын анытайтын программа ру.

Коллоквиум сратарыны тізімі:
1. Транслятор тсінігі. Трлері. 2. Программалау тілдері ні жіктемесі. 3. TURBO PASCAL программалау тілі: алфавиті, синтаксисі, семантикасы. 4. ТР тіліні программалау ортасыны жмысы. 5. Клавиатураны басару пернелеріні ызметтері. 6. Паскаль тіліні лексикасы. Программаны жалпы рылысы. 7. Паскаль тіліні типтер жйесі. Скаляр типтер. Мысал. 8. Паскаль тіліні типтер жйесі. Логикалы тип, олара олданылатын амалдар, нтижелері логикалы типті болатын фукнциялар. Логикалы амалдар. Мысалдар. 9. Айнымалдарды сипаттау болгы. Мысалдар. 10. Типтерді сипаттау. Мысалдар. 11. Тратылар. Трлері. Тратыларды сипаттау болгы. Мысалдар. 12. ТР тіліні типтер жйесі. Шектеулі, саналымды типтер. Мысалдар. 13. ТР тіліні тптер жйесі. Жолды типтер. Мысалдар. 14. Жолды типтерге олданылатын процедуралар мен функциялар. Мысалдар. 15. ТР тіліндегі рылымды типтер жйесі. Мысалдар. 16. ТР тіліндегі стандартты математикалы функциялар мен процедуралар. Мысал. 17. ТР тіліндегі символды жне жолды функциялар мен процедуралар. Мысал. 18. ТР тілі, Айнымалылар. рнектер. Мысал. 19. ТР программалау ортасында программаны деу, жктеу, аятау, орындау. 20. ТР тіліні операторлары: жй жне рылымды операторлар тсінігі. 21. Меншіктеу операторы. Мысал. 22. Енгізу – шыару стандартты процедуралары. Мысалдар. 23. Шартты кшу оператлары. Мысал. 24. Шартсыз кшу операторы мен функциялары. Мысалдар. 25. Мліметтер форматтап шыару. Мысалдар. 26. Дейін-циклыны базалы структурасы. ТР тіліні дейін-цикл операторы. Мысал. 27. зір-цикліні базалы структурасы. зір-цикл операторы. Мысал. 28. Параметрлі айталану операторы. Мысал. 29. Кшу операторларыны кмегімен циклды процестерді йымдастыру. Мысалдар. 30. Регуляр тип. Массивтер. Мысалдар. 31. Бір лшемді массивтер. Енгізу, шыару. Мысал. 32. Бір лшемді массивті элементтерін срыптау тсінігі. Алгоритмі. 33. Екі лшемді массивтер. Сипатталуы. 34. Екі лшемді массивтер элементтерін шыару, енгізу. Мысал. 35. Массивтерге олданылатын амалдар. Символды массивтер.  

 

№1.Трансляторлар.Паскаль тілінде жазылан программа компьютерге тсініксіз боландытан, оны машина тіліне аудару керек болады. Программалау тілінен машина кодтарына аудару процесі трансляция (translation – аудару) деп аталады, ал аудару арнайы трансляторлар деп аталатын программалар арылы орындалады.Трансляторлар ш трлі болады, олар: интерпретаторлар, компиляторлар жне ассемблерлер.Интерпретатор деп берілген программаны р операторын деп, орындайтын трансляторды атайды.Компилятор – берілген программаны толыымен машина тіліндегі модульге айналдырып, оны компьютерді жадына жазып барып орындайды.Ассемблерлер автокодтар (ассемблер) тілінде жазылан программаны машина тіліне трлендіреді.Кез- келген транслятор келесі мселелерді арастырады:Трансляция жасылып жатан программаны синтаксистік ателерін тексереді, талдайды;Объекттік немесе арапайым деп аталатын, копьютерге тсініті болатын программаны жасайды;Компьютерлік жадыны тиімді пайдалануын адаалап байайды (программаны р зіндісіне, айнымалылара, тратылара, массивтерге жіне де баса объектілерге здеріне тн болатын жадыны бліктерін белгілейді).Машиналы командалармен жмыс істеу кп ебекті ажет ететін боландытан,бірінші буын ЭЕМ дері жарыа шыаннан бастап а программа руды жеілдету жолы мен ЭЕМ ні зі осы программаны машиналы тілге автоиатты трде аударып,жадына енгізе алатын тсілдерді іздестірген зерттеулер кптеп жргізіле бастады.Осыны нтижесінде Осыны нтижесінде трлі жоары дегейлі алгоритмдік тілдер мен оларды ЭЕМ арылы машиналы тілге автоматты трде аударатын транслятор «аударыш» атаулы арнайы программалар пайда болды. Транслятор интерпретатор жне компилятор деп аталатын екі трі бар (interpretation – арадаы,тсініктілеу тілге аудару:compilation жинатау,растыру).Интерпретатормен жмыс істеу кезінде процессор оны прогрпммалау тілдерінен аударан кезекті р операторын бірден орындайды. Компилятор алдымен программаны синтаксисін тексеріп,программада жіберілген синтаксистік ателерді хабарлайды.Олар жнделген со жктеуші деп аталатын программасын іске осады, ол алдымен программаны машиналы тілге жуы обьектілік программа деп аталатын аралы программаа трлендіріп шыады.Одан рі байланыстарредакторы деп аталатын программа іске осылып,ол обьектілік программаа программалау тілі ішінде арнайы дайындалан кітапханалы процедуралардан ажетті стандартты процедуралар мен функцияларды осады.Осыдан кейін программа дайын болады да,ол бірден орындалады.лкен ЭЕМ дер компилятормен жабдыталан,ІВМ РС ге йлесімді дербес компьютерді екеуімен же жмыс істеу ммкіндіктері бар.

 

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

 

№38.Іздеу деп берілген жиында берілетін эталон априорыиы (немесе шаблонны) асиеттеріне и объектіні табуды атайды. Кп жадайда жиын массив трінде аныталады. Сызыты іздеу – ажетті элементті массив элементтерін арапайым бірінен кейін бірін эталонмен салыстыра отырып іздейтін процедура. Кедергімен сызыты іздеу – бл ізделінді элемент массивті шекаралы a[n+1] элементі болып осымша енгізіліп, жне іздеу рдісінде a[i]=x болатындай i табылатын іздеу.
Ал егер a[i]=x тек ана i=n+1 болса, онда массивте ізделінді элемент жо. Кп жадайда іздеу реттелген массивте жргізілген тиімді. Бл жадайларда тиімді дістерді бірі – а блу бойынша іздеу.
а бліп іздеу дісінде ізделінді эталонды салыстыру массивті ортасында орналасан элементпен жргізіледі, салыстыру нтижесіне байланысты (арты немесе кем) ары арай іздеу массивті не сол жа жартысында, не о жа жартысында жргізіледі.

 

Рекурсия. Рекурсивті алгоритмдер

зін зі шаыратын функция рекурсия деп аталады. Рекурсия тередігі дегеніміз – функция мнін есептеуде зін-зі шаыру саны. Рекурсивті программалау стек принципіне сйенеді.

Рекурсия трлері мынадай:

- сызыты рекурсия;

- параллель рекурсия;

- осалы рекурсия;

- жоары ретті рекурсия.

 

Рекурсивті алгоритмдер мысалдары:

§ 6!- алты факториялды есептеу алгоритмі:

#include< stdio.h>

double fact(int n);

int n=6;

double f;

f=fact(n);

printf(‘6!=%10.0f\n”,f);

return (0);

}

double fact(int n)

{

if (n<1) return(1.0)

else

return(n*fact(n-1); }