Различия между версиями 12 и 13
Версия 12 от 2020-09-23 00:00:28
Размер: 5836
Редактор: FrBrGeorge
Комментарий:
Версия 13 от 2020-09-26 00:06:56
Размер: 5834
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 93: Строка 93:
## 1. <<EJCMC(148, HandShakes, Теория рукопожатий)>>  1. <<EJCMC(148, HandShakes, Теория рукопожатий)>>

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

  • примеры со строками и кортежами

Кстати,

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

Индексируемые/неиндексируемые последовательности

Имеют метод последовательность.__getitem__(что-то), что означает последовательность[что-то]

Кортеж:

  • индексирование, +от конца
  • секционирование, шаг, умолчания, отсутствие границ
  • как на самом деле работает [].__getitem__()

    • тип slice

  • .__getitem__(кортеж) — не работает, а в других типах может)

Cтрока (введение):

  • Подстрока строки — строка :)

Модифицируемые

Списки

Имеют метод .__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(выражение)
      
      то есть является декартовым произведением
  • Методы списков
  • Список как динамический массив, сложность модификации его начала (n) и конца (1)

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

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

Деки:

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

  • from collectiond import deque

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

Множества

Имеют метод .__add__()

  • Реализация множеств как хеш-таблиц, линейный в среднем поиск
  • => хеширование только константных объектов!

  • Задание множества: { элемент1, элемент2, …}

    • Пустое множество — set(), (а {} — вообще не множество)

  • Теоретико-множественные операции
  • множество — это последовательность
  • замороженные множества

Вычислимые последовательности (введение, можем не успеть)

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

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

  • enumerate()

  • reversed() (а это — нет)

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

Д/З

  1. Прочитать и прощёлкать тьюториалпро цикл for) TODO Тесты к задачам пока не готовы, появятся вечером.

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

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

    Input:

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

    YES
  3. EJudge: MaxPrime 'Ближайшее простое'

    Ввести натуральное 1000000000000>N>1 и вывести максимальное простое число, не превосходящее N.

    Input:

    12345
    Output:

    12343
  4. EJudge: HandShakes 'Теория рукопожатий'

    Вводить построчно разделённые запятыми последовательности натуральных чисел (кортежи), окончание ввода — пустая строка. Числа в строке — идентификаторы людей, которые познакомились (или уже были знакомы) на некоторой вечеринке. Верно ли, что от любого из перечисленных людей можно построить цепочку знакомств к любому другому? Иными словами, если считать каждую пару x,y ребром неориентированного графа, является ли этот граф связным? Вывести YES или NO.

    Input:

    11,2,3
    7,8,9,
    36,10
    4,2
    5,7,
    11,3,4,
    9,5
    Output:

    NO
  5. EJudge: PairCubes 'Пары кубов'

    Ввести натуральное число и проверить, представимо ли оно в виде суммы кубов двух натуральных чисел. Вывести YES или NO. Придумать алгоритм поэффективнее.

    Input:

    32232195
    Output:

    YES
  6. TODO будет ещё одна задача на множества

LecturesCMC/PythonIntro2020/03_SequencesFor (последним исправлял пользователь FrBrGeorge 2020-09-26 00:07:55)