5835
Комментарий:
|
7019
|
Удаления помечены так. | Добавления помечены так. |
Строка 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
- Общий вид:
имена, а не только имя — распаковка, если элемент последовательности — тоже последовательность
break, continue и else:
- примеры со строками и кортежами
Кстати,
В конструкции множественного связывания имена = последовательность последовательность любая
Индексируемые/неиндексируемые последовательности
Имеют метод последовательность.__getitem__(что-то), что означает последовательность[что-то]
Кортеж:
- индексирование, +от конца
- секционирование, шаг, умолчания, отсутствие границ
как на самом деле работает .__getitem__()
тип slice
.__getitem__(кортеж) — не работает
Cтрока (введение):
Подстрока строки — строка
Модифицируемые
Имеют метод .__setitem__() Список:
.setitem(число)
.setitem(slice)
- вариант с шагом
циклическая cборка [выражение for имена in последовательность]
- Что работает так:
и даже [выражение for имена1 in последовательность1 for имена2 in последовательность2 …]:
то есть является декартовым произведением
- Методы списков
Список как динамический массив, сложность модификации его начала (n) и конца (1)
список как стек, .append(), .pop()
- сравнение с linked lists; есть ли разница в эффективности?
- единственная выгода linked list — это константная сложность вставки/удаления произвольного элемента
но алгоритмов, требующих вставки/удаления произвольного элемента без предварительного поиска, кажется (?) нет, а поиск в обоих случаях линейный
Деки:
Ответ на предыдущий вопрос — очередь
from collectiond import deque
- добавление в начало и в конец
Множества
- Реализация множеств как хеш-таблиц, линейный в среднем поиск
=> хеширование только константных объектов!
- Теоретико-множественные операции
- множество — это последовательность
- замороженные множества
Вычислимые последовательности (введение, можем не успеть)
Значения не хранятся, а вычисляются .__getitem__()-ом
range (индексируемая!)
enumerate()
reversed() (а это — нет)
ещё есть sorted(), но оно возвращает список
- …
Д/З
Прочитать и прощёлкать тьюториал (и про цикл for) TODO Тесты к задачам пока не готовы, появятся вечером.
<<EJCMC(148, HiddenText, Скрытое послание)>>
Ввести две строки и проверить, содержится ли вторая в первой, с учётом того, что символы второй строки могут находиться в первой на некотором равном расстоянии друг от друга. Вывести YES или NO:
q-We-Rt-Yu-Iweozzz WRYI YES
EJudge: MaxPrime 'Ближайшее простое'
Ввести натуральное 1000000000000>N>1 и вывести максимальное простое число, не превосходящее N.
12345
12343
<<EJCMC(148, HandShakes, Теория рукопожатий)>>
Вводить построчно разделённые запятыми последовательности натуральных чисел (кортежи), окончание ввода — пустая строка. Числа в строке — идентификаторы людей, которые познакомились на некоторой вечеринке. Верно ли, что от любого из перечисленных людей можно построить цепочку знакомств к любому другому? Вывести YES или NO
1,2,3 7,8,9 6,10 4,2 5,7 1,3,4 9,5 NO
(Здесь даже три изолированные группы.)
<<EJCMC(148, PairCubes, Пары кубов)>>
Ввести натуральное число и проверить, представимо ли оно в виде суммы кубов двух натуральных чисел. Вывести YES или NO. Придумать алгоритм поэффективнее.
32232195 YES