Последовательности и цикл for
Операции над объектами как совокупность методов
Поля объектов, пространство имён, dir(), поля-методы и поля-поля
- Операции — это методы
int.__add__(100500, 42) или даже (100500).__add__(42) как 100500+42
"строка".__len__() как len("строка")
- и т. п.
- Понятие протокола
Пример: числовой протокол (на Си), на Python
Строгая типизация (__mul__() vs __rmul__()) и т. п.
- Последовательность — это свойство объекта (нужные методы), т. е. тоже протокол
Цикл for
- Общий вид:
имена, а не только имя — распаковка, если элемент последовательности — тоже последовательность
break, continue
else:
- примеры со строками и кортежами
- более подробно — в лекции про итераторы
Кстати,
В конструкции множественного связывания имена = последовательность последовательность любая
расширенное множественное присваивание вида «A0, A1, …, *Аk, …, AN = последовательность_из_N+m_элементов»
Функции all() и any() принимают в качестве параметра последовательность
- …они повсюду!
Последовательности
Операции над последовательностями
Имеют метод последовательность.__getitem__(что-то), что означает последовательность[что-то]
Константные последовательности на примере кортежа
- Умножение на число и сложение
in и not in
- индексирование, +от конца
поэлементное лексикографическое сравнение
- секционирование:
- отсутствие границ
- шаг
умолчания (+чем A[:] отличается от A?)
как на самом деле работает [] — .__getitem__()
тип slice
.__getitem__(кортеж) — не работает, а в других типах может)
Cтрока (введение)
Подстрока строки — строка, так что "!@#"[0][0][0][-1][0][-1]… — сработает и выдаст "!"
⇒ Хотя строки и хранимая последовательность, её «элементы» вычисляются
Списки — модифицируемые последовательности
Имеют метод .__setitem__()
.__setitem__(число)
.__setitem__(slice)
- вариант с шагом
циклическая сборка [выражение for имена in последовательность]
Что работает почти так:
и даже [выражение for имена1 in последовательность1 for имена2 in последовательность2 …]:
то есть является декартовым произведениемФильтрующая клауза: [выражение1 for имена in последовательность if выражение2]
- Список как динамическая таблица (массив ссылок на элементы; размер ссылки в Python всегда одинаковый)
Сложность модификации его начала (O(n)) и конца (O(1))
Реализация динамического массива с геометрическим масштабированием (TODO показать геометрическое масштабирование):
- Выделяем N элементов массива
Если массив переполняется, удваиваем его размер и копируем все элементы на новое место
- Если массив опустошается на K% (т. н. «нижний урез»; в Python — на 3/4, кажется), ополовиниваем размер и копируем элементы
⇒ Сложность добавления элемента в конец / удаления обычно O(1)
при масштабировании O(N), но происходит в среднем в 1/2ⁿ случаях ⇒ несущественна
- Сравнение с linked lists; есть ли разница в эффективности?
- единственная выгода linked list — это константная сложность вставки/удаления произвольного элемента
но алгоритмов, требующих вставки/удаления произвольного элемента без предварительного поиска, кажется (?) нет, а поиск в обоих случаях линейный
Список как стек, .append(), .pop()
Работа += на списках
- Другие методы списка
Востребованный не последний элемент, искать который не нужно — первый.
⇒ list неэффективен как очередь
- «Колода» / deque (двойная очередь? «колочередь»?)
- эффективное добавление и в начало, и в конец
from collectiond import deque
Имитация многомерных структур данных
Соиспользование связанных объектов
Отсутствие «подковёрного» копирования
например, это совсем не матрица: [[0] * N] * M — почему? ☺
a.copy(), a[:] и copy.deepcopy()
Вычислимые последовательности
Значения не хранятся, а вычисляются .__getitem__()-ом
range (индексируемая!)
range(stop) / range(start, stop[, step])
«Классический» for i in range(N):
ещё есть sorted(), но оно возвращает список
Д/З
Напоминалка:
- Если перейти по ссылке, откроется более полная формулировка задания с советами и подсказками
- Подсказки-спойлеры изначально не видны, они открываются, если нажать в шапке страницы меню «комментарии». Обычно в спойлерах излагается алгоритм решения — всё-таки у нас тут не олимпиада ☺
Любителям «парковки на слух»: всего попыток в турнире 200, а задач примерно 40 — шлите решение, только если уже оттестировали его и уверены, что оно правильное!
Собственно задание:
Прочитать и прощёлкать тьюториал (и про цикл for)
EJudge: ShuffleString 'Перетасованная строка'
Ввести построчно две строки длиной не более 2222 символов и проверить, есть ли такое число n, что вторая строка получается из первой, если сначала взять каждый n-й символ, затем — каждый n-й, начиная с первого и т. д. до каждого n-го, начиная с n-1-го. Вывести наименьшее возможное n, а если такого числа нет — No.
- Предполагается простой алгоритм перебором — см. ограничение на размер
Возможно, потребуется конструкция "".join(последовательность строк), которая склеивает последовательность строк в одну
(необязательно) Постарайтесь уложиться в 7 или менее строк
qwertyuif qruwtieyf
qwertyuif qruwtieyf
3
EJudge: DiagonalDigits 'Цифры по диагонали'
Ввести целые M и N (0 ⩽ M, N ⩽ 1000), вывести последовательность 0 1 2 3 4 5 6 7 8 9 0 1 2 3 … в виде прямоугольной матрицы N×M, заполненной из верхнего левого угла по следующему правилу:
- На каждом шаге заполняется очередная диагональ матрицы с одинаковой суммой координат
- Диагонали заполняются поочерёдно сверху вниз и снизу вверх (таким образом формируется непрерывный «путь» из верхнего левого угла в правый нижний)
6, 5
0 2 3 9 0 9 1 4 8 1 8 0 5 7 2 7 1 6 6 3 6 2 5 7 4 5 3 4 8 9
EJudge: FindRect 'Морской бой'
Ввести несколько строк одинаковой длины, состоящих из символов «#» и «.». Ввод заканчивается пустой строкой. На получившемся поле изображены только прямоугольники, причём они не соприкасаются даже углами. Вывести количество этих прямоугольников.
###.....#. ###.##..#. ....##.... ....##..#. .......... .......... ####..#### ......#### ......####
6
EJudge: UniInterval 'Объединение отрезков'
Вводится кортеж пар натуральных чисел. Это координаты отрезков на прямой. Рассмотрим объединение этих отрезков и найдём длину этого объединения (т. е. совокупную длину всех «закрашенных» нашими отрезками отрезков на прямой).
(66, 91), (152, 230), (21, 81), (323, 342), (158, 211), (286, 332), (294, 330), (18, 58), (183, 236)
213
При подготовке последнего теста использовался графический редактор GIMP и формат XPM