ЛАБОРАТОРНА РОБОТА № 10.5

Тема: Базові алгоритми розрахунку суми, кількості елементів
масивів інформації

Мета: визначити основні правила та принципи побудови алгоритмів по обробці елементів масивів інформації графічним способом та набути практичні навички роботи з редактором блок-схем AFCE.

Обладнання: комп’ютери типа Pentium з ОС Windows (XP, Seven), програма-редактор блок-схем AFCE.

Теоретичні основи:

Основні характеристики масиву

Масив характеризується ім'ям, розмірністю і розміром.

Ім'я масиву

• Ім'я масиву утворюється за загальним правилом утворення імен перемінних ( тобто являє собою ідентифікатор).
• Воно не повинно збігатися з ім'ям ні однієї перемінної, використовуваної в тій же програмі.
• Елементи масиву позначаються перемінною з індексом і складаються з імені масиву і наступного за ним у круглих дужках списку індексів - А(1), В(8), С(3,5).
• В якості індексів можуть використовуватися константи – А(1), В(8), С(3,5); перемінні –  F(і), MAS(і,j); а також арифметичні вираження (індексні) – MAS(і+4).
• Якщо як індекси використовуються перемінні або індексні вираження, то значення всіх зазначених перемінних повинні бути визначені до звертання до елементів масиву.
• В одному масиві можуть бути елементи тільки одного типу.  –   А%(14), В#(8), С$(3,5); Базовий тип елемента масиву називається базовим типом всього масиву.

Розмірність масиву

Індекси визначають положення елементів у масиві, а кількість індексів в імені елемента масиву визначає розмірність цього масиву - тобто форму його компонування:

• Одномірний масив - відповідає лінійній таблиці, його елемент позначається перемінною з одним індексом  А(1), А(і)                                 
• Двовимірний масив - відповідає прямокутній таблиці, його елемент позначається перемінної з двома індексами  А(3,4), А(і,j), де перший індекс відповідає номерові рядка, а другий - номерові стовпця прямокутної таблиці.
• Тривимірний масив можна уявити в вигляді кубічної таблиці:

Індекс - це список числових виражень, розділених комами.

Розмір масиву

Для запису елементів масиву в пам'ять комп'ютера потрібно виділити для їхнього збереження необхідну кількість (масив) комірок пам'яті, що визначається розміром масиву.

Розмір масиву задається верхніми  границями зміни індексів (останніми) по кожнім вимірі:

• Для одномірного масиву – наприклад, якщо масив має останній елемент А(19), то його розмір дорівнює 19.
• Для двовимірного масиву (n-мірних масивів) – добуток значень верхніх границь індексів. Наприклад, якщо масив має останній елемент А(5,7), то його розмір дорівнює 5*7=35; для масиву В(3,4,2) – розмір дорівнює 3*4*2=24

Доступ до елементів масиву

• Ми повинні звертатися до окремих елементів масиву, щоб привласнити їм значення, вивести їх на друк, використовувати у відповідних операціях, тобто по всім тим причинам, з яких ми звертаємося до окремої змінної;
• Для звертання до окремого елементу масиву, ми повинні вказати ім'я масиву і після нього в дужках (можна в круглих, можна в квадратних) номер цього елемента в масиві. Значення в дужках називається індексом масиву. Максимальне значення індексу - це значення, задане при об'яві масиву;
• Таким чином, перший елемент масиву А ми описуємо як А(1). Другий елемент масиву описується як А(2); 53-й – як А(53);
• Найбільш могутній засіб при роботі з масивами - можливість представлення індексу перемінною або складним вираженням – А(і,j), MAS(і+1). Треба тільки передбачити, щоб значення індексу завжди задовольняло заданому розміру масиву;
• Програма не повинна намагатися звернутися до елементів, номер яких менше 0 або більше заданого в описі розміру масиву. Це вважається помилкою і називається порушенням границь масиву.

Завантаження багатомірних масивів:

Значення елементам багатомірних масивів можуть бути привласнені кожним зі способів, що використовуються для присвоєння значень звичайним перемінним.

Ці способи включають:

• команда присвоювання (х:=1),
• команда введення значень (ввод х),

Найбільш природний шлях присвоювання значень елементам масивів - використання цих команд у тілі циклу. Для двомірних масивів звичайно використовуються два вкладених цикли , найчастіше з параметрами. Лічильник (або змінна циклу) одного циклу пробігає по рядках масиву; лічильник іншого - по стовпцях. Нижче наведені приклади введення значень елементів двовимірного масиву, наприклад, А(8,7) (загальний вигляд A(i,j)):

Блок-схема алгоритму введення    Блок-схема алгоритму введення

даних по рядках (схема А)     даних по стовпцях (схема Б)

На псевдокоді алгоритми мають наступний вигляд:

Приклади виконання завдання:

Задача №1: Скласти схему алгоритму розрахунку суми елементів в одномірному масиві А(17)

Пояснення до розробки алгоритму рішення задачі:

Перш ніж почати які-небудь операції з елементами масиву необхідно ввести їх значення. Введення елементів масиву, як і сам процес обчислення суми, носить циклічний характер. Тому введення чергового елементу  А(і)  масиву А и додавання його до перемінної суми S складають тіло того самого циклу. Чому підрахунок суми ми помістили в тіло циклу? Давайте розглянемо схему підрахунку суми:

Спочатку перемінна суми не повинна мати ніякого значення, але якщо  ви (або інший користувач) у попередній програмі використовували перемінну S то, щоб захистити себе від випадкового значення перемінної суми  ми повинні її обнулити, тобто привласнити їй значення 0:

S=0.

У циклі нарощування значень зміною суми (фактично підрахунок поточного значення перемінної S) відбувається по наступному алгоритмі - до попереднього значення перемінної S додається поточне значення елемента A(і), схематично це виглядає в такий спосіб:

Перший прохід циклу:

S=[0]+A(1),де [0] – початкове значення перемінної S привласнене їй до початку роботи циклу.

Другий прохід циклу:

S=[0+A(1)]+A(2), де [0+A(1)] – попереднє значення перемінної S привласнене їй при першому проході циклу.

Третій прохід циклу:

S=[0+A(1)+A(2)]+A(3), де [0+A(1)+A(2)] – попереднє значення перемінної S привласнене їй при другому проході циклу.

Четвертий прохід циклу:

S=[0+A(1)+A(2)+A(3)]+A(4), де [0+A(1)+A(2)+A(3)] – попереднє значення перемінної S привласнене їй при третьому проході циклу.

І т.д. - узагальнимо весь процес нарощування суми в загальну формулу:

S=S+A(I)

Висновок значення перемінної суми оформлюється за циклом, тому що нам необхідно довідатися кінцеве значення перемінної суми S. Якщо дію виводу значення перемінної S помістити в циклі, то на екран будуть виводитися всі проміжні значення перемінної суми S при кожнім проході циклу.

Алгоритм рішення задачі:

Графічний засіб – блок-схема:    Псевдокод алгоритмічною мовою:

Задача №2: Скласти схему алгоритму розрахунку суми елементів в одномірному масиві А(17) з умовою

Пояснення до розробки алгоритму рішення задачі:

Нехай необхідно підрахувати окремо суму, тільки позитивних елементів масиву А, для цього в тіло циклу ми помістимо команду розгалуження (умовного переходу), у якому і задамо умову за якою буде вестися підрахунок суми, наприклад, тільки позитивних елементів масиву. У цьому випадку ми скористалися командою неповного умовного переходу, тому якщо при перевірки умова дасть значення «негативне» (значення поточного елемента негативне), то дія цієї гілки розгалуження не виконується, а поточний елемент просто буде пропущений.

Алгоритм рішення задачі:

Графічний засіб – блок-схема:    Псевдокод алгоритмічною мовою:

Задача №3: Скласти схему алгоритму розрахунку кількості елементів в одномірному масиві А(17)

Пояснення до розробки алгоритму рішення задачі:

Принцип підрахунку кількості елементів у масиві А аналогічний принципові підрахунку суми елементів масиву, але при підрахунку кількості елементів при кожнім проході циклу ми додаємо до попереднього значення перемінної кількості N одиницю (1) (фактично як би загинаємо пальці, тобто вважаємо).

Як і перемінну S при підрахунку суми, так і перемінну N при підрахунку кількості ми обнуляемо, щоб не спотворився результат підрахунку.

Схематично алгоритм підрахунку кількості виглядає в такий спосіб:

N=0

У циклі підрахунок значень зміною кількості (фактично підрахунок поточного значення перемінної N) відбувається по наступному алгоритмі - до попереднього значення перемінної N додається одиниця, схематично це виглядає в такий спосіб:

Перший прохід циклу:

N=[0]+1,де [0] – початкове значення перемінної N привласнене їй до початку роботи циклу.

Другий прохід циклу:

N=[0+1]+1, де [0+1] – попереднє значення перемінної N привласнене їй при першому проході циклу.

Третій прохід циклу:

N=[0+1+1]+1, де [0+1+1] – попереднє значення перемінної N привласнене їй при другому проході циклу.

Четвертий прохід циклу:

N=[0+1+1+1]+1, де [0+1+1+1] – попереднє значення перемінної N привласнене їй при третьому проході циклу.

І т.д. - узагальнимо весь процес підрахунку кількості елементів у загальну формулу:

N=N +1

Якщо необхідно підрахувати кількість елементів по якійсь ознаці, то як і в попередньому пункті ми використовуємо команду умовного переходу (повний або не повний у залежності від умови), де і задаємо умову підрахунку.

Алгоритм рішення задачі:

Графічний засіб – блок-схема:    Псевдокод алгоритмічною мовою:

Порядок виконання роботи:

• Розробити алгоритм рішення задачі словесним методом та записати його в звіті;
• Побудувати блок-схему в редакторі AFCE;
• Ввести команди в символи блок-схеми;
• Замалювати блок-схему в звіті;
• Записати псевдокод програми рішення задачі;
• Представити рішення задачі в програмі AFCE викладачу.

Завдання №1: Скласти схему алгоритму визначення кількості позитивних і кількості негативних елементів в одномірному числовому масиві А(15):

Алгоритм рішення задачі – словесний засіб:

Алгоритм рішення задачі:

Графічний засіб – блок-схема:      Псевдокод алгоритмічною мовою:

Позначка про виконання завдання: _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Завдання №2: Скласти схему алгоритму обчислення суми елементів рядків двовимірного масиву MАС(9,5):

Алгоритм рішення задачі – словесний засіб:

Алгоритм рішення задачі:

Графічний засіб – блок-схема:      Псевдокод алгоритмічною мовою:

Позначка про виконання завдання: _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Контрольні питання:

1. Дайте визначення поняттю «масив»?
2. Які типи масивів Ви знаєте?
3. Назвіть основні характеристики масивів.
4. Дайте визначення характеристиці «ім'я масиву»?
5. Дайте визначення характеристиці «розмірність масиву»?
6. Дайте визначення характеристиці «розмір масиву»?
7. Для чого використовуються команди розгалуження (умовного переходу) в циклі при роботі з елементами масиву?
8. Які конструкції в блок-схемі описують операції по введені/виведенні елементів одновимірного масиву? На псевдокоді?
9. Які конструкції в блок-схемі описують операції по опису дій з елементами масиву за якоюсь умовою? На псевдокоді?
10. Які конструкції в блок-схемі описують операції по введені/виведенні елементів двовимірного масиву? На псевдокоді?
11. Як задаються операції по рядках, стовпцях двовимірних масивів?
12. Дайте визначення поняттю «вкладені цикли» в алгоритмі?

Висновок: ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Лабораторну роботу виконав студент____________________________________________________

                                                                                                                        ^{Підпис.                                                  Прізвище, ініціали}

Лабораторну роботу перевірив і прийняв викладач ________________________________________

                                                                                                                                                       ^{Підпис.                                   Прізвище, ініціали}

________________________                                           _______________________________

                               ^{Дата                                                                                                                                             Оцінка}