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

• ознайомитися з описом використання різних структур даних мовою Python: список, словник, кортеж, стек, черга;

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

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

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


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


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

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

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

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

Хід уроку

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• int() — перетворює рядок або число з рухомою крапкою в ціле число;
• float() — перетворює аргумент у число з рухомою крапкою;
• str() — перетворює аргумент у рядок.

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

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

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

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

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

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

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

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

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

3. Вивчення нового матеріалу

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

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

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

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

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

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

Незмінювані об'єкти (immutable):

Змінювані об'єкти (mutable):

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

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

Списки можуть копіюватися, коли результат операції присвоюється іншій змінній.

• додавати нові елементи до списку;
• видаляти наявні елементи зі списку;
• замінювати елементи списку.

Символ у рядку змінити не можна, а елемент списку — можна. При спробі змінити один елемент рядка буде виведено повідомлення про помилку. Є можливість замінити зріз списку або створити додаткову змінну посилання на наявний список.

Способи виведення списку:

• print(a) — виводить елементи списку a у квадратних дужках через кому;

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

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

Вбудовані методи списків

• append(x) — додає елемент зі значенням x в кінець послідовності;

• clear — очищує список;

• copy — створює копію списку;

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

• extend(s) — розширює список, додаючи до кінця поточного списку список s;

• index(x[,j0[,j1]]) — повертає найменший iндекс елемента зі значенням x [для номерів елементів від j₀ [до j₁]], породжує виключення ValueError, якщо елемента з таким значенням не знайдено;

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

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

• remove(x) — вилучає елемент з найменшим iндексом серед тих, що мають значення x, породжує виключення ValueError, якщо елемента з таким значенням не знайдено;

• reverse() — змінює порядок елементів на зворотний;

• sort([f]) — упорядковує елементи з можливістю використання власної функції порівняння f

— див. приклади використання.

Створення порожнього списку з наступним заповненням його випадковими числами дуже зручне для створення тестів — див. приклад.

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

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

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

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

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

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

Завдання 1.

1. Створити два довільних списки.
2. Видалити з першого списку другий елемент.
3. Вивести змінений список на екран.
4. Змінити у другому списку останній об'єкт.
5. Вивести змінений список на екран.
6. Створити новий список злиттям наявних.
7. Вивести отриманий список на екран.
8. Отримати зріз створеного списку, що містить частини обох початкових списків.
9. Вивести значення зрізу.
10. Додати до зрізу два елементи: один на початок, інший — у кінець.
11. Порівняти створену програму з демонстраційним розв'язанням.

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

Для його зберігання буде використано менший розмір (у байтах), ніж для списку тієї самої довжини. Розглянемо приклади роботи з кортежами:

• створення порожнього кортежу;
• створення кортежу із заданим вмістом — варіанти 1 і 2;
• отримання значень елементів кортежу;
• видалення кортежу.

Але видалення елементів з кортежу неможливе.

Запровадимо теоретичне поняття (поза описом мови Python).

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

Геш-таблиця може містити у собі деякий масив H, елементами якого є пари (геш-таблиця з відкритою адресацією) або списки пар (геш-таблиця з ланцюжками).

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

Колізія — cитуація, коли для різних ключів отримують одне й те саме значення геш-функції.

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

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

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

Інакше кажучи, словник — втілення мовою Python поняття геш-таблиці. Можна провести аналогію зі спрощеним словником. Наприклад, англо-українським, у якому для кожного англійського слова є українське слово-переклад: cat — кішка, dog — собака, table — стіл тощо. Якщо такий словник описувати мовою Python, то англійські слова будуть ключами, а відповідні українські — їхніми значеннями.

Опис справжнього добротного словника передбачає відповідність слову однієї мови множини слів іншої мови. Інколи у таких слів-відповідників може бути більше десяти. І зворотній словник (для анго-українського — україно-англійський) має таку саму структуру.

Синтаксис словника мовою Python має такий вигляд:

{ключ : значення, ключ : значення, ключ : значення, …}

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

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

назва словника[ключ] = значення

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

Видалення елемента словника або самого словника здійснюють за допомогою функції del — див. приклад.

Словники неможливо об’єднувати за допомогою знака «+». Якщо користувач не зацікавлений у збереженні оригінальної версії словника, для об'єднання двох словників можна використовувати метод update — див. приклади 1 і 2. Інакше потрібно використати злиття — див. приклади 1 і 2.

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

Вбудовані методи словників

• dict.clear() — очищує словник;

• dict.copy() — повертає копію словника;

• dict.fromkeys(seq[, value]) — створює словник з ключами з seq та значенням value (як усталено None);

• dict.get(key[, default])(x) — повертає значення ключа, а якщо його немає, то повертає default (як усталено None)

• dict.items() — повертає пари (ключ, значення);

• dict.keys() — повертає ключі в словнику;

• dict.pop(key[, default]) — видаляє ключ і повертає значення. Якщо ключа немає, повертає default (як усталено породжує виключення);

• dict.popitem() — видаляє і повертає пару (ключ, значення). Якщо словник порожній, породжує виключення KeyError;

• dict.setdefault(key[, default]) — повертає значення ключа, але якщо його немає, то не породжує виключення, а створює ключ зі значенням default (як усталено None);

• dict.update([other]) — обновляє словник, додаючи пари (ключ, значення) із other. Якщо є пари в dict i other з одним ключем, значення буде взято з other.Повертає None (не новий словник!);

• dict.values() — повертає значення у словнику.

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

Завдання 2.

1. Створити словник з парами клас-чисельність класу (не менше 10 пар).
2. Ввести назву класу.
3. Вивести чисельність учнів цього класу.
4. Внести зміни до словника:
   • у трьох класах зменшити кількість учнів;
   • утворити два нових класи;
   • розформували (видалити) один класів.
5. Вивести вміст словника на екран.
6. Порівняти створену програму з демонстраційним розв'язанням.

Множина (set) — структура даних, що втілює математичне поняття множини — невпорядкованої сукупності неповторюваних елементів.

Множини можуть містити значення будь-якого типу.

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

Додавання елементів можна здійснити двома способами:

• метод add приймає один аргумент будь-якого незмінного типу і додає його в множину, якщо такого елемента там ще немає;

• метод update приймає один аргумент множину і додає всі елементи цієї множини до даної множини.

— див. приклад. Метод update еквівалентний виклику add для кожного елемента множини-параметра.

Видалення елементів з множини можна здійснити використавши один з таких методів: discard, remove, pop.

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

Метод remove так само приймає одине значення як аргумент і також видаляє це значення з множини. Але такого значення немає у множині, метод remove видає помилку KeyError — див. приклад

Метод pop видаляє одне значення з множини і повертає його. Для множини — це невпорядкованого набору — поняття останнього елемента немає, тому важко передбачити, який елемент буде вилучено методом pop. Спроба виклику pop для порожньої множини створить виняток KeyError.

Метод clear видаляє всі елементи множини, перетворюючи її на порожню. Це еквівалентне наданню значення = set(), яке створить нову порожню множину і замінить посилання на неї у змінній — див. приклад.

Перевірку належності до множини здійснюють за допомогою операції in — див. приклад.

Операції з множинами:
| — об'єднання;
& — перетин;
- — різниця;
^ — симетрична різниця — див. приклад

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

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

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

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

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

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

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

6. Створити словник з 10 пар такого вигляду:
   
   прізвище (на власний вибір) : оцінка (у початковий момент 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. Домашнє завдання
Вивчити навчальний матеріал уроку. Доробити при потребі розв'язання задач.

Текст упорядкувала Стеценко Антоніна Іванівна, вчитель Технічного ліцею Дніпровського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 29.10.2018 по 02.11.2018.