Последовательности и цикл for

Операции над объектами как совокупность методов

• Поля объектов, пространство имён, dir(), поля-методы и поля-поля

• Операции — это методы

  • int.__add__(100500, 42) или даже (100500).__add__(42) как 100500+42

  • "строка".__len__() как len("строка")

  • и т. п.
• Понятие протокола

  • Пример: числовой протокол (на Си), на Python

  • Строгая типизация (__mul__() vs __rmul__()) и т. п.

  • Последовательность — это свойство объекта (нужные методы), т. е. тоже протокол

Цикл for

• Общий вид:

     1 for имена in последовательность:
     2     тело
  

  • имена, а не только имя — распаковка, если элемент последовательности — тоже последовательность

  • break, continue

  • else:

• примеры со строками и кортежами
• более подробно — в лекции про итераторы

Кстати,

• В конструкции множественного связывания имена = последовательность последовательность любая

  • расширенное множественное присваивание вида «A₀, A₁, …, *А_k, …, A_N = последовательность_из_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 последовательность]

  • Что работает почти так:

       1   _=[]
       2   for имена in последовательность:
       3       _.append(выражение)
    

  • и даже [выражение for имена1 in последовательность1 for имена2 in последовательность2 …]:

       1   _=[]
       2   for имена1 in последовательность1:
       3       for имена2 in последовательность2:
       4           . . .
       5               _.append(выражение)
    

    то есть является декартовым произведением

  • Фильтрующая клауза: [выражение1 for имена in последовательность if выражение2]

       1   _=[]
       2   for имена in последовательность:
       3       if выражение2:
       4         _.append(выражение1)
    

• Список как динамическая таблица (массив ссылок на элементы; размер ссылки в 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

Имитация многомерных структур данных

• «Матрица» как список списков
  • Равенство размеров всех элементов списка?

• (есть array, NumPy и т. д)

Соиспользование связанных объектов

Отсутствие «подковёрного» копирования

• например, это совсем не матрица: [[0] * N] * M — почему? ☺

• a.copy(), a[:] и copy.deepcopy()

Вычислимые последовательности

Значения не хранятся, а вычисляются .__getitem__()-ом

• range (индексируемая!)

  • range(stop) / range(start, stop[, step])

  • «Классический» for i in range(N):

• enumerate

• ещё есть sorted(), но оно возвращает список

Д/З

Напоминалка:

• Если перейти по ссылке, откроется более полная формулировка задания с советами и подсказками
• Подсказки-спойлеры изначально не видны, они открываются, если нажать в шапке страницы меню «комментарии». Обычно в спойлерах излагается алгоритм решения — всё-таки у нас тут не олимпиада ☺

• Любителям «парковки на слух»: всего попыток в турнире 200, а задач примерно 40 — шлите решение, только если уже оттестировали его и уверены, что оно правильное!

Собственно задание:

0. Прочитать и прощёлкать тьюториал (и про цикл for)

   • Операции над последовательностями

   • Операции над модифицируемыми последовательностями

1. EJudge: ShuffleString 'Перетасованная строка'

   Ввести построчно две строки длиной не более 2222 символов и проверить, есть ли такое число n, что вторая строка получается из первой, если сначала взять каждый n-й символ, затем — каждый n-й, начиная с первого и т. д. до каждого n-го, начиная с n-1-го. Вывести наименьшее возможное n, а если такого числа нет — No.

   • Предполагается простой алгоритм перебором — см. ограничение на размер

   • Возможно, потребуется конструкция "".join(последовательность строк), которая склеивает последовательность строк в одну

   • (необязательно) Постарайтесь уложиться в 7 или менее строк

   qwertyuif
   qruwtieyf

   Input:

   qwertyuif
   qruwtieyf

   Output:

   3

2. EJudge: DiagonalDigits 'Цифры по диагонали'

   Ввести целые M и N (0 ⩽ M, N ⩽ 1000), вывести последовательность 0 1 2 3 4 5 6 7 8 9 0 1 2 3 … в виде прямоугольной матрицы N×M, заполненной из верхнего левого угла по следующему правилу:

   • На каждом шаге заполняется очередная диагональ матрицы с одинаковой суммой координат
   • Диагонали заполняются поочерёдно сверху вниз и снизу вверх (таким образом формируется непрерывный «путь» из верхнего левого угла в правый нижний)
   Input:

   6, 5

   Output:

   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

3. EJudge: FindRect 'Морской бой'

   Ввести несколько строк одинаковой длины, состоящих из символов «#» и «.». Ввод заканчивается пустой строкой. На получившемся поле изображены только прямоугольники, причём они не соприкасаются даже углами. Вывести количество этих прямоугольников.

   Input:

   ###.....#.
   ###.##..#.
   ....##....
   ....##..#.
   ..........
   ..........
   ####..####
   ......####
   ......####

   Output:

   6

4. EJudge: UniInterval 'Объединение отрезков'

   Вводится кортеж пар натуральных чисел. Это координаты отрезков на прямой. Рассмотрим объединение этих отрезков и найдём длину этого объединения (т. е. совокупную длину всех «закрашенных» нашими отрезками отрезков на прямой).

   Input:

   (66, 91), (152, 230), (21, 81), (323, 342), (158, 211), (286, 332), (294, 330), (18, 58), (183, 236)

   Output:

   213

   • При подготовке последнего теста использовался графический редактор GIMP и формат XPM