Домашняя работа по курсу

Как сдавать домашнюю работу

  1. Зарегистрироваться на факультетском Ejudge

  2. Выбрать 5-й «турнир» (UNИX Python 2014)
    • Возможно, придётся пойти по ссылке «Confirm registration» («Подтвердить регистрацию»)
    • Возможно, придётся пойти по ссылке «Participate» («Участвовать»)
  3. Выбрать соответствующую задачку

    • Задачу под названием «1» решать не надо :)

  4. Загрузить решение
    • Прежде, чем загружать решение, убедитесь, что оно правильное. Не надо вместо этого делать много различных вариантов решения в надежде, что какой-то один всё-таки пройдёт тесты.

    • Если возникают вопросы — спрашивайте, для этого есть и интерфейс eJudge, и почта (FrBrGeorge, PavelSutyrin)

  5. Дождаться конца проверки (как правило, несколько секунд) и обновить страницу браузера

Как оформлять решение

По умолчанию, т. е. если иное не указано отдельно:

⇒ Для ввода можно пользоваться input() (без строки-подсказки), а для вывода — print.

Сводный список домашних заданий

См. ../HomeworkRules

  1. Установить и настроить подходящий текстовый редактор или IDE (пример: настройка Geany)

  2. (AndOr) Условное выражение

    Ввести два объекта Python и вывести первый ненулевой из них. Если оба нулевые, вывести NO.

    Input: 

    []
123
    Output: 

    123

  3. (Methods) Вывести в столбик поля объекта

    Ввести объект Python и вывести в столбик имена тех его полей (независимо от типа ⇒ в т. ч. методов), которые не начинаются на «_»

    Input: 

    1
    Output: 

    bit_length
conjugate
denominator
imag
numerator
real

  4. (SecondMax) Найти второй максимум

    Ввести список и вывести второй максимум этого списка, т. е. элемент a∈S : ∃ b∈S : b>a и a⩾c ∀c∈S, c≠b. Если второго максимума нет, вывести NO.

    Input: 

    3,4,5,6,7
    Output: 

    6

  5. (Else) Точки в круге

    В первой строке ввести координаты центра круга и его радиус (числа x, y, r через запятую). Во второй строке ввести координаты точек (чётное количество чисел через запятую: x1, y1, x2, y2, ... xk, yk). Вывести YES, если все точки принадлежат кругу и NO, если не все.

    Input:

    x, y, r

    Output: 

    YES
  • Прочитать:

  • <!> Передать input() что-нибудь действительно нехорошее :)

  • (ParallelSegments) Параллельные отрезки

    Ввести восемь чисел через запятую — целочисленные координаты 4-х попарно несовпадающих точек A1, A2, A3 и A4: X1, Y1, X2, Y2, X3, Y3, X4, Y4. Вывести YES, если прямая A1A2 параллельна прямой A3A4 (или совпадает с ней), и NO — если не параллельна.

    Input: 

    1,2,7,14,8,8,18,28
    Output: 

    YES

  • (SectionShuffle) Перетасовать кортеж

    Ввести последовательность A объектов Python через запятую и вывести кортеж, состоящий из элементов последовательности, стоящих на чётных местах — в обратном порядке (включая A[0]), после которых идут элементы последовательности, стоящие на нечётных местах.

    Input: 

    '0', 1, 2, '3', 4, 5, '6', 7, 8, '9', 10, 11
    Output: 

    (10, 8, '6', 4, 2, '0', 1, '3', 5, 7, '9', 11)

  • (RepeatedString) Строка — повторение подстроки

    Ввести непустую строку s. Найти такое наибольшее число k и такую строку t, что s совпадает со строкой t, выписанной k раз подряд. Вывести k.

    Input: 

    abcabcabcabc
    Output: 

    4

  • (Labyrinth) Обход лабиринта

    Ввести заданный построчно лабиринт размером N×N. Каждая из N строк ввода содержит N символов: «.» — проходимый участок и «#» — непроходимый. Левый верхний и правый нижний участки лабиринта проходимы. С одного проходимого участка можно попасть на соседний либо по вертикали, либо по горизонтали. Проверить, можно ли попасть из левого верхнего участка в правый нижний, и вывести YES, если можно, и NO, если нельзя.

    Input: 

    ...........
.#.###.###.
.#...#...#.
.#.#####.#.
.#.....#.#.
##.###.###.
.....#.#.#.
.#.###.#.##
.#...#.#...
##.#.###.##
...#.......
    Output: 

    YES

  • <!> ввести W, H — размеры лабиринта и вывести представление достаточно случайного проходимого лабиринта для предыдущей задачи (обратите внимание на нескучные обои красивые неслучайные стены :) )

  • Прочитать в документации про строковые методы

  • (ReqSum) Сумма подпоследовательности

    Ввести число N, а на следующей строке — последовательность натуральных чисел через запятую. Проверить, является ли N суммой не более, чем 10 каких-либо элементов последовательности, и вывести YES или NO в зависимости от результата.

    Input: 

    21
1,2,3,4,5,6,7
    Output: 

    YES

  • (DiffLet) Количество разных символов

    Ввести строку (слова, разделённые пробелами), и вывести через пробел вначале слова, состоящие из повторения единственного символа (если таковые имеются), затем — слова, образованные всего из двух символов в любом количестве и сочетании, затем — из трёх и т. д. Слова с одинаковым количеством символов выводить в порядке их появления в строке.

    Input: 

        sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list
    Output: 

    --> new list sorted key=None, cmp=None, reverse=False) sorted(iterable,

  • (PopularWord) Самое популярное слово

    Ввести построчно текст, состоящий из пробелов, переводов строки и латинских букв, и заканчивающийся пустой строкой. Вывести слово, которое чаще других встречается в тексте, если оно такое одно, и ---, если таких слов несколько.

    Input: 

    Sed tempus ipsum quis eros tempus lacinia Cras finibus lorem ut lacinia egestas nunc nibh iaculis est convallis tincidunt mi mi sed nisl Sed porttitor aliquam elit ullamcorper tincidunt arcu euismod quis Mauris congue elit suscipit leo varius facilisis Cras et arcu sodales laoreet est vitae pharetra orci Integer eget nulla dictum aliquet justo semper molestie neque Maecenas bibendum lacus tincidunt auctor varius purus felis ullamcorper dui et laoreet ligula ex et risus Donec eget fringilla nibh Cras congue tincidunt accumsan Maecenas euismod eleifend elit ut rhoncus tortor sodales a Cras egestas finibus lorem non tempor tincidunt aera
    Output: 

    tincidunt

  • (MultTable) Таблица умножения на N

    Ввести через запятую M и N и вывести таблицу умножения от M×1 до M×N в столбик, где K-я строчка имеет вид __P_=__K_*_M. Между элементами стоят символы подчёркивания, причём перед P может быть ноль или больше подчёркиваний, а перед K — одно или больше, в остальных случаях подчёркивание одно. В результате символы = и * должны стоять друг под другом.

    Input: 

    7,11
    Output: 

    _7_=__1_*_7
14_=__2_*_7
21_=__3_*_7
28_=__4_*_7
35_=__5_*_7
42_=__6_*_7
49_=__7_*_7
56_=__8_*_7
63_=__9_*_7
70_=_10_*_7
77_=_11_*_7

Задачи для EJudge не могут включать в себя работу с ОС или модулями, так что просто упражнения:

  • (MaxSubst) Подстрока максимальной длины из разных букв

    Ввести строку и вывести ближайшую к началу подстроку максимальной длины, содержащую только различные символы.

    Input: 

    qweqweASDFGHASDFGASasdfghas123
    Output: 

    DFGASasdfgh

  • (GuessSigns) Вставить знаки в целочисленное выражение

    Ввести последовательность натуральных чисел через пробел (не более 12), и вывести YES, если можно ли между этими числами вставить произвольные знаки сложения или вычитания и один знак "=", чтобы получилось равенство. Вывести NO, если нельзя. Унарные операции и пропуск знака не допускаются.

    Input: 

    123 234 345 12
    Output: 

    YES

  • (ConstructIt) Проверить, можно ли собрать агрегат согласно инструкции

    Первая строка ввода — правило сборки агрегата вида «название_агрегата деталь1 деталь2 …», в ней сказано, из каких деталей можно собрать агрегат. Последующие строки ввода — либо аналогичные правила сборки деталей вида «деталь1 деталь2 …», либо состоят из одного слова «деталь» — в знак того, что такие детали есть на складе. Каждая деталь собирается не более, чем единственным способом. Последняя строка пустая. Вывести YES, если из деталей на складе можно собрать агрегат, и NO, если нельзя.

    Input: 

    Choo qw er ty ui
qw er ty
er ty ui
ty
ui
    Output: 

    YES

  • (SubModules) Ввести имя модуля и посчитать, сколько подмодулей в нём содержится

    Ввести имя модуля и посчитать, столько подмодуелй он содержит (солько объектов модуля сами являются модулями). Если имя не соответствует никакому модулю, вывести -1.

    Input: 

    os
    Output: 

    5
  • Прочитать:

  • (KdigNbase) K-значные N-ричные

    Ввести через запятую K и N (1<N<17), вывести в столбик все K-значные N-ричные числа в порядке возрастания (латинские буквы для цифр — большие, незначащие нули или пробелы не считаются).

    Input: 

    2,4
    Output: 

    10
11
12
13
20
21
22
23
30
31
32
33

  • (ParamForm) Параметрическая формула

    Первая строка содержит Python-совместимую формулу, в которой могут присутствовать названия переменных и элементы модуля math. В следующей строке через пробел в виде переменная=значение или переменная=начало_диапазона,конец_диапазона указаны допустимые целочисленные значения переменных (целочисленный диапазон включает и начальное, и конечное значения). Вывести наибольшее значение формулы на всех допустимых целочисленных значениях переменных.

    Input: 

    Param**2+Fun/6-Result+1
Param=3 Fun=-21,45 Result=5,15
    Output: 

    12

  • (WordSpot) Счётчик слов

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

    Input: 

    qwe sdf tyu qwe sdf try sdf qwe sdf rty sdf wer sdf wer
    Output: 

    qwe(7) sdf(12) tyu try rty wer(13)

  • (ByteReverse) Байты задом наперёд

    Ввести через запятую строку чисел типа «4-байтовое знаковое целое», переставить байты в занимаемой ими совместно памяти в обратном порядке, вывести в виде списка объектов типа «4-байтовое знаковое целое». Обратите внимание на то, что и «int», и «long int» на разных архитектурах имеют разную длину.

    Input: 

    -12,4,-345345345,12345
    Output: 

    [959447040, -1083020565, 67108864, -184549377]
  • Прочитать:

  • (CompareFields) Сравнение полей

    Реализовать класс Comparator, содержащий только поле value и метод compare, возвращающий результат сравнения value с полем value любого другого объекта (аналогичный работе стандартной функции cmp()). Если такого поля нет, метод возвращает 1.

    Input: 

       1 C = mod.Comparator(123)
   2 class Test: pass
   3 T = Test()
   4 T.value = 124
   5 print C.compare(T)
    Output: 

    -1

  • (SimpleVector) Вектора на плоскости

    Реализовать класс Vector, позволяющий

    • задавать двумерный вектор (из двух чисел)
    • вычислять вектор — сумму двух векторов
    • вычислять вектор — результат умножения вектора на число (или числа на вектор)
    • скалярно умножать вектор на вектор

    • преобразовывать вектор в строку вида |x,y|

    Input: 

       1 A = mod.Vector(1,2)
   2 B = mod.Vector(3,4)
   3 print A
   4 print A+B
   5 print A*B
   6 print 7*A
    Output: 

    |1,2|
|4,6|
11
|7,14|

  • (PrimitiveDot) Точки в N-мерном пространстве

    Реализовать клаcc Dot, позволяющий:

    • Задавать точку в N-мерном пространстве (с помощью N чисел, где N>0)

    • Преобразовывать точку в строку вида «X1,X2,…,XN»

    • Вычислять расстояние (distance()) между двумя точками пространства одинаковой размерности

    • Вычислять точку (middle()) — середину отрезка между двумя точками пространства одинаковой размерности

    • При попытке работы с такими же точками пространства, но разной размерности порождать исключение ValueError

    Input: 

       1 for A,B in (mod.Dot(1,2,3),mod.Dot(3,4,5)), (mod.Dot(1,2),mod.Dot(3)):
   2   print A
   3   try:
   4     print "{:.3f}".format(A.distance(B))
   5     print A.middle(B)
   6   except ValueError:
   7     print "ERROR"
    Output: 

    1,2,3
3.464
2.0,3.0,4.0
1,2
ERROR

  • (FakeField) Гласные поля

    Реализовать класс Vovel, у объекта которого можно получить значение любого поля, если имя этого поля состоит только из маленьких гласных латинских букв. Значение это — строка, совпадающая с именем поля, только состоящая из больших латинских букв. В противном случае поведение объекта должно быть естественным (вызывть исключение AttributeError, как минимум с тем же сообщением, что и «естественный» AttributeError в случае несуществующего поля). Реализовывать что-то, кроме получения значения поля, не надо.

    Input: 

    A = mod.Vovel()
print A.aoao
try:
  print A.field
except AttributeError, msg:
  print "ERROR",msg
    Output: 

    AOAO
ERROR Vovel instance has no attribute 'field'
  • Прочитать:

    • Раздел Data model (весь, можно несколько раз)

    • Всё по ссылкам выше

  • (SelfishTuple) Выворачиваемый кортеж

    Определить класс MTuple, проксирующий тип tuple, с добавлением в него единственной операции — унарного минуса (операция возвращает MTuple с элементами в обратном порядке). Прочие операции также должны возвращать MTuple вместо tuple.

    Input: 

    c=mod.MTuple(range(10))
print -(-c[2:6]+c[-1:2:-2])
print -c[7:9]+("Bdyshch","Bdyshch")
print {-c[3:5]:"QQ"}
    Output: 

    (3, 5, 7, 9, 2, 3, 4, 5)
(8, 7, 'Bdyshch', 'Bdyshch')
{(4, 3): 'QQ'}

  • (TrigonPea) Треугольная груша

    Создать три класса:

    1. Trigon, обозначающий треугольник:

      • заводится по трём сторонам

      • имеет методы square() (площадь) и perimeter() (периметр)

    2. Pea, обозначающий грушу круг

      • заводится (NB!) по трём сторонам вписанного треугольника

      • имеет методы square() и perimeter()

    3. TrigonPea (унаследованный от Trigon и Pea), обозначающий треугольную грушу

      • заводится по трём сторонам
      • периметр и площадь равны периметру и площади треугольника

      • имеет метод volume(), равный произведению периметра треугольника на площадь описанного круга

    Неравенство треугольника проверять не надо.

    Input: 

    t=mod.Trigon(3,4,5)
p=mod.Pea(3,4,5)
z=mod.TrigonPea(3,4,5)
print "{:.6f}".format(t.square())
print "{:.6f}".format(t.perimeter())
print "{:.6f}".format(p.square())
print "{:.6f}".format(z.volume())
print "{:.6f}".format(z.square())
    Output: 

    6.000000
12.000000
19.634954
235.619449
6.000000

  • Очередная алгоритмическая задачка, поупражнять мозг:

    (QuadChain) Прямоугольник из цепи

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

    Input: 

    1, 3, 2, 2, 4, 4
    Output: 

    YES

(необязательное)

  • FunctionCachier. Написать декоратор function_cachier, который возвращает функцию, значения которой не вычисляются заново при повторных обращениях. 

def f1(n):
  print 'f1 called'
  return n*n

@mod.function_cachier
def f2(n):
  print 'f2 called'
  return n*n*n

print len([ f1(n) for n in range(3)])
print len([ f1(n) for n in range(3)])
print len([ f2(n) for n in range(4)])
print len([ f2(n) for n in range(4)])

f1 called
f1 called
f1 called
3
f1 called
f1 called
f1 called
3
f2 called
f2 called
f2 called
f2 called
4
4
  • Усложнение: научить его работать с рекурсивными функциями. 

def f1(n):
  print 'f1 called'
  return n*n

def f2(n):
  print 'f2 called'
  return n*n*n

print len([ f1(n) for n in range(3)])

with mod.with_function_cachier(f2) as f:
  print len([ f(n) for n in range(5)])

f1 called
f1 called
f1 called
3
5
  • Усложнение: Сделать его повторно используемым между вызовами with, чтобы сохранялся однажды накопленный кэш функций.

  • Усложнение: Сделать его повторно используемым между вызовами программы ;)

Include: Ничего не найдено по регулярному выражению «== Д/З ==$».

Что дальше?

Мелочи и подчистка

Вопросы быстродействия

  • 1 ms vs. 1 µs
  • Быстродействие и ЗБЧ
  • Быстродействие и вычислительная сложность
  • Быстродействие и дзен Python (см. далее)
  • Действительные случаи потери быстродействия

Python Patterns - An Optimization Anecdote (довольно старое эссе Гвидо, здесь он ещё любил reduce() ;) ):

  • Rule number one: only optimize when there is a proven speed bottleneck. Only optimize the innermost loop. (This rule is independent of Python, but it doesn't hurt repeating it, since it can save a lot of work. :) )

  • Small is beautiful. Given Python's hefty charges for bytecode instructions and variable look-up, it rarely pays off to add extra tests to save a little bit of work.

  • Use intrinsic operations. An implied loop in map() is faster than an explicit for loop; a while loop with an explicit loop counter is even slower.

  • Avoid calling functions written in Python in your inner loop. This includes lambdas. In-lining the inner loop can save a lot of time.
  • Local variables are faster than globals; if you use a global constant in a loop, copy it to a local variable before the loop. And in Python, function names (global or built-in) are also global constants!

  • Try to use map(), filter() or reduce() to replace an explicit for loop, but only if you can use a built-in function: map with a built-in function beats for loop, but a for loop with in-line code beats map with a lambda function!

  • Check your algorithms for quadratic behavior. But notice that a more complex algorithm only pays off for large N - for small N, the complexity doesn't pay off. In our case, 256 turned out to be small enough that the simpler version was still a tad faster. Your mileage may vary - this is worth investigating.

  • And last but not least: collect data. Python's excellent profile module can quickly show the bottleneck in your code. if you're considering different versions of an algorithm, test it in a tight loop using the time.clock() function.

/!\ Разбор каких-то задач?

Дзен Python

import this:

  • The Zen of Python, by Tim Peters (structured by FrBrGeorge CO)

    1. Beautiful is better than ugly.
    2. Explicit is better than implicit.
    3. Simple is better than complex.
      • Complex is better than complicated.
    4. Flat is better than nested.
    5. Sparse is better than dense.
    6. Readability counts.
    7. Special cases aren't special enough to break the rules.
      • Although practicality beats purity.
    8. Errors should never pass silently.
      • Unless explicitly silenced.
    9. In the face of ambiguity, refuse the temptation to guess.
    10. There should be one — and preferably only one — obvious way to do it.
      • Although that way may not be obvious at first unless you're Dutch.
    11. Now is better than never.

      • Although never is often better than right now.

    12. If the implementation is hard to explain, it's a bad idea.

      • If the implementation is easy to explain, it may be a good idea.

    13. Namespaces are one honking great idea -- let's do more of those!

Дальнейшее движение

  • Изучение алгоритмического программирования на Python:
  • Инструментальная разработка и промышленное программирование
  • «Академическое» программирование
  • Сам Python и его реализации

EE: import antigravity

LecturesCMC/PythonIntro2014/HomeworkRules (последним исправлял пользователь FrBrGeorge 2014-11-20 21:06:00)