Различия между версиями 3 и 4
Версия 3 от 2020-09-22 11:19:53
Размер: 5835
Редактор: FrBrGeorge
Комментарий:
Версия 4 от 2020-09-22 12:36:10
Размер: 7019
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 25: Строка 25:
 * В конструкции множественного связывания `имена = последовательность` последовательность любая  * В конструкции множественного связывания `имена = последовательность` последовательность ''любая''
Строка 77: Строка 77:
 * замороженные множества
Строка 81: Строка 82:
 * `sotred()` и `reversed()`  * `reversed()` (а это — нет)
  * ещё есть `sorted()`, но оно возвращает список
Строка 83: Строка 85:
=== Про Д/З ===
Почти весь ввод в Д/З делается с помощью `eval(nput())`:
 * `input()` вводит строку
 * `eval()` __вычисляет__ эту строку, как если бы это было __выражение python3__
Строка 91: Строка 88:
## 1. <<EJCMC(131, MaxSubsum, Полоса удач)>>
## 1. <<EJCMC(131, PackedQueue, Чудо-конвейер)>>
## 1. При подготовке последнего теста использовался графический редактор GIMP и формат [[FrBrGeorge/LearnXPM|XPM]] :)
## <<EJCMC(131, FindRect, Морской бой)>>
## 1. <<EJCMC(131, SpiralDigits, Цифры по спирали)>>
## 1. Д/З мне: на следующий раз не забыть про множество
 '''TODO''' Тесты к задачам пока не готовы, появятся вечером.
 1. `<<EJCMC(148, HiddenText, Скрытое послание)>>`
  Ввести две строки и проверить, содержится ли вторая в первой, с учётом того, что символы второй строки могут находиться в первой на некотором ''равном'' расстоянии друг от друга. Вывести `YES` или `NO`:
  {{{
  q-We-Rt-Yu-Iweozzz
  WRYI

  YES
  }}}
 1. <<EJCMC(148, MaxPrime, Ближайшее простое)>>
 1. `<<EJCMC(148, HandShakes, Теория рукопожатий)>>`
  Вводить построчно разделённые запятыми последовательности натуральных чисел (кортежи), окончание ввода — пустая строка. Числа в строке — идентификаторы людей, которые познакомились на некоторой вечеринке. Верно ли, что от любого из перечисленных людей можно построить цепочку знакомств к любому другому? Вывести `YES` или `NO`
  {{{
  1,2,3
  7,8,9
  6,10
  4,2
  5,7
  1,3,4
  9,5


  NO
  }}}
  (Здесь даже три изолированные группы.)
 1. `<<EJCMC(148, PairCubes, Пары кубов)>>`
  Ввести натуральное число и проверить, представимо ли оно в виде суммы кубов двух натуральных чисел. Вывести `YES` или `NO`. Придумать алгоритм поэффективнее.
  {{{
  32232195

  YES
  }}}

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

TODO это план прошлогодней лекции, поправить

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

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

  • Операции — это методы
    • int.__add__(100500,42) или даже (100500).__add__(42) как 100500+42

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

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

    • Строгая типизация (__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

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

Множества

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

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

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

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

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

  • enumerate()

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

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

Д/З

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

  2. <<EJCMC(148, HiddenText, Скрытое послание)>>

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

        q-We-Rt-Yu-Iweozzz
        WRYI
      
        YES
  3. EJudge: MaxPrime 'Ближайшее простое'

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

    Input:

    12345
    Output:

    12343
  4. <<EJCMC(148, HandShakes, Теория рукопожатий)>>

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

        1,2,3
        7,8,9
        6,10
        4,2
        5,7
        1,3,4
        9,5
      
      
        NO
      (Здесь даже три изолированные группы.)
  5. <<EJCMC(148, PairCubes, Пары кубов)>>

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

        32232195
      
        YES

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