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

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

Мета:

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

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

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

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

Хід уроку

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ключ — значення,
тобто
назва формального параметра — назва фактичного аргумента.

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

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

Відповідним чином побудовані структури даних надають можливість оптимізувати використання машинного часу й пам’яті комп’ютера. У Python передбачено 4 вбудованих типи для структур даних: список (list), кортеж (tuple), словник (dictionary), множина (set).

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

Список можна утворити, записавши у квадратних дужках [ ] через кому значення або назви величин. Списки можуть містити об'єкти різних типів. Навіть інші списки. В останньому випадку, списки називають вкладеними — див. приклад.

Списки можна поєднувати і повторювати — див. приклад.

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

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

При роботі зі списками інші списки не обов'язково створювати, можна обмежитися зміною початкового списку:

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

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

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

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

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

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

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

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

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

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

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

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

Завдання 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завдання 2.

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

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

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

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

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

— див. приклад. Метод 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-ій людині з черги одного квитка касир витрачає Aj секунд, на продаж двох квитків — Bj секунд, трьох квитків — Cj секунд. Написати програму, яка підрахує мінімальний час, за який можна обслужити усіх глядачів. Звернути увагу, що квитки на групу людей, що об'єдналися, завжди купує перший з них. Також ніхто в цілях прискорення не купує зайвих квитків.

    Формат вхідних даних: Спочатку вводять число N — кількість глядачів у черзі (3 ≤ N ≤ 5000). Далі йде N трійок натуральних чисел Aj , Bj , Cj . Кожне з цих чисел не перевищує 999 999 999. Людей у черзі нумерують, починаючи з 0, від каси.

    Формат вихідних даних. Вивести одне число — мінімальний час у секундах, за який можна обслужити N глядачів.

    Вказівка до виконання. Ефективні алгоритми комбінаторики як правило пов'язані з рекурентними співвідношеннями. Немає необхідності запам'ято­вувати всі вхідні дані.

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

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

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


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