Различия между версиями 15 и 16
Версия 15 от 2022-09-28 18:14:33
Размер: 8992
Редактор: FrBrGeorge
Комментарий:
Версия 16 от 2022-10-01 17:22:21
Размер: 9739
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 36: Строка 36:
 * `in`  * `in` и `not in`
Строка 39: Строка 39:
 * секционирование: шаг, умолчания, отсутствие границ  * секционирование:
* отсутствие границ
  * шаг
  * умолчания (+чем `A[:]` отличается от `A`?)
Строка 45: Строка 48:
 * Подстрока строки — строка :)  * Подстрока строки — строка, так что `"!@#"[0][0][0][-1][0][-1]…` — сработает и выдаст `"!"` :)
 * ⇒ Хотя строки и ''хранимая'' последовательность, её «элементы» ''вычисляются''
Строка 52: Строка 56:
 * [[py3doc:stdtypes.html#mutable-sequence-types|Операции над модифицируемыми последовательностями]]
Строка 75: Строка 81:
 * [[py3doc:stdtypes.html#mutable-sequence-types|Операции над модифицируемыми последовательностями]]
Строка 94: Строка 99:
'''Имитация многомерных структур данных'''
 * списки списков: проблема внутренних размеров
==== Имитация многомерных структур данных ====
 * «Матрица» как список списков
  * Равенство размеров всех элементов списка?
 * (есть [[py3doc:array]], [[http://numpy.org|NumPy]] и т. д)
==== Соиспользование связанных объектов ====
Отсутствие «подковёрного» копирования
 * например, это совсем не матрица: `[[0] * N for i in range(M)]` — почему?
 * `a.copy()`, `a[:]` и `copy.deepcopy()`

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

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

Кстати,

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

    • расширенное множественное присваивание вида «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)

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

  • циклическая 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 — шлите решение, только если уже оттестировали его и уверены, что оно правильное!

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

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

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

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

    Input:

    q-We-Rt-Yu-Iweozzz
    WRYI
    Output:

    YES
  3. 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
  4. 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)
  5. 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

LecturesCMC/PythonIntro2022/03_SequencesFor (последним исправлял пользователь FrBrGeorge 2022-10-01 17:22:21)