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

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

Мета:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Дати відповіді на запитання:

  1. Яким словом починають оголошення:
    • використаних модулів;
    • типів;
    • сталих;
    • змінних;
    • міток?
  2. Яким символом розмежовують вказівки у коді програми?
  3. Які типи простих даних ви знаєте?

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


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

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

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

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

Наприклад,

[1, 2, 3] + [4, 5] == [1, 2, 3, 4, 5]
[4, 5]*3 = [4, 5, 4, 5, 4, 5]

Методи списків

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

В останньому прикладі бачимо істотну відмінність мови Pytnon від мов-попередників: цикл for надає зручний спосіб перебрати саме елементи послідовності, а не індекси елементів.

Розглянемо приклад створення списку d цілих чисел з цифри рядка s

s = 'ab12c59p7dq'
d = []
for с in s:
    if '1234567890'.find(с) != -1:
            d.append(int(с))
print(d)

з таким результатом виведення: [1, 2, 5, 9, 7].

Способи створення й наповнення списків

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

import random
n=9
amax=99
a=[]
for j in range(n):                      
    a.append(random.randint(1,amax))
print(a)
print('Сума парних чисел з поданих дорівнює')
s=0
for j in range(n): 
    if a[j]%2==0:
        s+=a[j]
print(s)

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

import random
n=9
amax=99
a=[]
for j in range(n):
    a.append(random.randint(1,amax))
print(a)
print('Найменше з поданих чисел дорівнює')
Min=a[0]
for j in range(n):
    if a[j]<Min:
        Min=a[j]
print(Min) 

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

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

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

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

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

import random
n=9
amax=99
a=[]
for j in range(n):
  a.append(random.randint(1,amax))
print(a)
for j in range(n-1):
  for k in range(j+1,n):
    if a[j]>a[k]:
       a[j],a[k]=a[k],a[j]
print('Результат впорядкування цього масиву такий')
print(a)

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

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

import random
n=9
amax=99
a=[]
for j in range(n):
    a.append(random.randint(1,amax))
print(a)
def qsort(L):
    if L: return qsort([x for x in L if x<L[0]]) + [x for x in L if x==L[0]] + qsort([x for x in L if x>L[0]])
    return []
print('Результат впорядкування цього масиву такий')
print(qsort(a)) 

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

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

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

import random
n=10
amax=20
a=[]

for j in range(n):  a.append(random.randint(1,amax))
print(a)

b=[0]*(amax+1)
for j in a: b[j]+=1

c=[]
for j in range(amax+1):  
    if b[j]>0:
        for k in range(b[j]):
            c.append(j)
print(c)

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

import random
n=9
amax=99
a=[]
for j in range(n):
    a.append(random.randint(1,amax))
print(a)
a.sort()
print(a)

У цьому випадку елементи списку буде переставлено. Метод sort не повертає значення, тому результат виклику методу sort не використовують в арифметичних виразах або при виведенні результату. Інший спосіб — це функція sorted. Вона, навпаки, не модифікує переданий їй список, а повертає новий список. Функцію sorted можна викорис­товувати таким чином:

import random
n=9
amax=99
a=[]
for j in range(n):
    a.append(random.randint(1,amax))
print(a)
b=sorted(a)
print(b)

Функцію sorted можна використати при введенні-виведенні. Наступна програма упорядковує зчитаний з одного рядка введення список чисел, розділених у рядку пробілами, і виводить результат на екран.

print ( " " .join (map (str, sorted (map (int, input (). split ())))))

І методу sort, і функції sorted можна передати значення параметра reverse. Якщо це значення дорівнює True, то упорядкування буде проведено у зворотному порядку, тобто за незростанням.

Якщо елементи списку самі є списками, то сортування відбуватиметься за першими елементам вкладених списків:

>>>a=[[2,1],[3,2],[1,3]]
>>>print(sorted(a))
[[1, 3], [2, 1], [3, 2]]

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

a = [['Петро',10,130,35], ['Василина',11,135,39],['Христина',9,140,33],['Тарас',10,128,30]]
n = input('Упорядкувати за іменем (1), віком (2), зростом (3) чи вагою (4): ')
n = int(n)-1

def sort_col(i):
   return i[n]

a.sort(key=sort_col)
for i in a:
  print(i[0],' ', i[1],' ', i[2],' ',i[3])

Якщо критерієм упорядкування елемент вкладеного списку (як у попередньому випадку), то можна використати функцію lambda

a = [['Петро',10,130,35], ['Василина',11,135,39],['Христина',9,140,33],['Тарас',10,128,30]]
n = input('Упорядкувати за іменем (1), віком (2), зростом (3) чи вагою (4): ')
n = int(n)-1
a.sort(key=lambda i: i[n])
for i in a:
  print(i[0],' ', i[1],' ', i[2],' ',i[3])

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

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

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

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

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

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

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

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

import random
import math
a=[]
n=10
for i in range(n):                   
  a.append(random.randint(1,100))
print(a)
k=a[3]
l=0
r=n-1
while True:
  x=math.ceil((l+r)/2)
  if k==a[x]:
    res=x
    break
  elif k<a[x]:
    r=x
  else:
    l=x
print(res)

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

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

  1. Назвати різновиди послідовностей у мові Python.
  2. Назвати методи роботи зі списками.
  3. Назвати способи виведення елементів списку.
  4. Назвати способи створення й наповнення списків.
  5. описати методи упорядкування списків.
  6. Описати бінарний пошук.

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

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


Текст упорядкувала Сцібан Ірина Вікторівна, вчитель середньої загальноосвітньої школи № 6 Подільського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 2.10.2017 по 06.10.2017.