Розробка уроку

Тема: табличні величини.

Мета:

Після вивчення матеріалу учень:

Обладнання: комп'ютери зі встановленими ОС та браузером.

Структура уроку

  1. Організаційний момент.
  2. Актуалізація опорних знань.
  3. Інструктаж з ТБ.
  4. Вивчення нового матеріалу.
  5. Закріплення вивченого матеріалу.
  6. Підбиття підсумків уроку.
  7. Домашнє завдання.
Хід уроку

1. Організаційний момент
Привітання з класом, знайомство з класом. Перевірка присутності учнів.

2. Актуалізація опорних знань.
Дати означення понять, виділені жирним шрифтом, і порівняти з очікуваним.

Алгоритмце запис скінченої послідовності вказівок, виконання яких призводить до розв'язання певної задачі.

Програмаце алгоритм, що написаний спеціальною мовою для реалізації на комп'ютері.

Компіляціяпереклад програми з мови програмування на мову команд, які може виконати комп'ютер.

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

Ідентифікаторце назва, яку надають об'єктам: змінним, сталим, функціям тощо.

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

// текст коментаря до кінця рядка

Величинаодиниця даних, якими оперує програма. Вона має такі властивості:

З кожною величиною (або її складовою для структурованої величини) пов'язана ділянка оперативної пам’яті, куди її під час роботи програми заносять та у якій зберегають. Цю ділянку визначено її адресою. Тут під адресою розуміють адресу першого байту з послідовновних щодо адресації байтів, відведених для збереження величини. Назва змінної слугує назвою цієї послідовності байтів під час виконання програми.

Зміннівид даних, значення яких дозволено змінювати протягом виконання програми.

Змінні можуть бути глобальними або локальними. Глобальні змінні досяжні з довільного місця сценарію. Область дії локальних змінних обмежено кодом функції, всередині якого оголошено ці змінні. При створенні сценаріїв JavaScript рекомендовано оголошувати змінні до їхнього використання та надавання початкових початкових. Це спрощує відлагодження сценаріїв і зменшує ймовірність помилки.

Оголошення змінної у JavaScript здійснюють таким чином:

var назва змінної1; // давніший варіант
let назва змінної2;

Відмінності між цими варіантами настільки тонкі, що початківці їх не відчувають. І досі збережено можливість створити змінну наданням значення без використання службових слів var чи let. Але лише за умови відсутності use strict у файлах кодів.

Оголошення сталої у JavaScript здійснюють таким чином:

const назва сталої;

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


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

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

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

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

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

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

Примітка. У мові Javascript з динамічною типізацією змінних тип змінної можна змінюти разом зі значенням. Тому й елементами масиву можуть бути різні за типом змінні.

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

Наприклад, а[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 — лишок.

Створення масиву

назва_масиву = new Array();

Розмір масиву буде визначено за результатами заповнення.

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

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

Примітка. У перших трьох прикладах елементам масиву надано числових значень, в останніх двох — рядків (програма мовою Javascript зчитуює і записує лише рядки). Для перетворення рядка у число використовують функцію Number, для перетворення числа у рядок — String.

Обчислення суми елементів масиву здійснюють, надавши деякій змінній початкового нульового значення, яке змінюють послідовним додаванням всіх елементів масиву у циклі — див. приклади для 1- і 2-вимірного масивів.

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

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

Визначення найменшого (найбільшого) елемента масиву здійснюють таким чином: змінній min (max) — найменшому (найбільшому) значенню з проглянутих — спочатку надають значення елемента масива з найменшим номером. Послідовно переглядаючи значення наступних елементів масиву при виявленні значення, меншого від min (більшого від max), надаємо змінній min (max) цього значення див. приклад.

Алгоритм, що упорядковує елементи масиву, характеризують:

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

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

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

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

Метод швидкого сортування
Основу цього алгоритму розробив у 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 цього алгоритму можна деталізувати:

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

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

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

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

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

При прямуванні n — довжини лінійного масиву — до нескінченності кількість виконуваних операцій при впорядкуванні (майже) пропорційна:
  • n2 — для методів впорядкування вибором найменшого елемента або бульбашки;

  • n log2n — для методів впорядкування Хоара або пірамідального чи злиттям, не описаних у цій розробці;

  • n + m — для методу обліку (див. далі) з m — кількістю елементів діапазону зміни значень елементів масиву.

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

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

Але як усталено ці методи працюють з елементами масиву як з рядками — див. приклад.

Для роботи з числовими значеннями потрібно використати аргумент методу sort — функцію двох аргументів, яка повертає:

— див. приклад.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Текст упорядкував Олександр Рудик.