|
После завершения работы над каждым вопросом фиксируй изменения (делай коммит): Также не возбраняется в любое время проталкивать изменения на GitHub: |
Связные списки
Вопрос 1: Длина глубокого связного списка
Связный список, содержащий один или несколько связных списков в качестве элементов, называют глубоким. Напиши функцию deep_len, которая принимает (вероятно, глубокий) связный список и возвращает его глубокую длину. То есть длину с учётом элементов вложенных связных списков. Посмотри на доктесты, чтобы удостовериться, что ты правильно понимаешь, что надо сделать.
Чтобы проверить, что что-то является экземпляром чего-то, используй isinstance.
|
Часами измеряется время, а временем жизнь человеческая; но чем, скажи, измеришь ты глубину Восточного океана?
def deep_len(lnk):
"""Возвращает «глубокий» размер связного списка с возможными вложениями.
>>> deep_len(Link(1, Link(2, Link(3))))
3
>>> deep_len(Link(Link(1, Link(2)), Link(3, Link(4))))
4
>>> levels = Link(Link(Link(1, Link(2)), \
Link(3)), Link(Link(4), Link(5)))
>>> print(levels)
<<<1 2> 3> <4> 5>
>>> deep_len(levels)
5
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Порядки роста
Вопрос 2
Определи порядок роста is_prime в терминах n.
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return TrueОпредели порядок роста bar в терминах n.
def bar(n):
i, sum = 1, 0
while i <= n:
sum += biz(n)
i += 1
return sum
def biz(n):
i, sum = 1, 0
while i <= n:
sum += i**3
i += 1
return sumОпредели порядок роста foo в терминах n, где n является длиной lst. Считай, что срез списка и получение длины списка выполняются за константное время.
def foo(lst, i):
mid = len(lst) // 2
if mid == 0:
return lst
elif i > 0:
return foo(lst[mid:], -1)
else:
return foo(lst[:mid], 1)| Ответ на этот вопрос не нужно сдавать. Просто проверь свои знания. |
Рекурсия и древовидная рекурсия
Вопрос 3: Подпоследовательности
Подпоследовательность последовательности S — это последовательность элементов из S, следующих в том же порядке, что и в S, однако некоторые элементы могут быть пропущены. То есть списки [], [1, 3], [2] и [1, 2, 3] — некоторые (но не все) подпоследовательности [1, 2, 3]. Напиши функцию, которая принимает список и возвращает список списков, где вложенные списки являются подпоследовательностями.
Для выполнения этого задания рекомендуется сначала сделать функцию insert_into_all, принимающую значение item и список списков nested_list и возвращающую исходный список списков, в котором в каждом вложенном списке в начало вставлен элемент item.
def insert_into_all(item, nested_list):
"""В предположении, что nested_list — это список списков, возвращает новый
список, включающий всё, что было в nested_list, но к каждому вложенному
списку в начало добавляется элемент item.
>>> nl = [[], [1, 2], [3]]
>>> insert_into_all(0, nl)
[[0], [0, 1, 2], [0, 3]]
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"
def subseqs(s):
"""В предположении, что S является списком, возвращает вложенный список
всевозможных подпоследовательностей элементов исходного списка.
Подпоследовательности могут быть добавлены в любом порядке.
>>> seqs = subseqs([1, 2, 3])
>>> sorted(seqs)
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
>>> subseqs([])
[[]]
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Вопрос 4: Увеличивающиеся подпоследовательности
Теперь наложим на подпоследовательности дополнительное ограничение — они должны быть неубывающими, то есть для любых двух соседних элементов должно быть верным то, что второй элемент не меньше первого. Например, [1, 3, 2] — это подпоследовательность [1, 3, 2, 4], но поскольку 2 < 3, эту подпоследовательность следует исключить.
Заполни пропуски в коде функции inc_subseqs. Можно считать, что исходный список содержит только положительные значения.
Можешь использовать функцию insert_into_all.
|
def inc_subseqs(s):
"""В предположении, что S является списком, возвращает вложенный список
всевозможных подпоследовательностей элементов исходного списка, за
исключением подпоследовательностей с убывающим порядком хотя бы двух
соседних элементов. Подпоследовательности могут быть добавлены в любом порядке.
>>> seqs = inc_subseqs([1, 3, 2])
>>> sorted(seqs)
[[], [1], [1, 2], [1, 3], [2], [3]]
>>> inc_subseqs([])
[[]]
>>> seqs2 = inc_subseqs([1, 1, 2])
>>> sorted(seqs2)
[[], [1], [1], [1, 1], [1, 1, 2], [1, 2], [1, 2], [2]]
"""
def subseq_helper(s, prev):
if not s:
return ____________________
elif s[0] < prev:
return ____________________
else:
a = ______________________
b = ______________________
return insert_into_all(________, ______________) + ________________
return subseq_helper(____, ____)Объекты
Вопрос 5: Клавиатура
Хотелось бы сделать класс Keyboard, который принимал бы некоторое количество кнопок Button и хранил бы их в словаре. Ключи словаря были бы целыми числами, кодирующими положение кнопки на клавиатуре, значения были бы собственно кнопками. Заполни методы класса Keyboard в соответствии с их описаниями. Изучи доктесты, чтобы в точности понимать, что требуется сделать.
class Keyboard:
"""Класс Keyboard принимает некоторое количество кнопок Button, и имеет
словарь для сопоставления положения кнопок (ключи) и кнопок Button (значения).
>>> b1 = Button(0, "H")
>>> b2 = Button(1, "I")
>>> k = Keyboard(b1, b2)
>>> k.buttons[0].key
'H'
>>> k.press(1)
'I'
>>> k.press(2) #Тут нет кнопки
''
>>> k.typing([0, 1])
'HI'
>>> k.typing([1, 0])
'IH'
>>> b1.times_pressed
2
>>> b2.times_pressed
3
"""
def __init__(self, *args):
"*** ТВОЙ КОД ЗДЕСЬ ***"
def press(self, info):
"""Принимает положение нажатой кнопки и возвращает результат"""
"*** ТВОЙ КОД ЗДЕСЬ ***"
def typing(self, typing_input):
"""Принимает список положений нажатых кнопок и возвращает
результирующую последовательность результатов нажатий"""
"*** ТВОЙ КОД ЗДЕСЬ ***"
class Button:
def __init__(self, pos, key):
self.pos = pos
self.key = key
self.times_pressed = 0Nonlocal
Вопрос 6: Усовершенствованный счётчик
Дополни определение функции make_advanced_counter_maker, которая создаёт счётчики. Эти счётчики могут не только изменять собственное состояние, но и состояние, общее для всех счётчиков. Вдобавок они поддерживают сброс.
def make_advanced_counter_maker():
"""Создаёт функцию, которая создает счётчики, понимающие сообщения
"count", "global-count", "reset", и "global-reset".
Смотри на примеры:
>>> make_counter = make_advanced_counter_maker()
>>> tom_counter = make_counter()
>>> tom_counter('count')
1
>>> tom_counter('count')
2
>>> tom_counter('global-count')
1
>>> jon_counter = make_counter()
>>> jon_counter('global-count')
2
>>> jon_counter('count')
1
>>> jon_counter('reset')
>>> jon_counter('count')
1
>>> tom_counter('count')
3
>>> jon_counter('global-count')
3
>>> jon_counter('global-reset')
>>> tom_counter('global-count')
1
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Изменяемые списки
Вопрос 7: Диаграмма окружения
Нарисуй диаграмму окружения для следующей программы.
|
Вот что надо помнить:
|
def got(lst, el, f):
welcome = []
for e in lst:
if e == el:
el = f(lst[1:], 2, welcome)
return lst[3:] + welcome
def avocadis(lst, i, lst0):
lst0.append(lst.pop(i))
return len(lst0)
bananis = [1, 6, 1, 6]
n = bananis[3]
we = got(bananis, n, avocadis)| Ответ на этот вопрос не нужно сдавать. Просто проверь свои знания. |
Вопрос 8: Торговля
На рынке целых чисел каждый участник владеет списком положительных целых чисел для продажи. Два продавца при встрече могут обменяться наименьшими возможными префиксами своих списков. Под префиксом будем понимать срез, начинающийся с нуля.
Напиши функцию trade для обмена первых m элементов списка первого продавца на первые n элементов списка второго продавца. Обмен возможен, только если суммы обмениваемых элементов совпадают и суммы малы настолько, насколько это возможно. Если условия не соблюдены, функция должна вернуть строку Нет! и ничего не менять в списках, в противном случае списки должны измениться и результатом должна быть строка По рукам!.
|
Припомни, что в списке через присвоение можно изменить целый срез. Для этого слева от знака равенства нужно указать срез Также не забывай, что начальный и конечный индексы списка в срезе можно опускать. То есть |
def trade(first, second):
"""Производит обмен наименьшими префиксами (подпоследовательностями) списков
first и second, которые одинаковы по сумме элементов.
>>> a = [1, 1, 3, 2, 1, 1, 4]
>>> b = [4, 3, 2, 7]
>>> trade(a, b) # Меняет 1+1+3+2=7 на 4+3=7
'По рукам!'
>>> a
[4, 3, 1, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c = [3, 3, 2, 4, 1]
>>> trade(b, c)
'Нет!'
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[3, 3, 2, 4, 1]
>>> trade(a, c)
'По рукам!'
>>> a
[3, 3, 2, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[4, 3, 1, 4, 1]
"""
m, n = 1, 1
"*** ТВОЙ КОД ЗДЕСЬ ***"
if False: # измени эту строку!
first[:m], second[:n] = second[:n], first[:m]
return 'По рукам!'
else:
return 'Нет!'Итераторы и генераторы
Вопрос 9: Перестановки
Для заданной последовательности уникальных элементов перестановкой будет являться список, содержащий все элементы исходной последовательности в произвольном порядке. Например, [2, 1, 3], [1, 3, 2] и [3, 2, 1] — это перестановки последовательности [1, 2, 3].
Дополни функцию permutations — функцию-генератор, принимающую последовательность seq и возвращающую генератор, который выдаёт все перестановки seq.
Перестановки могут выдаваться в любом порядке. Доктесты проверяют выдачу всех возможных перестановок, но без учёта порядка выдачи. Встроенная функция sorted принимает итерируемый объект и возвращает список всех выданных значений, упорядочивая его в возрастающем порядке.
Твоё решение не должно противоречить приведённой заготовке.
Если у тебя есть перестановки всех элементов за исключением первого, как это использовать для получения всех перестановок lst?
|
def permutations(seq):
"""Генерирует все перестановки заданной последовательности. Каждая
перестановка — это список элементов исходной последовательности в другом
порядке. Перестановки могут выдаваться в любом порядке.
>>> perms = permutations([100])
>>> type(perms)
<class 'generator'>
>>> next(perms)
[100]
>>> try:
... next(perms)
... except StopIteration:
... print('Больше вариантов нет!')
Больше вариантов нет!
>>> sorted(permutations([1, 2, 3])) # Возвращает отсортированный список результатов
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> sorted(permutations((10, 20, 30)))
[[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
>>> sorted(permutations("ab"))
[['a', 'b'], ['b', 'a']]
"""
if ____________________:
yield ____________________
else:
for perm in _____________________:
for _____ in ________________:
_________________________Рекурсивные объекты
Вопрос 10: Связный список в строку
Umputun и Bobuk предпочитают разные способы отображения структур связных списков. Umputun считает, что наше всё — это диаграммы «контейнер-и-указатель», тогда как Bobuk предпочитает более футуристичный стиль (если вы понимаете, о чём я).
Напиши функцию make_to_string, которая возвращает функцию, преобразующую связный список в строку с заданным стилем.
|
Для преобразования чисел в строки воспользуйся функцией |
def make_to_string(front, mid, back, empty_repr):
""" Возвращает функцию, которая преобразует связные списки в строки.
>>> umputun_to_string = make_to_string("[", "|-]-->", "", "[]")
>>> bobuk_to_string = make_to_string("(", " . ", ")", "()")
>>> lst = Link(1, Link(2, Link(3, Link(4))))
>>> umputun_to_string(lst)
'[1|-]-->[2|-]-->[3|-]-->[4|-]-->[]'
>>> umputun_to_string(Link.empty)
'[]'
>>> bobuk_to_string(lst)
'(1 . (2 . (3 . (4 . ()))))'
>>> bobuk_to_string(Link.empty)
'()'
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Вопрос 11: Отображение дерева
Определи функцию tree_map, которая принимает дерево t и функцию одного аргумента fn и возвращает новое дерево, полученное из исходного применением функции fn к узловым значениям.
def tree_map(fn, t):
"""Применяет функцию fn ко всем элементам дерева t и возвращает новое дерево
с результатами.
>>> numbers = Tree(1,
... [Tree(2,
... [Tree(3),
... Tree(4)]),
... Tree(5,
... [Tree(6,
... [Tree(7)]),
... Tree(8)])])
>>> print(tree_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
>>> print(numbers)
1
2
3
4
5
6
7
8
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Вопрос 12: Дальняя дорога
Реализуй функцию long_paths, которая возвращает список всех путей в дереве, длина которых не меньше, чем n. Путь в дереве — это связный список узловых значений, который начинается в корне дерева и продолжается до листа. Длина пути — это количество рёбер (на один меньше, чем количество узлов в пути). Пути формируются слева направо. Посмотри доктесты, чтобы точно понимать, что требуется.
def long_paths(tree, n):
"""Возвращает список всех путей в дереве, которые не короче чем n.
>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12, [Tree(13, [Tree(14)])])])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> for path in long_paths(whole, 2):
... print(path)
...
<0 1 2>
<0 1 3 4>
<0 1 3 4>
<0 1 3 5>
<0 6 7 8>
<0 6 9>
<0 11 12 13 14>
>>> for path in long_paths(whole, 3):
... print(path)
...
<0 1 3 4>
<0 1 3 4>
<0 1 3 5>
<0 6 7 8>
<0 11 12 13 14>
>>> long_paths(whole, 4)
[Link(0, Link(11, Link(12, Link(13, Link(14)))))]
"""
"*** ТВОЙ КОД ЗДЕСЬ ***"Опять порядки роста
Вопрос 13: Бум!
Определи временной порядок роста для функции boom.
def boom(n):
sum = 0
a, b = 1, 1
while a <= n*n:
while b <= n*n:
sum += (a*b)
b += 1
b = 0
a += 1
return sumОпредели порядок роста для функции zap.
def boom(n):
sum = 0
a, b = 1, 1
while a <= n*n:
while b <= n*n:
sum += (a*b)
b += 1
b = 0
a += 1
return sumdef zap(n):
i, count = 1, 0
while i <= n:
while i <= 5 * n:
count += i
print(i / 6)
i *= 3
return count