Бағдарламалауға_кіріспе_5

1.

АЛМАТЫ ГУМАНИТАРЛЫ-ЭКОНОМИКАЛЫҚ УНИВЕРСИТЕТІ
Ақпараттық жүйелер және жалпы білім беретін пәндер кафедрасы
«Бағдарламалауға кіріспе» курсы (С/C++ тілдері мысалында)
5-ДӘРІС
Массивтер және оларды өңдеу
Лектор
Байсалбаева Куляш Нарзилдаевна
қауымдастырылған профессор, PhD
Байсалбаева К.Н. · 5-дәріс
e-mail: k.bais@mail.ru
жұм. тел. 8 727 309 58 15, қосымша 110
ұялы. 8 777 362 38 15
1

2.

5-ДӘРІС
Дәріс тақырыбы
Бір өлшемді массивтерді анықтау және өңдеу, сондай-ақ массивтерді толтыру үшін
кездейсоқ сандар датчигін пайдалану қарастырылады. Одан әрі массивтерді өңдеу
тәсілдері мен оларды сұрыптау көрсетіледі.
Анықтау
Өңдеу
Сұрыптау
жариялау, индекстер,
инициализация
массивті аралау,
есептердің төрт класы
реттеудің қарапайым
әдістері
Байсалбаева К.Н. · 5-дәріс
2

3.

Дәріс сұрақтары
1
Массивтермен жұмыс
5
Кездейсоқ сандар датчигі
2
C/C++ тілінде массивті анықтау
6
Массивтерді өңдеу класы
3
Бір өлшемді массивтерді өңдеу
7
Массивтерді сұрыптау
4
Псевдодинамикалық массивтер
Негізгі идея
Массивке қатысты кез келген есеп
элементтерді аралау схемасын таңдап, оған
қажетті өңдеу операторларын қоюға саяды.
Байсалбаева К.Н. · 5-дәріс
3

4.

1-СҰРАҚ
Массивтермен жұмыс
C/C++ тілінде базалық типтерден басқа, солардың
негізінде алынған туынды типтерді енгізуге және
пайдалануға рұқсат етілген. Тіл стандарты оларды
алудың үш тәсілін анықтайды:
1
2
3
Массив
бір типтегі айнымалылардың
реттелген тізбегі.
берілген типтегі элементтер массиві
берілген типтегі объектіге сілтеуіш
берілген типтегі мән қайтаратын функция
Байсалбаева К.Н. · 5-дәріс
Массивтің әрбір элементіне жадының бір
ұяшығы бөлінеді.
Бір массивтің элементтері жадының
бірінен соң бірі орналасқан ұяшықтарын
алады.
4

5.

1-СҰРАҚ
Массивтің аты, индексі, өлшемі
▪ Барлық элементтің аты бір — массив аты, ал олар индекстерімен, яғни массивтегі реттік нөмірімен
ажыратылады.
▪ Массивтегі элементтер саны оның өлшемі деп аталады.
▪ Жадыда қажетті ұяшық санын бөлу үшін массивтің өлшемін алдын ала білу керек.
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
44
55
12
42
94
18
a[99]
…
7
100 элементтен тұратын a массиві: аты біреу, индекстері әртүрлі
Массивке жады бөлу бағдарламаны компиляциялау кезеңінде орындалады.
Байсалбаева К.Н. · 5-дәріс
5

6.

2-СҰРАҚ
C/C++ тілінде массивті анықтау
int a[100];
sizeof(a)
// бүтін типтегі 100 элементтен тұратын массив
=
400
нөмірлеу 0-ден басталады
4 байттан 100 элемент
0
бірінші элемент — a[0], соңғысы — a[99]
1
2
99
…
жадының бірінен соң бірі орналасқан 100 ұяшығы
Байсалбаева К.Н. · 5-дәріс
6

7.

2-СҰРАҚ
Массив элементіне қатынау
Массив элементіне қатынау үшін оның атын және элемент нөмірін (индексін) көрсету керек:
a[0]
a[55]
a[i]
a[2*i]
индекс — тұрақты
индекс — тұрақты
индекс — айнымалы
индекс — өрнек
Жариялау кезіндегі инициализация:
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
sizeof(a) = 40 — 4 байттан 10
элемент
Массивті сипаттағанда элементтердің нақты саны көрсетіледі, мысалы a[20].
Байсалбаева К.Н. · 5-дәріс
7

8.

2-СҰРАҚ
Массивті инициализациялау
Егер бастапқы мәндер саны массивтің жарияланған ұзындығынан аз болса, бастапқы мәндерді тек
алғашқы элементтер алады, ал қалғандары нөл деп саналады.
int a[10] = {1, 2, 3, 4, 5};
// a[5] … a[9] нөлге тең
int a[ ] = {0, 1, 1, 2, 3, 5, 8};
// sizeof(a) = 28 — 7 элемент
Массивтің ұзындығы инициализация кезінде келтірілген мәндер саны бойынша есептеледі.
a[n] деп жазу үшін n айнымалысын алдын ала тұрақты ретінде жариялау керек:
#define n 20
Байсалбаева К.Н. · 5-дәріс
const int n = 20;
8

9.

3-СҰРАҚ
Бір өлшемді массивтерді өңдеу
Массивтермен жұмыс істегенде барлық
элементті немесе олардың бір бөлігін бірдей
өңдеу жиі қажет болады. Ол үшін массивті
аралау ұйымдастырылады.
Аралау бағыттары
солдан оңға — массивтің басынан соңына қарай
оңнан солға — массивтің соңынан басына қарай
Аралау сипаттамалары
▪
аралау бағыты;
▪
бір мезгілде өңделетін элементтер саны;
▪
индекстердің өзгеру сипаты.
Байсалбаева К.Н. · 5-дәріс
екі шеттен ортаға қарай
Индекстердің өзгеруі
сызықты
сызықты емес
тұрақты қадаммен
айнымалы қадаммен
9

10.

4-СҰРАҚ
Псевдодинамикалық массивтерді құру
Бағдарламада массивті сипаттағанда компилятор
оған қажетті жады көлемін бөлуі үшін элементтер
санын міндетті түрде көрсету керек.
Қолайсыздығы неде
Массивтегі элементтер саны шешілетін есепке
байланысты өзгеруі мүмкін, ал сипаттауда
көрсетілген өлшем компиляция кезеңінде
бекітіліп қалады.
Байсалбаева К.Н. · 5-дәріс
Шешімі
Динамикалық массивтер
сілтеуіштер арқылы жүзеге
асырылады: массивке жады өлшемі
белгілі болғанда, бағдарламаның
жұмысы кезінде бөлінеді.
10

11.

5-СҰРАҚ
Кездейсоқ сандар датчигін пайдалану
Кездейсоқ сандар датчигі (КСД) — псевдокездейсоқ
сан құрайтын бағдарлама.
rand() функциясы
Қарапайым КСД қалай жұмыс істейді
int rand()
▪
үлкен K саны және еркін x0 саны алынады;
▪
x1 = бөлшек_бөлігі(x0·K), x2 = бөлшек_бөлігі(x1·K)
сандары құрылады және т.с.с.
Нәтижесінде 0-ден 1-ге дейінгі кесіндіде ретсіз
шашыраған x0, x1, x2, … тізбегі шығады. Оларды
кездейсоқ, дәлірек айтқанда псевдокездейсоқ деп
санауға болады.
Байсалбаева К.Н. · 5-дәріс
0 … RAND_MAX = 32767 диапазонынан
псевдокездейсоқ сан қайтарады.
Функцияның сипаттамасы <stdlib.h>
файлында. Нақты КСД күрделірек f(x)
функциясын жүзеге асырады.
11

12.

5-СҰРАҚ
КСД көмегімен массив құру
#include <iostream>
#include <stdlib.h>
using namespace std;
main()
{
int a[100], n;
cout << "\nEnter the size of array:";
cin >> n;
for (int i = 0; i < n; i++)
{
a[i] = rand() % 100 - 50;
cout << a[i] << " ";
}
}
Байсалбаева К.Н. · 5-дәріс
Жұмыс нәтижесі
Талдау
▪
rand() % 100 өрнегі 0…99 санын
береді;
▪
50-ді азайту диапазонды −50…49
аралығына жылжытады;
▪
аралау солдан оңға қарай 1
қадаммен, бір элементтен
жүреді.
12

13.

6-СҰРАҚ
Массивтерді өңдеу есептерінің класы
Циклдерді ұйымдастыру ұқсастығы бойынша массивтерді өңдеу есептері төрт класқа бөлінеді.
1-класс
2-класс
Массивтің барлық немесе көрсетілген
элементтерін біртектес өңдеу.
Массив элементтерінің орналасу реті өзгереді.
3-класс
4-класс
Бірнеше массивті немесе бір массивтің ішкі
массивтерін өңдеу — синхронды не
асинхронды.
Іздеу есептері: берілген мәнмен сәйкес келетін
алғашқы элементті табу.
Байсалбаева К.Н. · 5-дәріс
13

14.

6.1-СҰРАҚ
1-класс есептері. Минимумды іздеу
Қолайлы аралау схемасы таңдалып, оған элементтерді өңдеу операторлары қойылады.
// Минимумды анықтау
#include <iostream>
#include <stdlib.h>
using namespace std;
main()
{
int a[100], n;
cout << "\nEnter the size of array:";
cin >> n;
for (int i = 0; i < n; i++)
{
a[i] = rand() % 100 - 50;
cout << a[i] << " ";
}
int min = a[0];
for (int i = 1; i < n; i++)
if (a[i] < min) min = a[i];
cout << "\nMin = " << min << endl;
}
Байсалбаева К.Н. · 5-дәріс
Жұмыс нәтижесі
Идеясы
▪
минимум ретінде a[0]
алынады;
▪
массив екінші элементтен
бастап қаралады;
▪
кіші мән ағымдағы
минимумды алмастырады.
14

15.

6.2-СҰРАҚ
2-класс есептері. Элементтерді алмастыру
Массив ішіндегі элементтерді алмастыру көмекші айнымалы арқылы орындалады:
int r = a[i];
a[i] = a[j];
a[j] = r;
Мысал. Массивті керісінше аудару
for (int i = 0, j = n-1; i < j; i++, j--)
{
int r = a[i];
a[i] = a[j];
a[j] = r;
}
Байсалбаева К.Н. · 5-дәріс
// a[i] мен a[j] алмасады
Қалай жұмыс істейді
▪
екі индекс бір-біріне қарама-қарсы
жүреді: i басынан, j соңынан;
▪
әр қадамда екі элемент орындарын
ауыстырады;
▪
индекстер массивтің ортасында
кездескенде цикл аяқталады.
15

16.

6.2-СҰРАҚ
2-класс есептері. Жұп элементтерді алмастыру
Массивтегі элементтердің жұптарын алмастыру: 1 мен 2, 3 пен 4, 5 пен 6 және т.с.с.
for (int i = 0; i < n-1; i += 2)
{
int r = a[i];
a[i] = a[i+1];
a[i+1] = r;
}
алмасқанға дейін
1
2
Байсалбаева К.Н. · 5-дәріс
Назар аударыңыз
▪
цикл қадамы 2-ге тең — индекс жұптан
аттап өтеді;
▪
i < n−1 шарты тақ n болғанда массив
шегінен шығып кетуден қорғайды.
алмасқаннан кейін
3
4
5
6
2
1
4
3
6
5
16

17.

6.3-СҰРАҚ
3-класс есептері. Бірнеше массив
Синхронды өңдеу
Асинхронды өңдеу
Массивтерді аралағанда индекстер бірдей өзгереді.
Әр массивтің индексі өз схемасы бойынша өзгереді.
Синхронды өңдеу мысалы
n бүтін элементтен тұратын екі массив берілген. c[i] = a[i] + b[i] массивін алу керек.
for (int i = 0; i < n; i++)
Байсалбаева К.Н. · 5-дәріс
c[i] = a[i] + b[i];
17

18.

6.4-СҰРАҚ
4-класс есептері. Іздеу есептері
Іздеу есептерінде берілген шартты
қанағаттандыратын элементті табу керек. Ол үшін
массивті аралау және шартты тексеру
ұйымдастырылады.
Циклден шығудың екі мүмкіндігі
int k = -1;
// табылған элементтің индексі
for (int i = 0; i < n; i++)
if (a[i] == x)
{
k = i;
break;
// элемент табылды
}
if (k == -1)
cout << "element ne nayden";
else
cout << "index = " << k;
Элемент табылды
қарау мерзімінен бұрын тоқтайды
Элемент табылмады
бірақ массивті қарау аяқталды
Байсалбаева К.Н. · 5-дәріс
18

19.

7-СҰРАҚ
Массивтерді сұрыптау
Сұрыптау — берілген объектілер жиынын белгілі бір тәртіпте қайта топтастыру
процесі.
Сұрыптаулар жылдамдығы бойынша бөлінеді
Қарапайым әдістер
Жылдам сұрыптаулар
n · n салыстыру
n · ln(n) салыстыру
n — массивтегі элементтер саны
амалдар аз, бірақ амалдардың өзі күрделірек
Қарапайым әдістердің алгоритмдері қысқа әрі оңай, сондықтан сұрыптау принциптерін түсіндіруге
ыңғайлы. Шағын массивтер үшін олар күрделі әдістерден тиімдірек.
Байсалбаева К.Н. · 5-дәріс
19

20.

7-СҰРАҚ
Қарапайым сұрыптау әдістері
1
қарапайым қосу (кірістіру) әдісімен сұрыптау
2
қарапайым бөліп алу әдісімен сұрыптау
3
қарапайым алмастыру әдісімен сұрыптау
7.1 Қарапайым қосу әдісімен сұрыптау
Массив элементтері дайын тізбек пен бастапқы тізбекке
бөлінеді. i = 2-ден бастап әр қадамда бастапқы тізбектен iші элемент алынып, дайын тізбектің қажетті орнына
қойылады, содан кейін i бірге артады.
Байсалбаева К.Н. · 5-дәріс
44
дайын
55
12
42
94
18
бастапқы тізбек
20

21.

7.1-СҰРАҚ
Қосу әдісі: орынды іздеу
▪ Таңдалған a[i] элементі j = i − 1-ден бастап сұрыпталған бөліктің элементтерімен салыстырылады.
▪ Егер a[j] таңдалғаннан үлкен болса, ол бір орынға оңға жылжиды, ал салыстыру дайын тізбектің
келесі элементімен жалғасады.
▪ Қолайлы орын табылысымен таңдалған элемент сұрыпталған бөлікке қосылады.
Орынды іздеу процесі екі шарттың бірінде аяқталады
a[j] > a[i] элементі табылды
Сол жақ шетке жетті
қою орны анықталды
таңдалған элемент дайын бөліктегі ең кішісі
Байсалбаева К.Н. · 5-дәріс
21

22.

М А С С ИВ Т Е Р Д І Ө Ң Д Е У
1-мысал. Массивтің орташа арифметикалық мәні
a(10) бүтін сандар массивінің орташа арифметикалық мәнін табу.
#include <iostream>
#include <stdlib.h>
#define n 10
using namespace std;
main()
{
int i = 0, s = 0, a[n];
cout << "Vvedite 10 elementov massiva:\n";
while (i < n)
{
cout << "a[" << i << "]=";
cin >> a[i];
s = s + a[i];
i = i + 1;
}
cout << "srednee arifm. massiva: " << (float)s/n;
}
Байсалбаева К.Н. · 5-дәріс
22

23.

М А С С ИВ Т Е Р Д І Ө Ң Д Е У
1-мысал. Бағдарламаның жұмыс нәтижесі
Бағдарламада не болып жатыр
Байсалбаева К.Н. · 5-дәріс
▪
массив өлшемі #define n 10
тұрақтысымен берілген;
▪
while циклі элементтерді бір-бірден
енгізіп, s қосындысын бірден
жинақтайды;
▪
(float)s/n түрлендіруі бөлудің бүтін
емес, нақты сандық болуы үшін
қажет.
23

24.

М А С С ИВ Т Е Р Д І Ө Ң Д Е У
2-мысал. Максимум және оның индексі
Берілген массивтің ең үлкен элементін және оның индексін анықтау.
/* Максимумды анықтау */
#include <iostream>
#define n 10
using namespace std;
main()
{
int i, t, a[n] = {6,5,9,8,7,4,1,2,3,0}, max;
cout << "Elementi massiva a[10]: ";
for (i = 0; i < n; i++)
cout << " " << a[i];
max = a[0]; t = 0;
// max - maximum, t - index
for (i = 1; i < n; i++)
if (a[i] > max)
{ max = a[i]; t = i; }
cout << "\nmax = " << max << " index = " << t;
}
Байсалбаева К.Н. · 5-дәріс
Жұмыс нәтижесі
Идеясы
▪
екі мән сақталады:
максимум max және
оның индексі t;
▪
максимум ауысқанда
индекс те онымен бірге
жаңарады;
24

25.

Тыңдағандарыңызға рахмет!
Сұрақтарыңыз бар ма?
Байсалбаева К. Н.
k.bais@mail.ru · 8 777 362 38 15
Байсалбаева К.Н. · 5-дәріс
25