Табличні величини мовою Python
Табличні величини мовою Python
Алгоритм — це запис скінченої послідовності вказівок, виконання яких призводить до розв'язання певної задачі.
Вказівка (алгоритму) — це спонукальне речення, що вказує, яку дію має виконати виконавець алгоритму.
Виконавець (алгоритму) — це жива істота (людина або тварина) або автоматичний пристрій (робот, електронна обчислювальна машина тощо), спроможна діяти відповідно з алгоритмом.
Система вказівок виконавця — це множина (сукупність) всіх вказівок, які може виконувати даний виконавець.
Середовище виконання алгоритму — об'єкти, з якими працює виконавець у процесі виконання алгоритму.
Властивості алгоритму: дискретність, визначеність, виконуваність, скінченність, результативність, масовість, ефективність.
Дискретність (латинською discretus — розділений, розривний) алгоритму означає, що виконання алгоритму зводиться до виконання окремих дій (кроків) у певній послідовності. Причому, кожну вказівку алгоритму виконують за скінченний проміжок часу.
Визначеність (однозначність) означає, що алгоритм однозначно визначає порядок дій виконавця, результат цих дій і не потребує додаткового тлумачення..
Виконуваність означає, що алгоритм, призначений для певного виконавця, може містити лише вказівки, які входять до системи вказівок цього виконавця.
Скінченність означає, що виконання алгоритму закінчиться після скінченної (можливо, досить великої) кількості кроків і за скінченний час для довільних вхідних даних.
Результативність алгоритму означає, що після закінчення виконання алгоритму обов’язково:
- або одержують розв'язок-результат відповідно до поставленої мети;
- або встановлюють відсутність таких розв'язків (множина розв'язків порожня);
- або встановлюють неможливість розв'язання задачі.
Масовість алгоритму означає, що алгоритм можна застосувати до цілого класу однотипних задач, для яких спільними є умова та хід розв’язування та які відрізняються лише початковими (вхідними) даними. Наприклад, алгоритмом дій, складеним для одного касира, можуть успішно скористатися всі касири супермаркету. А програмою пошуку коду і підрахунку суми вартостей товарів, придбаних покупцем, — усі комп'ютери супермаркету
Ефективність алгоритму описує час виконання і об'єм ресурсів, необхідних для виконання алгоритму: чим менше часу (часова ефективність) і ресурсів (просторова ефективність), тим ефективність вища.
Потреба запровадження табличних величин випливає з необхідності запам'ятовувати й однотипно (за одним алгоритмом) опрацьовувати великий набір можливо однотипних даних. Наприклад, при знаходженні середнього балу кожного учня класу з інформатики за чверть потрібно знаходити суму великої кількості оцінок. Як зберігати всі ці оцінки? Зарезервувати для цього 40 чи більше змінних? Це дуже незручно.
У мові Python відповідні зручні структури даних називають послідовностями. Це рядки (символів), списки, масиви, значення функції range і ще деякі інші об'єкти.
Списку (у мові програмування) відповідає (у математиці) послідовність, члени якої занумеровано невід'ємними цілими числами, починаючи з 0, з нефіксованими довжиною та типом елементів.
Оператори й функції для роботи зі списками (s і t у позначеннях нижче)
- len(s) — довжина послідовності s;
- x in s — результат перевірка приналежності значення x послідовності s — True або False. У останніх версіях Python можна перевіряти приналежність підрядка рядку;
- x not in s — not (x in s) — результат заперечення x in s;
- s[j] — повертає значення j-го елемента списку s або (len(s)+j)-й при j < 0;
- s[j]= x — надання елементу з номером j списку s значення x;
- s[i:j:d] — зріз зі списку s від елементів i-го до j-го з кроком d;
- min(s) — найменший елемент s;
- max(s) — найбільший елемент s;
- s + t — результат «дописуванням» до списку s списку t;
- s*n або n*s — результат n-кратного повторення списку s. При n ≤ 0 — порожня послідовність.
Наприклад,
[1, 2, 3] + [4, 5] == [1, 2, 3, 4, 5]
[4, 5]*3 = [4, 5, 4, 5, 4, 5]
Методи списків
- append(x) — додає елемент зі значенням x в кінець послідовності;
- clear — очищує список;
- copy — створює копію списку;
- count(x) — повертає кількість елементів зі значенням x;
- extend(s) — розширює список, додаючи до кінця поточного списку список s;
- index(x[,j0[,j1]]) — повертає найменший iндекс елемента зі значенням x [для номерів елементів від j0 [до j1]]. Породжує виключення ValueError, якщо елемента з таким значенням не знайдено;
- insert(j,x) — вставляє на місце з номером j елемент зі значенням x;
- pop(j) — повертає значення елемента з номером j, видаляючи його з послідовності;
- remove(x) — вилучає елемент з найменшим iндексом серед тих, що мають значення x. Породжує виключення ValueError, якщо елемента з таким значенням не знайдено;
- reverse() — зміняює порядок елементів на зворотний;
- sort([f]) — упорядковує елементи з можливістю використання власної функції порівняння f;
Способи виведення елементів списку
- Вказівка print(a) виводить елементи списку a у квадратних дужках через кому.
- Цикл for можна організувати двома способами:
- змінюючи індекс j, виводити елемент списку з індексом j.
for i in range(len(A)):
print(A[i], end = ' ') (тут і далі запис end = ' ' означає вставлення пробілу);
- змінюючи не індекс елемента списку, а його значення.
for elem in A:
print(elem, end = ' ')
В останньому прикладі бачимо істотну відмінність мови Pytnon від мов-попередників: цикл for надає зручний спосіб перебрати саме елементи послідовності, а не індекси елементів.
Розглянемо приклад створення списку d цілих чисел з цифри рядка s
s = 'ab12c59p7dq'
d = []
for с in s:
if '1234567890'.find(с) != -1:
d.append(int(с))
print(d)
з таким результатом виведення: [1, 2, 5, 9, 7].
Способи створення й наповнення списків
- Використати багатократне повторення списку для заповнення списку одними й тими самими значеннями. Наприклад,
n = 999
a = [0] * n
- Перелічити елементи списку у квадратних дужках. Наприклад,
Primes = [2, 3, 5, 7, 11, 13]
Rainbow = ['червоний','оранжевий','жовтий','зелений','блакитний','синій','фіолетовий']
- Заповнити список згідно з формулою
[вираз for змінна in послідовність]
де послідовність містить усі значення, яких набуває змінна, від якої залежить вираз. Наприклад, список квадратів усіх цифр [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] можна створити таким чином:
a = [j**2 for j in range(0,10)]
print(a)
- Cтворити порожній список і в кінець списку додавати елементи (по одному) за допомогою методу append, значення яких зчитувати, наприклад, з клавіатури.
a = [] # створено порожній список
n = int(input()) # зчитино кількість елементів списку
for i in range(n):
a.append(int(input()))
Змінну n використано лише для зручності сприйняття — див. змінений приклад.
A = []
for i in range(int(input())):
A.append(int(input()))
Можна по-іншому організувати процес прочитування списків, спочатку створивши список з потрібного числа елементів.
A = [0] * int(input())
for i in range(len(A)):
A[i] = int(input())
- Зчитати з файлу
f=open('input.txt','r')
a=[]
for i in range(int(f.readline())): # зчитати кількість елементів
a.append(int(f.readline())) # зчитати по 1 числу у рядку й заповнити масив
print(a) # вивести масив а
b=f.readline().split() # зчитати рядок тексту і утворити масив b з його слів
print(b) # вивести масив b
- Заповнити випадковими числами з використанням функциї randrange з модуля random:
from random import randrange
n = 10
a = [randrange(1, 10) for i in range(n)]
Обчислення суми елементів масиву, що задовольняють певним умовам
(приклад подано для знаходження суми парних елементів лінійного масиву 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, — робимо таке:
- визначаємо номер l найменшого елемента для індексів у межах від j до n включно;
- міняємо місцями значення елементів з індексами j та l. У результаті такої заміни на місце з номером (індексом) j стане те значення, що потрібно.
Код програми мовою 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 включно має такий вигляд:
Вибирати значення елемента масиву.
Значення елементів масиву, що не менші за вибране, розташувати на місцях з номерами (індексами) більшими від індексу обраного значення, а ті, що не перевищують — на місцях з номерами меншими від індексу обраного значення. У результаті вибране значення матиме той номер j у масиві, що потрібно. Тому надалі відповідний елемент масиву буде незмінним.
Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.
Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.
Рекурсивність алгоритму означає виклик цього алгоритму в ньому самому — див. кроки 3–4.
Метод обліку передбачає використання окремого масиву з нульовими початковими значеннями, який після проглядання масиву, що підлягає впорядкуванню, містить інформацію про те, скільки разів те чи інше значення зустрілося серед значень елементів масиву.
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. Зазвичай для цього використовують двійковий (бінарний) пошук. Він полягає у послідовному поділі (приблизно) навпіл діапазону номерів, у якому проводять пошук. На початку виконання цього алгоритму:
l — менша межа діапазону номерів, на якому шукають потрібний номер, дорівнює меншій межі діапазону номерів масиву;
r — більша межа діапазону номерів, на якому шукають потрібний номер, дорівнює більшій межі діапазону номерів масиву.
Алгоритм бінарного пошуку має такий вигляд:
Поки справджується нерівність l ≤ r, робити таке:
надати значення змінній l = [(j + k)/2] — знайти індекс l, що поділяє досліджуваний діапазон навпіл;
якщо al = b, завершити пошук зі знайденим номером l;
якщо al < b, надати значення змінній l = (x + 1), тобто вибрати для подальшого пошуку діапазон, розташований правіше від l;
якщо al > b, надати значення змінній r = (x – 1), тобто вибрати для подальшого пошуку діапазон, розташований лівіше від l;
Завершити пошук, вважаючи його неуспішним.
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.
про публікацію авторської розробки
Додати розробку