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

Й тапсырмалары №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); }