1. З чого складаються програми?
2. Обчислити значення логічного виразу: (7+3 > 16–4*3)?
3. Обчислити значення логічного виразу: (–3 >= 5) || (7 < 9) && (0 < 3)?
4. Наведіть приклади ключових слів.
5. Які правила створення ідентифікаторів?
6. Що таке дужки блоків і що вони позначають?
7. Розпишіть конструкцію вказівки галуження.
8. Які вказівки повторення вам відомі?
9. Яким символом розмежовують вказівки у коді програми?
10. Назвіть типи простих даних ви знаєте?

Порівняти з очікуваними:

1. Програми складаються з вказівок (операторів, інструкцій).
2. TRUE.
3. TRUE.
4. if, else, int, float, const, sqrt.
5. Не можна вживати зарезервовані слова, кирилицю, пробіли.
6. { } позначають початок і кінець блоку вказівок.
7. if (умова) вказівка.
8. for (j=0; j<n; j++) {…}.
9. ; (крапка з комою).
10. Наприклад, real, int, float.

3. Інструктаж з ТБ
4. Вивчення нового матеріалу

Потреба запровадження табличних величин випливає з необхідності запам'ятовувати й опрацьовувати великий набір однотипних даних. Наприклад, при знаходженні середнього балу кожного учня класу з інформатики за чверть потрібно знаходити суму великої кількості оцінок. Як зберігати всі ці оцінки? Зарезервувати для цього 40 чи більше змінних? Це дуже незручно. Ось тут і приходить на допомогу такий структурований тип даних, як таблиця або масив (дві назви одного й того самого об'єкта).

Масив — згруповані за місцем розташування у пам'яті величини одного типу, що мають одну назву (ідентифікатор) і різні порядкові номери (індекси). Це поняття програмування відповідає математичним поняттям послідовності й таблиці (матриці).

Елемент масиву — одна з величин, що утворюють масив. Це поняття програмування відповідає математичному поняттю елемента послідовності чи матриці.

Індекс масиву — величина перелічуваного (зазвичай цілого) типу, яка (сукупність яких) вказує на конкретний елемент масиву. Це поняття програмування відповідає математичному поняттю номера елемента послідовності чи номеру рядка/стовпчика таблиці (матриці). У мові С++ найменше значення індексу — 0.

Масив має такі властивості:

• тип елементів (масиву);
• назва (ідентифікатор) — одна й та сама для всіх елементів масиву;
• розмірність — кількість номерів (індексів), необхідних для визначення розташу­вання елемента у масиві;
• діапазони зміни номерів (індексів).

Cукупність розмірності й діапазонів називають формою масиву.

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

Наприклад, а[3] — 3-тій елемент масиву а, с[j] — j-ий елемент масиву с.

Елемент масиву може мати і тип простої (неструктурованої) величини і складений тип (масиву, рядка тощо), тобто може існувати масив масивів, масив рядків тощо. Глибину вкладеності (а значить, і кількість індексів) необмежено, але загальну довжину структури обмежено. У пам'яті ПК всі елементи масиву зберігають послідовно: при переході від молодших до старших адрес першим змінюється індекс, записаний останнім (праворуч).

Порядок роботи з масивом

1. У розділі описів вказати назву, розмір і тип елементів масиву. Це забезпечить (на етапі завантаження програми) виділення потрібного об'єму оперативної пам'яті для зберігання значень елементів .
2. Заповнити комірки пам'яті, виділені для елементів масиву, потрібними значеннями.
3. При потребі вивести масив (на екран, у файл) для наочної перевірки роботи коректності заповнення.
4. Опрацювати масив.
5. Вивести отримані результати.

Під час розв'язування задач переважно використовують одновимірні та двовимірні масиви.

Одновимірний масив інакше називають лінійним масивом або вектором. Кожному його елементу ставлять у відповідність один індекс. У математиці лінійному масиву відповідає поняття послідовності, а номеру члена послідовності — індекс масиву.

Двовимірний масив інакше називають таблицею або матрицею. Кожному його елементу ставлять у відповідність два індекси: номер рядка та номер стовпчика. Прикладом двовимірного масиву є шахівниця.

Примітка. Використання масивів розмірності 2 і більше зумовлено лише міркуваннями зручності для програмістів. Наприклад, існує взаємно однозначна відповідність j = kn + l між індексом j — у межах від 0 до (mn – 1) і парою індексів (k, l) при k — у межах від 0 до (m – 1), l — у межах від 0 до (n – 1). А саме: при діленні j на n маємо: k — частка, l — лишок.

Форма опису масиву

тип_елемента назва_масиву [кількість значень індекса₁]…;

Тут трикрапка позначає або порожній символ, або кількість значень індекса₂ у квадратних дужках, або кількість значень індекса₂ у квадратних дужках і кількість значень індекса₃ у квадратних дужках і т.д.

Масиви одного типу можна описувати в одному рядку через кому. Для багатовимірних масивів кожен індекс береться у квадратні дужки []. Наприклад:

int  a1[9], a2[99];
real a3[3][5];

Тут описано масив a3, який має 3 рядки та 5 стовпчиків. Цей опис можна тлумачити як одновимірний масив з 3 елементів, кожен із яких є одновимірним масивом з 5 елементів.

Граничні значення індексів (у квадратних дужках в описі масивів) вказують явно або як вирази з попередньо визначених змінних або сталих.

Примітка. Подані далі (за гіперпосиланнями) програми бажано не лише споглядати, але й протестувати, використавши вказане вчителем середовище програмування.

Способи заповнення масиву:

• використовуючи ініціалізацію:

  int  a[9] = {1,2,4,8,0,3,6,9,5}; 
  char b[5] = {H,e,l,l,o,\o};
  char c[5] = "Hello";
  real d[2][3] = {2,3,4,5,6,7};     
  real e[2][3] = {{2,3,4},{5,6,7}};

• з клавіатури;
• з використанням генератора випадкових чисел rand ();
• з файлу;
• за формулою.

• залежністю часу роботи від кількості елементів масиву;
• залежністю додаткової пам'яті від кількості елементів масиву;
• cтійкістю роботи.

Впорядкування елементів масиву вибором найменшого (найбільшого) елемента (опис подано для лінійного масиву з діапазоном індексу 0..n)

Змінюючи j від 0 — найменшого значення індексу — до (n – 1) — найбільшого значення індексу, зменшеного на 1, — робимо таке:

• визначаємо номер l найменшого (найбільшого) елемента для індексів у межах від j до n включно;

• міняємо місцями значення елементів з індексами j та l. У результаті такої заміни на місце з номером (індексом) j стане те значення, що потрібно.

Подамо для наочності ілюстрацію такого впорядкування 10-елементного масиву, запозичену зі сторінки Вікіпедії.

Тут червоним тлом виділено те значення, яке серед елементів з номером від j до n вважають найменшим у поточний момент виконання алгоритму, блакитним — значення поточного елемента масиву, яке порівнюють з тим, що наразі вважають найменшим, жовтим — ті значення, які вже стоять на потрібному місці. Див. приклад програми мовою С++.

Метод «бульбашок» або упорядкування обміном полягає у порівнянні двох сусідніх елементів. Якщо один з елементів, не відповідає критерію упорядкування, то ці два елементи міняють місцями. Прохід списком продовжують до тих пір, поки дані не буде упорядковано.

Алгоритм отримав свою назву від того, що процес упорядкування нагадує поведінку бульбашок повітря у резервуарі з водою. Для кращого розуміння див. ілюстрацію упорядкування 10-елементного масиву, запозичену за такою адресою: https://cdn.tproger.ru/wp-content/uploads/2017/09/BubbleSort.gif:

і код програми мовою С++.

Упорядкування включенням — див. приклад — простий алгоритм упорядкування на основі порівнянь, що має низку переваг:

• простота реалізації;
• ефективний на коротких та частково упорядкованих масивах;
• на практиці ефективніший за більшість квадратичних алгоритмів;
• стабільність.

Більшість людей при упорядкуванні колоди гральних карт дотримуються сценарію, схожого на алгоритм упорядкування включенням.

Метод швидкого сортування
Основу цього алгоритму розробив у 1962 році британський учений Чарлз Ентоні Річард Гоар (Charles Antony Richard Hoare). Рекурсивний алгоритм для впоряд­кування за неспаданням масиву зі значеннями індексів від l до r включно має такий вигляд:

1. Вибирати значення елемента масиву.

2. Значення елементів масиву, що не менші за вибране, розташувати на місцях з номерами (індексами) більшими від індексу обраного значення, а ті, що не перевищують — на місцях з номерами меншими від індексу обраного значення. У результаті вибране значення матиме той номер j у масиві, що потрібно. Тому надалі відповідний елемент масиву буде незмінним.

3. Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.

4. Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.

Пункт 2 цього алгоритму можна деталізувати:

• надати змінним i, j значення l, r відповідно;
• збільшувати значення l, поки l-й елемент менший від обраного;
• збільшувати значення r, поки r-й елемент більший від обраного;
• при l < r:
  • поміняти місцями елементи з індексами l і r;
  • збільшити значення l на 1;
  • зменшити значення r на 1.

Рекурсивність алгоритму означає виклик цього алгоритму в ньому самому — див. кроки 3–4. На малюнку нижче подано частину схеми впорядкування.

Тут кольоровими кругами позначено вибрані значення елементів масиву. Після переставлянь навколо них ці значення надалі залишаються нерухомими у масиві. Спочатку буде впорядковано елементи, менші від значення, позначеного зеленим кольором, потім — менші від значення, позначеного червоним кольором, ще пізніше — менші від значення, позначеного синім кольором.

Примітка. Поданий вище запис стане алгоритмом лише після того, як буде деталізовано вибір значення. У багатьох описах алгоритму можна зустріти вибір елемента з найменшим чи з найбільшим номером. Розглянемо спробу впорядкувати вже впорядкований масив при такому виборі. Глибина занурення — кількість послідовних викликів рекурсивного алгоритму без виходу з нього — буде майже збігатися з довжиною масиву. Останнє може призвести до переповнення стеку частини оперативної пам'яті, куди програма заносить дані про виклик програмі та функцій, їхні аргументи, точку повернення тощо. А переповнення стеку означає аварійне завершення роботи. Який би не був детерміністичний (без випадковостей) вибір значення (наприклад, із середини масиву), завжди можна вказати вхідні дані, для яких глибина занурення для цих вхідних даних лише на 1 відрізнятиметься від довжини масиву. Тому вибір потрібно робити з використанням генератора випадкових чисел. І в цьому випадку можливе переповнення стеку, але ймовірність цієї події настільки мала, що аварійне припинення роботи зазвичай не відбувається.

Проаналізуйте на відповідність опису ілюстрацію для вибору правого краю (елемента з найбільшим номером), запозичену із сайту http://uk.wikipedia.org/wiki

Див. приклад програми мовою С++.

Іншими словами про це кажуть так: часові складності алгоритмів дорівнюють відповідно O(n²), O(n log₂n) і O(n + m). У більшості випадків доречно використати саме швидкий метод Хоара, хоча бувають випадки, коли для розв'язування поставленої задачі (не лише впорядкування) потрібно використати, наприклад, метод злиття, або використати метод обліку, щоб задовольнити обмеження на час виконання програми. Обидва випадки зустрічалися на ІІІ (міському) етапі Всеукраїнської учнівської олімпіади з інформатики у місті Києві.

Насправді досвідчені програмісти не програмують методи упорядкування окрім тих випадків, у яких упорядкування є основою розв'язання істотно складнішого алгоритму. А для упрядкування використовують вбудовані методи (функції) - див. приклад використання qsort, у якому при зверненні до цієї функції:

qsort(a, n, sizeof (int), (int(*) (const void *, const void *)) f);

маємо

• a — масив для упорядкування;
• n — кількість елементів масиву;
• sizeof(int) — розмір у байтах кожного елемента масиву;
• f — функція порівняння.

Формат опису функції порівняння такий:

тип назва (const void * x, const void * y) {… return …;}

Функція має повертати такі значення:

• від'ємне, якщо x має передувати y;
• 0, якщо x збігається з y;
• додатне, якщо y має передувати x.

Метод обліку передбачає використання окремого масиву з нульовими початковими значеннями, який після проглядання масиву, що підлягає впорядкуванню, містить інформацію про те, скільки разів те чи інше значення зустрілося серед значень елементів масиву — див. приклад.

Бінарний пошук заданого елемента
Розглянемо задачу пошуку номера елемента упорядкованої за зростанням послідовності {a_n}, який (елемент) має значення b. Зазвичай для цього викорис­товують двійковий (бінарний) пошук. Він полягає у послідовному поділі (приблизно) навпіл діапазону номерів, у якому проводять пошук. На початку виконання цього алгоритму:

j — менша межа діапазону номерів, на якому шукають потрібний номер, дорівнює меншій межі діапазону номерів масиву;

k — більша межа діапазону номерів, на якому шукають потрібний номер, дорівнює більшій межі діапазону номерів масиву.

Алгоритм бінарного пошуку має такий вигляд:

1. Поки справджується нерівність j ≤ k, робити таке:

   • надати значення змінній l = [(j + k)/2] — знайти індекс l, що поділяє досліджуваний діапазон навпіл;

   • якщо a_l = b, завершити пошук зі знайденим номером l;

   • якщо a_l < b, надати значення змінній j = (l + 1), тобто вибрати для подальшого пошуку діапазон, розташований правіше від l;

   • якщо a_l > b, надати значення змінній k = (l – 1), тобто вибрати для подальшого пошуку діапазон, розташований лівіше від l.

2. Завершити пошук, вважаючи його неуспішним.

Тут квадратні дужки (у першій дії всередині циклу) позначають операцію визначення цілої частини. Див. приклад.

5. Закріплення вивченого матеріалу

1. Що таке масив?
2. Які властивості має масив?
3. Що таке форма масиву?
4. Як описують масив?
5. Які методи впорядкування лінійних масивів Ви знаєте?
6. У чому полягає впорядкування масиву швидким методом Хоара?
7. У чому полягає бінарний пошук?

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання

1. Вивчити матеріал уроку.
2. Написати програму розв'язання такої задачі: заповнити лінійний масив випадковим чином і визначити, скільки разів досягається найбільше значення у даному масиві та найменший порядковий номер (індекс) для такого найбільшого значення.

Текст упорядкувала Іванова Ірина Павлівна, вчитель школи І-ІІІ ступенів № 306 Деснянського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 30.10.2017 по 04.11.2017.