Последовательности и цикл 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)

  • вариант с шагом

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

• циклическая cборка [выражение 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)
    

• Список как динамический массив, сложность модификации его начала (n) и конца (1)

  • список как стек, .append(), .pop()

  • сравнение с linked lists; есть ли разница в эффективности?
    • единственная выгода linked list — это константная сложность вставки/удаления произвольного элемента

    • но алгоритмов, требующих вставки/удаления произвольного элемента без предварительного поиска, кажется (?) нет, а поиск в обоих случаях линейный

Колоды:

• Ответ на предыдущий вопрос — очередь

• from collectiond import deque

• добавление в начало и в конец

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

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

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

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

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

• например, это совсем не матрица: [[0] * N for i in range(M)] — почему?

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

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

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

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

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

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

Д/З

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

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

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

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

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

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

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

1. EJudge: HiddenText 'Скрытое послание'

   Ввести две строки и проверить, содержится ли вторая в первой, с учётом того, что символы второй строки могут находиться в первой на некотором равном расстоянии друг от друга. Вывести YES или NO.

   Input:

   q-We-Rt-Yu-Iweozzz
   WRYI

   Output:

   YES

2. EJudge: FourSquares 'Четыре квадрата'

   Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов неотрицательных целых чисел (теорема Лагранжа). Ввести натуральное N⩽100000 и найти для него такие целые неотрицательные x,y,z и t, чтобы x²+y²+z²+t²=N. Вывести все такие четвёрки в следующем формате: x,y,z и t — через пробел, и упорядочены по убыванию, а сами четвёрки — лексикографически по возрастанию (без повторений).

   Input:

   100

   Output:

   5 5 5 5
   7 5 5 1
   7 7 1 1
   8 4 4 2
   8 6 0 0
   9 3 3 1
   10 0 0 0

3. EJudge: PackedQueue 'Чудо-конвейер'

   Ввести последовательность объектов Python (только кортежей или целых чисел), и сымитировать работу Чудо-Конвейера. Если объект — кортеж, это означает, что на вход конвейеру подаются поочерёдно все объекты из этого кортежа. Если объект — натуральное число N, это означает, что с выхода конвейера надо снять поочерёдно N объектов, объединить их в кортеж и вывести. Если с конвейера нельзя снять N объектов, или в последовательности нет больше команд, Чудо-Конвейер немедленно останавливается.

   Input:

   ("QWE",1.1,234),2,(None,7),0,2,(7,7,7),2,(12,),(),3,(5,6),3,100500

   Output:

   ('QWE', 1.1)
   ()
   (234, None)
   (7, 7)
   (7, 7, 12)

4. EJudge: HalfTranspose 'Недостранспонировали'

   Ввели N строк по N целых чисел (для удобства представлены тут цифрами). Полученную матрицу

   • 1234
     5678
     9012
     3456

   попытались «транспонировать на 45°» — получилось примерно так:

   •    1
       5 2
      9 6 3
     3 0 7 4
      4 1 8
       5 2
        6

   При этом способе поворота между числами образовались «пустые места» каждое размеров в одно число, размер матрицы увеличился до 2N-1 × 2N-1. Затем все числа «упали на свободные места под ними» — переместились до ближайшей незанятой ячейки:

   •    1
       562
      90173
     3456284

   Ввести построчно через запятую элементы исходной квадратной матрицы. Вывести построчно через запятую элементы получившейся матрицы (без учёта свободных ячеек)

   Input:

   1,2,3,4
   5,6,7,8
   9,0,1,2
   3,4,5,6

   Output:

   1
   5,6,2
   9,0,1,7,3
   3,4,5,6,2,8,4