Тема: cпособи реалізації структур даних. Застосування на практиці різних структур даних. Відмінність між формальними і фактичними параметрами. Поняття масиву, стека, черги, хешу мовою Ruby.

Мета:

• ознайомитися з описом використання різних структур даних мовою Ruby: вкладені колекції, масив, хеш;

• сформувати в учнів поняття: сталі, змінні, типи даних, структури даних.

По завершенню вивчення учень:

• має уявлення про:
  • комп'ютерну програму та її структуру мовою Ruby;
  • вказівки й алгоритми роботи у середовищі програмування;
  • поняття величини та її типу;


• yміє:
  • обирати ефективний алгоритм та обґрунтувати свій вибір;
  • оформлювати блочні структури;
  • бути економним щодо кількості операцій і використання пам’яті;


• розуміє, як застосовувати на різні типи даних для різних типів задач.

Обладнання: комп’ютери зі встановленими ОС та компілятором мови Ruby, бажано середовищем програмування (наприклад, Ruby Mine) або стійким сполученням з інтернетом для роботи з online-сервісами.

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

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

Хід уроку

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

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

2. Актуалізація опорних знань

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

• назва (ідентифікатор) — послідовність літер латиниці, цифр і нижнього підкреслювання «_», на початку — обов'язково літера;

• тип — визначає обсяг відведеної пам'яті, можливі дії, правила тлумачення бітів пам'яті та множину допустимих значень;

• розмірність — проста або складена (структурована);

• значення — елемент множини допустимих значень величини.

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

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

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

У мові Ruby кожне значення має тип, але тип змінної не оголошують. На основі наданого змінній значення інтерпретатор Ruby визначає, якому типу воно належить, і запам’ятовує його. У мові Ruby використовують динамічну типізацію об'єктів: тип об’єкта можна змінити при виконанні коду. Наприклад, при наданні значення іншого типу.

Найуживаніші вбудовані типи даних мови Ruby:

• логічний (булевий), що набуває значень True або False;
• ціле число;
• число з рухомою крапкою (десятковий дріб);
• звичайний дріб;
• комплексне число;
• рядок тексту (послідовності символів);
• байт і масив байтів (наприклад, зображення у форматі jpeg);
• масив — набір елементів;
• хеш — набір елементів під ключами;
• вкладені колекції — набір елементів з під наборами елементів;

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

• .to_i — перетворює рядок або число з рухомою крапкою в ціле число;
• .to_f — перетворює аргумент у число з рухомою крапкою;
• .to_s — перетворює аргумент у рядок.

Неявне перетворення типу даних буде здійснено при використанні в одному виразі різних типів даних. Наприклад, при додаванні цілого і дробового чисел, числа й рядка. У першому випадку буде отримано число з рухомою крапкою. У другому випадку інтерпретатор Ruby повідомить про помилку.

Надання значення:

• каскадне (наприклад, x = y = z + 0);
• множинне (наприклад, x, y, z = 1, 2, 3).

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

Процедура — підпрограма, призначена лише для виконання певних дій.

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

У Ruby усі підпрограми є функціями, що можуть повертати об'єкт будь-якого типу (число, рядок, список тощо). Якщо код функції не містить вказівки return або під час виклику функції інтерпретатор не натрапляє на неї, функція повертає значення nil (ніщо).

В описі функції необхідно:

• вказати її назву;
• описати її аргументи (не обов'язково);
• описати програмний код;
• описати повернення результату (не обов'язково).

3. Вивчення нового матеріалу
Аргументи (параметри) функції поділяють на формальні та фактичні.

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

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

def max2(a, b)
  if a>b
     puts a
  else
     puts b
  end
end

max2(2, 3) # 3

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

Щоб обчислити функцію, її потрібно викликати з фактичними аргументами, тобто підставити фактичні параметри замість формальних у шаблон функції. Лише після цього будуть виконані вказівки тіла функції. Така операція копіює не значення змінних (або об’єктів), а їхні адреси (посилання) у пам’яті.

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

def f(a)
  a += 1
end

b = 1
f(b)
puts b  # 1

Пояснення: у момент виклику функції f формальний параметр a і фактичний аргумент b посилаються на один об'єкт у пам'яті, що належить до цілого типу. Після виконання вказівки a = 1, формальний параметр буде посилатися вже на інший об'єкт цілого типу зі значенням 2, а фактичний аргумент залишиться незмінним. Наступний приклад зі зміною значення:

def g(a)
  a.push(2) # 
end

b = [1]
g(b)
print(b) # [1, 2]

Пояснення: у момент виклику функції g і формальний параметр a, і фактичний аргумент b посилаються на один і той же список (змінюваний тип). Після виконання вказівки a.append(1), формальний параметр a і фактичний аргумент b буде доповнено елементом 1.

Примітка. У Ruby змінюваність (mutability) є властивістю екземпляра, а не цілого класу. Цей екземпляра можна зробити незмінним, викликавши метод freeze. Стан щодо змінюваності визначають за допомогою методу frozen?

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

тобто

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

def f(p1:, p2:, p3:)
  puts p1-p2
end

a1=1
a2=2
a3=3

f(p1: a1, p2: a2, p3: a3) # -1
f(p3: a3, p2: a1, p1: a2) #  1

Структура даних — це спосіб організації даних і операцій з ними.

Відповідним чином побудовані структури даних надають можливість оптимізувати використання машинного часу й пам’яті комп’ютера. У Ruby передбачено 2 вбудованих типи для структур даних: список і хеш (hash).

Список (array) — структура даних, що втілює математичне поняття змінюваної послідовності з цілими невід'ємними індексами (номерами).

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

Cтек (stack) — структура даних, що є сукупністю елементів і в якій останній доданий елемент буде вилучено першим.

Інакше кажучи, діє принцип: «останнім увійшов, першим вийшов». Описані методи надають можливість використання списку s як стеку:

• щоб додати новий елемент , використовують метод push();
• щоб видалити елемент, використовують метод pop();

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

Черга (queue) — структура даних, що є сукупністю елементів і в якій перший доданий елемент буде вилучено першим.

Інакше кажучи, діє принцип: «першим увійшов, першим вийшов»:

• щоб додати новий елемент, використовують метод push();
• щоб видалити елемент, використовують метод delete_at(0)

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

Хеш (hash, асоціативний масив) — структура даних, що містить сукупність пар ключ-значення.

Хеш можна утворити, записавши у фігурних дужках { } через кому кожну пару: ключ => значення. І як ключі, і як значення пар асоціативного масиву можна використовувати будь-які типи. Якщо стан об'єктів-ключів змінився, то необхідно викликати метод .rehash. У відповідному прикладі ключами хешу h) є два масиви a1 і a2. Одному з них (a1) було змінено нульовий елемент (з "а" на "я"). Після цього доступ до значення було втрачено. Після виконання методу .rehash все встало на свої місця.

Способи створення асоціативного масиву

• з одновимірного масиву за допомогою методів * і Hash;

• з двовимірного масиву з елементами вигляду:
  [[ключ₁, значення₁], [ключ₂, значення₂], [ключ₃, значення₃], …]
  перетворенням у одновимірний методом flatten;

• з двовимірного масиву з елементами вигляду:
  [[ключ₁, ключ₂, ключ₃, …] [значення₁], значення₂, значення₃…]]
  перетворенням у одновимірний методами transpose (транспонування) і flatten;

• наданням значень.

Методи роботи з асоціативними масивами:

• отримання масиву ключів або значень методами keys і values;
• зміна місцями ключів і значень методом invert;
• злиття масивів методами merge або merge!;
• визначення розміру методом size;
• видалення пари за ключем методом delete;
• видалення довільної пари методом shift;
• перетворення в індексний масив методом to_a;
• перетворення в індексний масив з упорядкуванням методом sort;
• пошук максимума й мінімума за ключем методами max i min;
• пошук максимума й мінімума за значенням методами max_by i min_by;
• визначення, чи порожній кеш методом empty?;
• визначення масиву ключів методом keys;
• визначення наявності ключа методами key?, member? і .has_key?;
• визначення масиву значень методом values;
• визначення наявності значеня методом value? i has_value?.

Ітератори асоціативних масивів:

• find_all — пошук всіх елементів, які задовольняють певній умові;
• map — зміна всіх елементів за певним алгоритмом;
• inject — складання, множення і агрегація елементів масиву

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

Особливості роботи ітераторів з асоціативними масива порівняно з індексними масивами:

• результатом є двовимірний масив;
• лічильником є масив вигляду [ключ, значення];
• можна розгорнути масив вигляду [ключ, значення] у дві змінні;
• в ітераторі inject розгорнути масив не вийде.

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

4. Інструктаж з ТБ
5. Вироблення практичних навичок

Створити програми для розв'язання таких задач.

1. Зчитати 6 цілих чисел. Розмістити парні числа на початку списку, непарні — в кінці.

2. Заповнити випадковими дійсними числами різного знаку список з 10 елементів. Отримати новий список з додатних елементів списку

3. Заповнити випадковими невід'ємними цілими числами від 0 до 5 включно список з 20 елементів. Видалити зі створеного списку списку елементи, що належать проміжку [2, 4].

4. Заповнити випадковими цілими числами від −15 до 15 включно список з 10 елементів. Знайти суму модулів елементів списку, що розташованих після першого від’ємного.

5. Заповнити випадковими цілими числами від 0 до 19 включно список з 5 елементів. Обчислити суму всіх цифр елементів списку.

6. Створити словник з 5 пар такого вигляду: прізвище (на власний вибір) : оцінка (у початковий момент 0). Надати оцінкам випадкових значень від 1 до 12 включно. Вивести значення середнього арифметичного оцінок і прізвища тих, у кого середній бал вищій, ніж середній бал по групі.

7. Створити асоціативний масив school, наповнити його даними, які б відображали кількість учнів в різних класах початкової школи: 1а, 1б, 2а, 2б, … , 4б і вивести його. В усіх класах змінити кількість учнів на 1 чи 2 і знову вивести дані. Обчислити загальну кількість учнів у школі і вивести її значення.

8. Використавши стек, перевірити, чи правильно розставлені дужки у заданому виразі.

9. Змоделювати відповідь на повідомлення прізвища:
   • при зверненні уперше: «Спасибі, що вибрали саме нас!»
   • при повторному зверненні: «Раді знову вас бачити!»
   При введенні рядка «exit» програма має припинити роботу.

10. За квитками на прем'єру нового мюзиклу вишикувалася черга з N глядачів, кожний з яких хоче купити один квиток. На всю чергу працює лише одна каса, тому продаж квитків йшов дуже повільно, приводячи глядачів у відчай. Найкмітливіші швидко помітили, що, як правило, декілька квитків в одні руки касир продає швидше, ніж коли ці самі квитки продають по одному. Тому вони запропонували декільком людям, що стоять підряд, віддавати гроші першому з них, щоб він купив квитки на всіх. Але для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки. Тому домовитися таким чином між собою могли лише двоє або троє глядачів. Відомо, що на продажу j-ій людині з черги одного квитка касир витрачає A_j секунд, на продаж двох квитків — B_j секунд, трьох квитків — C_j секунд. Написати програму, яка підрахує мінімальний час, за який можна обслужити усіх глядачів. Звернути увагу, що квитки на групу людей, що об'єдналися, завжди купує перший з них. Також ніхто в цілях прискорення не купує зайвих квитків.
    
    Формат вхідних даних: Спочатку вводять число N — кількість глядачів у черзі (3 ≤ N ≤ 5000). Далі йде N трійок натуральних чисел A_j , B_j , C_j. Кожне з цих чисел не перевищує 999 999 999. Людей у черзі нумерують, починаючи з 0, від каси.
    
    Формат вихідних даних. Вивести одне число — мінімальний час у секундах, за який можна обслужити N глядачів.
    
    Вказівка до виконання. Ефективні алгоритми комбінаторики як правило пов'язані з рекурентними співвідношеннями. Немає необхідності запам'ято­вувати всі вхідні дані.

Порівняти отримані розв'язання з демонстраційними: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

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

7. Домашнє завдання
Вивчити навчальний матеріал уроку. Доробити при потребі програми.

Текст упорядкувала Мазур Наталія Іванівна, вчитель школи № 104 Оболонського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 26.11.2018 по 30.11.2018.