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

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

• пояснює: організацію даних у вигляді масивів та принципи опрацювання табличних даних;

• знає зміст понять: масив, елемент масиву, індекс та значення елемента;

• розпізнає: клас задач, що розв'язують з використанням табличних даних;

• уміє:

  • оголошувати змінні табличного типу;

  • створювати програми для введення та виведення елементів масивів;

  • програмувати опрацювання лише тих елементів масиву, що задовольняють певній умові;

  • програмувати обчислення суми, середнього арифметичного та кількості елементів масивів, що відповідають певній умові;

  • застосовувати алгоритми впорядкування для заданого масиву;

  • аналізувати результати виконання програм;

  • налагоджувати програму з використанням табличних величин.

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

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

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

Хід уроку

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

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

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

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

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

Система вказівок виконавця — це множина (сукупність) всіх вказівок, які може виконувати даний виконавець.

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

Властивості алгоритму: дискретність, визначеність, виконуваність, скінченність, результативність, масовість, ефективність.

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

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

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

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

Результативність алгоритму означає, що після закінчення виконання алгоритму обов’язково:

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

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

Ефективність алгоритму описує час виконання і об'єм ресурсів, необхідних для виконання алгоритму: чим менше часу (часова ефективність) і ресурсів (просторова ефективність), тим ефективність вища.

Дати відповіді на запитання і порівняти з очікуваним:

1. Що таке змінна в Ruby? Змінною називають названу область пам’яті, відведену для збереження даних, які використовують при виконанні програми.

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

3. Назвіть кілька основних типів даних в Ruby. Дійсні числа (Float), цілі числа (Integer), рядки (String), логічні величини (Boolean), символи (Symbol).

4. Назвіть конструкції мови програмування Ruby для опису повторень. while, until, for, each.

5. Як в мові програмування Ruby створити коментар? В Ruby коментарі записують від символа # до кінця рядка.

6. Чи обов’язково використовувати круглі дужки при записі коду виклику метода? Не обов’язково. Наприклад, код puts("Привіт!") і puts "Привіт!" еквівалентні за дією.

7. Що називають блоком у мові Ruby? Будь-який код всередині фігурних дужок:
   2.times{print"Це блок!"}
   Замість фігурних дужок можна використати слова do та end.

У разі потреби повторити основи мови програмування Ruby.

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

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

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

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

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

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

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

Мова Ruby є динамічно типізованою. Для масивів це означає: типи елементів масиву можна змінювати протягом виконання коду і для різних елементів по різному.

В Ruby для створення масиву можна використати розділений комами список елементів розміщений у квадратні дужки. Наприклад:

  [1, 2, 3] 
  ['один', 'два', 'три']
  [1,"два", [3,4]]

Як видно з останнього прикладу елементами масиву можуть бути дані різного типу. В тому числі і числа, і рядки тексту, і масиви одночасно.

1. Або створити порожній масив (наприклад, a = []), або ініціалізувати його певними значеннями (наприклад, a = [1, 2, 3]).

2. Порожній масив заповнити елементами з потрібними значеннями.

3. При потребі вивести масив (на екран, у файл) для наочної перевірки роботи коректності заповнення.

4. Опрацювати масив.

5. Вивести отримані результати.

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

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

Оператори й методи для роботи з масивами (s і t у позначеннях нижче)

• s.length або s.size — довжина масиву s;

• s.include?(x) або s.member?(x) — метод, що перевіряє приналежність значення x масиву s. Якщо масив s містить елемент зі значенням x то метод повертає значення true, інакше — false.

• s.empty? — метод повертає значення true якщо масив s не містить елементів, інакше — false.

• s[j] — повертає значення j-го елемента масиву s (нумерацію елементів масиву починають з нуля);

• s[j] = x — надання елементу з номером j масиву s значення x;

• s[i..j] — зріз з масиву s від елемента з індексом i до j-го елемента включно

• s[i, n] — масив з n елементами, що є зрізом з масиву s починаючи від елемента з індексом i;

• s.min — найменший елемент s;

• s.max — найбільший елемент s;

• s + t — результат «дописування» до масиву s масиву t;

• s*n — результат n-кратного повторення масиву s. Тут n — невід’ємне ціле число. При n = 0 результатом буде порожній масив.

• s.push(x) — додає елемент зі значенням x у кінець масиву s;

• s.clear — очищує масив;

• s.clone — створює копію масиву;

• s.count(x) — повертає кількість елементів зі значенням x;

• s.index(x) — повертає найменший iндекс елемента зі значенням x у масиві s. Повертає значення nil, якщо елемента з таким значенням не знайдено;

• s.insert(j,x) — вставляє на місце з індексом j елемент зі значенням x;

• s.pop(j) — повертає значення елемента з номером j, видаляючи його з масиву s;

• s.delete(x) — вилучає всі елементи з масиву s, що мають значення x. Повертає останне видалене значення або nil, якщо елемента з таким значенням не знайдено;

• s.reverse! — зміняює порядок елементів на зворотний змінюючи масив;

• s.sort — повертає новий масив, що є упорядкованою версією масиву s;

• s.sort! — упорядковує елементи масиву s змінюючи сам масив;

Способи створення та заповнення масиву (подано на прикладі одновимірного масиву a):

• cтворення масива із заздалегідь відомими значеннями
  a = [2, 4, 6, 8, 10]

• введення з клавіатури (подано на прикладі одновимірного масиву a з n елементами):

  (0..n-1).each do |i|
    a[i] = gets.chomp       # Зчитування рядків
  end
  
  (0..n-1).each do |i|
    a[i] = gets.chomp.to_i  # Зчитування цілих чисел
  end
  
  (0..n-1).each do |i|
    a[i] = gets.chomp.to_f  # Зчитування дійсних чисел
  end

• зчитування з файлу:

  a = []
  File.open("input.txt", "r") do |f| # відкрити файл input.txt для читання і
                                     # передати посилання на нього через змінну f
    f.each do |line|                 # для кожного рядка (line) з файла
      a.push(line)                   # додати рядок до масиву
    end
  end                                # при виході з блоку файл буде закрито автоматично

  або те саме одним рядком:
  
  a = File.readlines('input.txt')

• cтворення масива, значення елементів якого визначають згідно з формулою (далі подано приклади створення масиву з n елементів, значення j-го елемента якого дорівнює j ∙ (j + 1) − 1:

  a = []
  for j in (0..n-1) do
    a[j] = j*(j+1)-1
  end

  або так:

  a = []
  (0..n-1).each do |j|
    a[j] = j*(j+1)-1
  end

  або з використанням метода new класу Array:

  a = Array.new(n) { |j| j*(j+1)-1 }

• з використанням генератора випадкових чисел (далі подано приклад створення масиву з n випадкових чисел, що набувають значень з проміжку [x, y]:
  
  a = Array.new(n) { |j| rand(x..y) } або
  
  a = Array.new(n) { rand(x..y) }

Способи виведення елементів масиву

• Вказівка print(a) виводить елементи масиву a у квадратних дужках через кому. Наприклад, код
  
  a = [1, 2, 3]
  print(a)
  
  виведе:
  
  [1, 2, 3]

• Вказівка puts(a) виводить елементи масиву з ознакою кінця рядка після кожного. Наприклад, код
  
  a = [1, 2, 3]
  puts(a)
  
  виведе:
  
  1
  2
  3

• Виведення масиву в файл подамо прикладом запису значень елементів масиву a в окремі рядки файлу filename.txt:

  File.open("filename.txt", "w+") do |f|
    a.each { |element| f.puts(element) }
  end

  або:

  File.open("filename.txt", "w+") do |f|
    f.puts(a)
  end

Обчислення суми елементів масиву

n = 9; amax = 99; a = []
(0..n-1).each do |j|
  a[j] = rand(amax)   # надання елементу a[j] випадкового значення з діапазону [0, 99)
  print "#{a[j]} "
end
puts
s = 0
(0..n-1).each do |j|
  s += a[j]
end
puts "Сума цих чисел дорівнює #{s}"

n = 9; amax = 99; a = []
a = Array.new(n) { rand(amax) }
print "#{a}\n"
s = 0
a.each { |elem| s += elem }
puts "Сума цих чисел дорівнює #{s}"

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

n = 9; amax = 99
a = Array.new(n) { rand(amax) }
print "#{a}\n"
s = 0
a.each do |elem| 
  s += elem if elem % 2 == 0
end
puts "Сума парних чисел з поданих дорівнює #{s}"

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

n = 9; amax = 99
a = Array.new(n) { rand(amax) }
print "#{a}\n"
min = a[0]
(1..n-1).each do |j|
  min = a[j] if a[j] < min  
end
puts "Найменше з поданих чисел дорівнює #{min}"

В Ruby цю задачу можна розв’язати ще простіше за допомогою методу min класу Array:

n = 9; amax = 99
a = Array.new(n) { rand(amax) }
print "#{a}\n"
puts "Найменше з поданих чисел дорівнює #{a.min}"

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

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

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

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

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

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

Код програми мовою Ruby має такий вигляд.

n = 9; amax = 99
a = Array.new(n) { rand(amax) }    # заповнення масиву випадковими числами від 0 до 99
puts "Невпорядкований масив:"
print "#{a}\n"
(0..n-2).each do |j|
  l = j
  (j+1..n-1).each do |k|
    l = k if a[l] > a[k]
  end
  a[l], a[j] = a[j], a[l]          # міняємо значення елементів a[j] та a[l] місцями
end
puts "Результат впорядкування цього масиву такий:"
print "#{a}\n"

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

Рекурсивний алгоритм для впорядкування за неспаданням масиву зі значеннями індексів від l до r включно має такий вигляд:

1. Вибрати значення елемента масиву.
2. Значення елементів масиву, що більші за вибране, розташувати на місцях з номерами (індексами) більшими від індексу обраного значення, а ті, що не перевищують — на місцях з номерами меншими від індексу обраного значення. У результаті вибране значення матиме той номер j у масиві, що потрібно. Тому надалі відповідний елемент масиву буде незмінним.
3. Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.
4. Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.

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

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

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

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

і код програми.

n = 9
amax = 99
a = Array.new(n) { rand(amax) }
puts "Невпорядкований масив:"
print "#{a}\n"

def qsort(list)
  return [] if list.empty?                   # повернути порожній масив, якщо у масив порожній
  x = list.sample                            # випадковим чином вибрати значення елемента масиву list.
  left   = list.select { |elem| elem <  x }  # значення елементів масиву, що менші за вибране x, зберегти у масиві left
  center = list.select { |elem| elem == x }  # значення елементів масиву, що дорівнюють вибраному x, зберегти у масиві center
  right  = list.select { |elem| elem >  x }  # значення елементів масиву, що більші за вибране x, зберегти у масиві right
  qsort(left) + center + qsort(right)        # повернути масив, у якому елементи зі значенням x розташовано на своєму місці,
                                             # a ліворуч і праворуч від них знаходяться рекурсивно упорядковані масиви
                                             # Вказівку return можна не писати. У цьому випадку значення останнього 
                                             # обчисленого у тілі функції виразу і буде значенням функції
end

puts "Результат впорядкування цього масиву такий:"
print "#{qsort(a)}\n"

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

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

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

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

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

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

n = 9
amax = 99
a = Array.new(n) { rand(amax) } # створити масив з випадковим наповненням цілими числами від 0 до 99
puts "Невпорядкований масив:"
print "#{a}\n"

b = [0] * amax                  # створити масив з amax нулів
a.each { |x| b[x] += 1 }        # для кожного значення x з масиву а збільшити значення b[x] на 1

a = []                          # спорожнити масив

# для кожного додатного значення value елементів масиву b
#  створити масив [index]*value і долучити його до кінця масиву а 
b.each_with_index { |value, index| a += [index] * value if value > 0 }

puts "Результат впорядкування цього масиву такий:"
print "#{a}\n"

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

n = 9
amax = 99
a = Array.new(n) { rand(amax) }
puts "Невпорядкований масив:"
print "#{a}\n"
a.sort!
puts "Результат впорядкування цього масиву такий:"
print "#{a}\n"

(Бінарний) пошук заданого елемента
Розглянемо задачу пошуку номера елемента упорядкованої за зростанням послідовності {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. Завершити пошук, вважаючи його неуспішним.

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

У поданій далі програмі крім описаних вже змінних використано булеву змінну s (англійською search — шукати): s справджується, якщо шуканого номеру немає або пошук ще не завершено.

n = 9
amax = 99
a = Array.new(n) { rand(amax) }.sort!
puts "Впорядкований масив:"
print "#{a}\n"
b = rand(amax)
print "Серед елементів цього масиву значення #{b}"

s = true
j = 0
k = n-1
while (j <= k) and s do
  l = (j + k).div 2
  if a[l] == b
    s = false
  elsif a[l] < b
    j = l + 1
  else
    k = l - 1
  end
end
if not s
  puts " має елемент з індексом #{l}"
else
  puts " не має жоден елемент"
end

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

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

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

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

Текст упорядкував Москаленко Олег Іванович, вчитель спеціалізованої школи № 43 «Грааль» Солом’янського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 29.10.2018 по 02.11.2018.