№4 Зертханалық жұмыс

Тақырыбы: Алгоритмдер. Алгоритмді әзірлеу негіздері. Блок-схемалар.

Жұмыстың мақсаты: Есеп қойылымы және блок-схема түрінде есептеу процесі құрылысының базалық алгоритмін әзірлеуді студенттерге үйрету.

Теориядан қысқаша мағлұматтар

Алгоритм ұғымы – информатиканың аса іргелі ұғымдарының бірі. Нақты алгоритмдерді орындау әртүрлі жүйелердегі басқару процестеріне келіп тіреледі, ол алгоритм ұғымын кибернетикаға жақындатады. «Алгоритм» сөзі IX ғасырда арифметикалық амалдарды орындау ережесін ойлап тапқан ғалым әйгілі математик Аль-Хорезми есімінің латынша жазылуы - algorithmi сөзінен алынған.

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

Блок-схема дегеніміз – алгоритм командаларының орындалу ретін көрсететін бағытталған граф. Мұндай графтың төбелері үш типтің біреуіне жатуы мүмкін: «функциональды» (а) төбе (бір кіріс және бір шығыстан тұрады); «предикатты» (б) төбе (бір кірістен және екі шығыстан тұрады); «біріктіруші» (в) төбе (қосылу төбесі), ол басқаруды шығысқа екі кірістің біреуінен беруді қамтамасыз етеді.

Бағдарламалаудың базалық құрылысы

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

• композиция немесе бір ізбен жүру;

• тармақталу (альтернатива, егер – онда – әйтпесе);

• итерация немесе цикл (алдынан шартталған, соңынан шартталған, белгілі қайталану санымен).

Бұл құрылымдардың ерекшелігі оларда бір кірістің және бір шығыстың бар болуы.

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

Оператор дегеніміз әрекеттердің қандай да бір тізбегін орындауға арналған ұйғарымды формальді түрде жазу.

Екінші базалық құрылым. Екінші базалық құрылымға "альтернатива немесе тармақталу" жатады. Бұл құрылым шартты тексеру нәтижесіне тәуелді (ақиқат немесе жалған) альтернативтік жолдардың біреуінен алгоритм жұмысын таңдайды, сонымен қоса жолдардың әрқайсысы жалпы шығуға алып келеді.

Алгоритмнің орындалуының мүмкін жолдарын сәйкес белгілермен көрсетеді: ақиқат/жалған, иә/жоқ, 1/0.

Дербес жағдайда таңдап алынған жолдардың біріне әрекетті орындау қажет болмауы мүмкін. Мұндай құрылым "айналып өту" немесе "егер - онда" құрылысы деп аталады.

Құрамына "альтернатива немесе тармақталу" базалық құрылысы кіретін алгоритм тармақталған деп аталады.

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

Үшінші базалық құрылым. Үшінші базалық құрылым "цикл". Цикл бірнеше рет қайталанып орындалуды немесе басқа сөзбен айтқанда операторлардың циклдік жұмысын береді.

Мұндай құрылымның үш түрі бар:

• "цикл - әзірше"

• "цикл - дейін".

• Қайталанудың ақырғы саны.

Циклде қайталанатын операторлар тобын цикл денесі деп атайды. "Цикл - әзірше" құрылысының "цикл - дейін" құрылысынан айырмашылығы мынада: бірінші құрылымда цикл денесінің операторлары шартқа байланысты мүлдем орындалмауы да мүмкін, ал "цикл – дейін" құрылысында цикл денесі бір рет болса да орындалады. "Цикл - әзірше" құрылысында шарттың орындалуын тексеру цикл денесінің операторларын орындаудан бұрын жүзеге асырылады, ал "цикл - дейін" құрылысында – цикл денесінен өткеннен кейін орындалады.

Циклдер ішінде тағы басқа циклдер болуы мүмкін. Мұндай құрылымдар ішкі циклдер деп аталады. Құрамында "цикл" базалық құрылысы бар алгоритмдер циклдік деп аталады.

Қарастырылған базалық құрылымдарды алгоритмді әзірлеуге қойылатын құрылымдық артықшылықты сақтау үшін қолдану ұсынылады. Нақты алгоритмдер қарастырылған барлық базалық құрылымдардан тұрады. Қайталану саны берілген (санағыш цикл) цикл қандай да бір әрекеттерді көрсетілген санмен қайталау керектігін белгілейді.

Кез келген алгоритм келесі қасиеттерге ие болуы керек:

• Бірдей бастапқы берілгендермен бірнеше рет есептегенде алынған нәтиженің қайталануы;

• Қандай да бір нәтиженің (сан, кесте, дыбыс, бейне) міндетті түрде алынғандығы туралы немесе берілген алгоритм қойылған есепті шешу үшін қолайлы екендігі туралы сигналды беретін - нәтижелілігі;

• Ұқсас есептердің бірнеше тобы үшін әртүрлі бастапқы берілгендерде нәтижені алу мүмкіндігі - жалпылығы;

• Алгоритмді жеке қарапайым әрекеттерге бөлу мүмкіндігі - дискреттілігі.

4.1-кесте – Графиктік блок-схемаларды құруға арналған негізгі блоктар

1		2
Процесс
Алдын ала анықталған процесс (ішкі бағдарлама)
Сызық түрлері
Басы- соңы
4.1 – кестенің жалғасы
1	2
5. Шарты
6. Енгізу-шығару
7. Модификация
8. Түсіндірме
9. Парақ ішіндегі біріктіргіш
10. Парақ арасындағы біріктіргіш

Жұмыстың барысы:

1. Тапсырма нұсқасын таңдау.

2. Теориялық бөліммен танысу.

3. Әрбір тапсырма үшін есептің қойылымын орындау.

4. Әртүрлі – сызықты, тармақталған, циклдік құрылымды есептің алгоритмін блок-схема түрінде әзірлеу.

Есеп беру мазмұны:

1. Есептің қойылымы.

2. Алгоритмнің графиктік блок-схемасы.

3. Алгоритмдерге талдау жүргізу.

Тапсырма нұсқалары:

4.2-кесте – Сызықты (бір ізбен жүру) құрылымды алгоритм құру

№ нұсқа	Есептеу формулалары	Бастапқы берілгендер
1	2	3
1.
2.
3.
4.		a=-0.5 b=1.7 t=0.44
5.		a=-15 b=15.5 x=- 2.9
6.		a=16.5 b=3.4 x=0.61
7.		a=0.7 b=0.05 x=0.5
4.2-кестенің жалғасы
1	2	3
8.		a=1.1 b=0.004
9.		m=2 c=- 1 t=1.2; b=0.7
10.		a=3.2 b=17.5 x=- 4.8
11.		a=10.2 b=9.2 c=0.5
12.		a=0.3 b=0.9 x=0.61
13.		a=0.5 b=3.1 x=1.4
14.		a=0.5 b=2.9 x=0.3
15.		m=0.7 c=2.1 x=1.7 b=1.08

4.3-кесте – Тармақталған (альтернатива) құрылымды алгоритм құру

№ нұсқа	Формула	Шарт	Бастапқы берілгендер	Диапазон және аргументтің өзгеру қадамы
1.	2	3	4	5
1.			a=-0.5 b=2

4.3-кестенің жалғасы
1	2	3	4	5
2.		x<1.3 x=1.3 x>1.3	a=1.5
3.		x<1.2 x=1.2 x>1.2	a=2.8 b=-0.3 c=4
4.		x<1.4 x=1.4 x>1.4	a=1.65
5.		x<1 x=1 1<x<2 x>2	a=2.3
6.			a=2.5
7.			b=1.5
8.			_
9.			a=20.3
10.		x<0.5 x=5 x>0.5	t=2.2

4.3-кестенің жалғасы
1	2	3	4	5
12.			a=0.9
13.			a=2.1 b=1.8 c=-20.5
14.			a=0.3 n=10
15.		t<0.1 t=0.1 t>0.1	a=2.5 b=0.4

4.4-кесте – Циклдік (итерация) құрылымды алгоритм құру

№ нұсқа	Массив	Әрекет	Шарттар мен шектеулер
1	2	3	4
	X(100)	X массивінің элементтерінің санын және қосындысын есептеу	1xi 0
	A(80)	A массивінің элементтерінің орташа арифметикалық қосындысын есептеу	ai >0
	X(70)	X массивінің элементтерін Y массивіне жазу және олардың санын анықтау	1xi -1
	B(50)	В массивінің ең үлкен элементін және оның нөмірін анықтау	xi >0
	C(40)	C массивінің ең кіші элементін және оның нөмірін анықтау	xi <0
	D(80)	D массивінің ең үлкен және ең кіші элементтерін тауып, олардың орындарын ауыстыру	__
	Y(20)	Y массивінің элементтерінің орташа геометриялық қосындысын есептеу	yi >0

4.4-кестенің жалғасы
1	2	3	4
	Z(30)	Z массивінің элементтерін R массивіне алдымен оң элементтерін, содан кейін теріс элементтерін орналастыру	__
	N(50)	A массивінің элементтерінің қосындысын табу	n i /3*3= n i
	X(N)	X массивінің элементтерінің санын және қосындысын есептеу	x i >0, 30N
	A(N)	X массивінің элементтерінің орташа геометриялық қосындысын есептеу	a i >0, 50N
	X(N)	X массивінің оң элементтерін Y массивіне ретімен жазу	x i >0, 40N
	X(N)	X массивінің оң элементтерін Y массивіне, ал теріс элементтерін Z массивіне ретімен жазу	40N
	B(K)	B массивінің ең үлкен элементін және оның реттік нөмірін табу	x i <0, 40K
	C(K)	C массивінің ең кіші элементін және оның реттік нөмірін табу	1x i -1, 20K

Бақылау сұрақтары

1. Алгоритмнің базалық құрылымдары қандай?

2. Бағдарламаны тестілеу дегеніміз не?

3. Бағдарламаны жобалауға құрылымдық тәсіл неден тұрады?

4. Алгоритм дегеніміз не?

5. Бағдарламаны жобалау кезінде қайталап есептеу қалай жүзеге асырылады?

6. Алгоритм сөзі қайдан шыққан?

7. Блок-схема деген не?

8. Итерация деген не?

9. Есептеу процесінде қайталауды орындайтын алгоритм түрлері қандай?

Әдебиеттер:

1. Вирт Н. Алгоритмы и структуры данных

2. Могилев А.В. Информатика: Учеб. пособие для студ. пед. вузов. -М.: Издательский центр «Академия», 2003.

3. Попов В.Б. Основы компьютерных технологий. – М.: Финансы и статистика, 2002.

4. Симонович С.В. Информатика. –СПб, 2004.