Языки и методы программирования
Душанбе 2021
Python, черновики лекций
Python -- создатель Gvido Rossum
Имеется интерпретатор
Объектно ориентированный язык
Нет фигурных скобок, begin-end и проч.
Вложенность конструкций определяется только
по отступам (indentation)
Принято в Python'е
-- не использовать табуляции
-- отступ равен 4-м пробелам.
Вместо Hello, World! напишем программу,
печатающую квадраты первых 20 натуральных чисел.
Питон -- язык с динамической типизацией.
Это означает, что переменные не имеют типов,
они хранят объектные ссылки. Тип выражения
определяется по объекту только во время выполнения.
n = 1
while n <= 20:
print(n, n*n)
n += 1
Списки в Питоне -- выглядят как списки в
функциональных языках, но на самом деле это
динамические массивы.
s = [2, 3, 5, 7]
Кусок списка s[1:3] == [3, 5]
1 -- индекс начала
3 -- индекс за концом
s[2:] == [5, 7]
s[:3] == [1, 2, 5]
range(1, 10) -- задает диапазон: 1, 2, ..., 9
Умное (математическое) задание списка
List comprehension
[ (x, x**2) for x in range(1, 21) ]
Получаем список
[(1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36),
(7, 49), (8, 64), (9, 81), (10, 100), (11, 121),
(12, 144), (13, 169), (14, 196), (15, 225), (16, 256),
(17, 289), (18, 324), (19, 361), (20, 400)]
Цикл for -- в Питоне это конструкция
для каждого элемента x структуры данных выполнить:
действие(x)
m = 41
res = False
for x in [2, 3, 5]:
if m%x == 0:
res = True
break
for i in range(100):
# i принимает значения 0, 1, 2, ..., 99
Функции в Питоне
def f(x, y):
. . .
return x + y
Напишем функцию, проверяющую простоту числа
isPrime(97) == True
isPrime(561) == False
При определении списка с помощью list comprehension
можно указывать фильтр -- какие элементы из указанного
диапазона оставлять в списке:
>>> [ m for m in range(100) if prime(m) ]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Распаковка кортежа (tuple)
(a, b, c, d) = (200, 300, 400, 1000)
где a, b, c, d -- это обязательно переменные
Вычисляется кортеж справа и элементы этого
кортежа записываются в переменные из кортежа слева
Круглые скобки писать не обязательно!
a, b, c, d = 200, 300, 400, 1000
Как обменять значения двух переменных:
(x, y) = (y, x)
или даже
x, y = y, x
Задача: найти все пифагоровы тройки с числами,
меньшими 100.
Прямоугольный треугольник со сторонами a, b, c
a^2 + b^2 == c^2
a <= b
Если (a, b, c) -- пифагорова тройка, то для m = 1
(ma, mb, mc) -- тоже пифагорова
3, 4, 5 -- пифагорова, то
6, 8, 10 -- тоже пифагорова
Найдем все "элементарные" пифагоровы тройки, где
a, b взаимно просты, т.е. gcd(a, b) == 1
Используем list comprehension
pythTriples = [(a, b, c) for a in range(1, 101)
for b in range(a, 101)
for c in range(b+1, 101)
if gcd(a, b) == 1 and a**2 + b**2 == c**2]
Задача на дом (не обязательно, желательно!)
Написать функцию, которая раскладывает число на простые
множители.
Имеется операция деления /, которая возвращает
вещественный результат:
11/2
5.5
10/2
5.0
Операция целочисленного деления обозначается //
11 // 2
5
10 // 2
5
(Комментарий до конца строки в Python'е: #)
На дом: написать функцию, которая возращает
разложение числа на множители:
def factor(m):
. . .
возвращает список пар
(p, e)
p -- простое число, входящее в раздожение m,
e -- его степень.
Пример:
factor(100)
[(2, 2), (5, 2)]
100 = 4 * 25 = 2^2 * 5^2
factor(561)
[(3, 1), (11, 1), (17, 1)]
factor(1024)
[(2, 10)]
Как формировать список?
s = []
for m in range(100):
if prime(m):
s.append(m)
Обязательно дома:
1) установить Python3
======================================
18 Mar 2021
Было задано:
реализовать функцию, которая получает разложение числа на множители:
factor(m)
Возвращает список пар
[(p, e), ... ]
p -- простой делитель числа m
e -- его степень
factor(100)
[(2, 2), (5, 2)]
factor(48)
[(2, 4), (3, 1)]
factor(19)
[(19, 1)]
Совершенные числа
Целое число m > 0 совершенно (perfect),
если оно равно сумме своих собственных делителей.
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
Написать функцию, проверяющую, является ли число m совершенным
perfect(m) возвращает True/False (тип bool)
Просте решение: находим список всех делителей числа
и проверяем, равна ли сумма элементов списка числу.
def divizors(m):
'''Return a list of all proper divizors of integer m'''
return [d for d in range(1, m) if m%d == 0]
def perfect(m):
'''Check whether an integer m is a perfect number'''
return sum(divizors(m)) == m
Число называется полусовершенным (semiperfect),
если оно равно сумме некоторого подмножества своих
собственных делителей.
def semiperfect(m):
'''Check whether an integer m is a semiperfect number,
i.e. m equals a sum of some subset of its proper divizors'''
Идея решения:
Используя функцию divizors(m), находим список
собственных делителей числа m.
После этого решаем задачу о рюкзаке:
можно ли из некоторых элементов этого списка набрать
сумму, в точности равную m.
def knapsack(l, m):
'''
Input: l is a list of positive integers
m >= 0 -- integer
Return: a pair (True, s), where
s is a subset of l such that sum(s) == m,
or a pair (False, []), if such subset
does not exist.
'''
. . . Домашнее задание (вариант 1): реализовать
функцию, решающую задачу о рюкзаке
(проще всего с помощью рекурсии)
Идея:
# краевое условие:
если m == 0
| вернуть (True, [])
конец если
если длина(l) == 0
| вернуть (False, [])
иначе если длина(l) == 1
| если l[0] == m
| | вернуть (True, [l[0]])
| иначе
| | вернуть (False, [])
| конец если
конец если
# Шаг рекурсии
если l[0] <= m
| (res, s) = knapsack(l[1:], m - l[0])
| если res
| | вернуть (True, l[0] + s)
| конец если
конец если
# Не удалось заполнить рюкзак, положив в него первую вещь.
# Попробуем заполнить рюкзак без первой вещи.
вернуть knapsack(l[1:], m)
конец функции
Задача про счастливые билеты
Номер билета счастливый, если сумма первой половины его цифр
равна сумме второй половины (предполагаем, что номер билета
состоит из четного числа цифр)
132402 132 == 402 -- билет счастливый
Две задачи:
1) получить список всех счастливых билетов длины n, n четное;
2) подсчитать число счастливых билетов длины n.
Переменные в Питоне хранят не указатели на объекты,
а объектные ссылки. Указатель хранить нельзя, поскольку
объекты могут перемещаться по памяти. Их может перемещать
сборщик мусора (garbage collector, gc)
>>> x = [2, 3, 5, 7]
>>> id(x)
140211549220488
>>> y = x
>>> id(y)
140211549220488
>>> x[0] = 222
>>> x
[222, 3, 5, 7]
>>> y
[222, 3, 5, 7]
Shallow copy -- мелкое копирование
сам объект не копируется, копируются только переменные
(объектные ссылки)
В результате меняем одну переменную, другая переменная также синхронно
меняется (на самом деле меняется объект, на который ссылаются обе переменные).
Чтобы создать копию списка, можно воспользоваться методом copy:
>>> x
[222, 3, 5, 7]
>>> y = x.copy()
>>> y
[222, 3, 5, 7]
>>> id(x)
140211549220488
>>> id(y)
140211549260232
>>> x[1] = 333
>>> x
[222, 333, 5, 7]
>>> y
[222, 3, 5, 7]
Есть понятия Shallow copy (мелкое копирование) и
Deep copy (глубокое копирование).
При глубоком копировании создаются дубликаты
всех объектов, составляющих структуру копируемого объекта.
В Питоне надо подключить модуль copy и использовать функцию
deepcopy(x)
Чтобы получить список всех счастливых билетов, надо иметь функцию
def happy(number):
проверяющую, является ли билет счастливым,
а также уметь перебирать все номера заданной длины.
Список длины n, состоящий из всех нулей:
Используя list comprehension:
[0 for i in range(n)]
Но есть блоее простой способ:
[0]*n
повторить список n раз
Например,
[1, 2]*3 == [1, 2, 1, 2, 1, 2]
Удобно иметь функцию, которая по списку чисел 0..9
получает список, следующий в лексикографическом порядке.
[0, 0], [0, 1], [0, 2], ..., [0, 9], [1, 0], [1, 1], ..., [1, 9],
[2, 0], ..., [2, 9], ..., [9, 9] --> [0, 0] и перенос из старшего
разряда (carry)
def nextNumber(number):
# меняет список number на следующий в лексикографическом порядке,
# возвращает перенос из старшего разряда (0 или 1)
Итак, решим задачу:
получить список всех счастливых билетов длины n, n четное.
def happyTickets(n):
Задание на дом:
3 варианта, нужно сделать задачу,
номер которой совпадает с вашим номером в журнале
по модулю 3.
1. Реализовать функцию knapsack(lst, m)
lst -- список положительных целых чисел,
m -- объем рюкзака
Ответ: (True/False, подмножество/[])
C ее помощью реализовать ф-цию
semiperfect(m)
2. Найти быстую реализацию функции
numHappyTickets(n)
Идея: перебираем не все билеты, а билеты
половинной длины.
n = 4
Сумма 0: 1 полубилет [0, 0] => 1^2 = 1
Cумма 1: 2 полубилета [1, 0], [0, 1] => 2^2 = 4
Cумма 2: 3 полубилета [2, 0], [1, 1], [0, 2] => 3^2 = 9
. . .
Cумма 18: 1 полубилет [9, 9]
Массив numSemiTickets из 19 элементов
numSemiTickets[s] содержит число полубилетов
с данной суммой
Ответ для нашей задачи равен сумме квадратов
элементов этого массива.
3. Рассматриваем перестановки чисел 1, 2, 3, ..., n
всего их n!
Реализовать функцию
nextPermutation(permutation)
возвращает False, если не дошли до начальной перестановки
[1, 2, 3, ..., n]
или True, если перебор закончен.
nextPermutation([2, 1, 3])
получим [2, 3, 1]
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],
[3, 1, 2], [3, 2, 1]