Науки о данных

И. В. Щуров, НИУ ВШЭ

Авторы задач в подборке: А. Зотов, И. Щуров.

На странице курса находятся дополнительные материалы.

Домашнее задание №3

За разные задачи можно получить разное число баллов. Если не указано обратное, задача весит 1 балл. Максимум за ДЗ можно набрать 23 балла. Вы можете решить больше задач, чем требуется, чтобы потренироваться.

Для предварительной проверки задания нужно сделать следующее:

  1. Скачать данный ipynb-файл на свой компьютер, открыть его в IPython Notebook/Jupyter.
  2. Активировать тесты (см. ниже).
  3. Вставить решение каждой задачи в ячейку для кода, следующую за его условием, там, где написан комментарий # YOUR CODE HERE. Отступ вашего кода должен составлять 4 пробела. Ничего не менять вокруг!
  4. Запустить ячейку, в которую вы вставили код с решением. Ввести какие-то входные данные, проверить визуально правильность вывода.
  5. Запустить следующую ячейку (в ней содержится тест). Если запуск ячейки с тестом не приводит к появлению ошибки (assertion), значит, всё в порядке, задача решена. Если приводит к появлению ошибки, значит, тест не пройден и нужно искать ошибку.

Внимание! Если в какой-то момент забыть ввести входные данные и перейти на следующую ячейку, есть риск, что Notebook перестанет откликаться. В этом случае надо перезапустить ядро: Kernel → Restart. При этом потеряются все значения переменных, но сам код останется.

Чтобы сдать ДЗ, его надо загрузить в nbgr-x в виде ipynb-файла. Получить ipynb-файл можно, выбрав в Jupyter пункт меню File → Download as... → IPython Notebook (.ipynb).

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

Активировать тесты

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

In [ ]:
# Фабрика тестов для проверки программ, принимающих данные через input()

from collections import deque

class Tester(object):
    def __init__(self, inp):
        self.outputs = []
        self.inputs = deque(inp)
    def print(self, *args, sep = " ", end = "\n"):
        text = sep.join(map(str, args)) + end
        newlines = text.splitlines(keepends=True)
        if self.outputs and self.outputs[-1] and self.outputs[-1][-1] != "\n" and newlines:
            self.outputs[-1] += newlines[0]
            self.outputs.extend(newlines[1:])
        else:
            self.outputs.extend(newlines)
            
    def input(self, *args):
        assert self.inputs, "Вы пытаетесь считать больше элементов, чем предусмотрено условием"
        return self.inputs.popleft()
    def __enter__(self):
        global print
        global input
        print = self.print
        input = self.input
        return self.outputs
    def __exit__(self, *args):
        global print
        global input
        del print
        del input

Часть 1: функции

Задача 1 (1 балл).

Написать функцию times2(x), принимающую на вход число x и возвращающую это число, увеличенное в два раза.

Подсказка. Решение должно начинаться со строчки

def times2(x):

Подсказка. В этом ДЗ вам не придётся вводить данные с клавиатуры. Вместо этого вы будете передавать входные данные функции в виде аргументов.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert(times2(1) == 2)
assert(times2(2) == 4)
assert(times2(-2) == -4)
assert(times2(0) == 0)
assert(times2(100) == 200)
with Tester([]) as t:
    times2(4)
    assert len(t) == 0, "функция ничего не должна печатать"

print("Окей! :)")

Задача 2 (1 балл)

Написать функцию is_odd(n), проверяющую, является ли данное число n нечётным. Она должна возвращать True, если число нечётное, и False, если чётное. Функция не должна ничего выводить на экран!

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert(is_odd(1))
assert(not is_odd(2))
assert(not is_odd(0))
assert(is_odd(101))
with Tester([]) as t:
    is_odd(1)
    assert len(t) == 0, "функция ничего не должна печатать"
print("Отлично! Едем дальше.")

Задача 3 (1 балл)

Написать функцию hello(n), выводящую на экран строчку Hello n раз подряд и ничего не возвращающую. Например, вызов hello(3) должен привести к выводу на экран

Hello
Hello
Hello
In [ ]:
"# YOUR CODE HERE"
In [ ]:
for n in range(100):
    with Tester([]) as t:
        x = hello(n)
        assert x is None, "функция ничего не должна возвращать"
        assert len(t) == n, "функция должна выводить ровно n строк"
        assert "".join(t).strip() == ("Hello\n" * n).strip(), "функция вывела что-то не то"

Задача 4 (2 балла)

Написать функцию num_div(n), вычисляющую, сколько у данного числа n делителей (включая 1 и само это число). Функция должна работать с целыми положительными числами.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert(num_div(1) == 1)
assert(num_div(2) == 2)
assert(num_div(3) == 2)
assert(num_div(100) == 9)
assert(num_div(1000) == 16)
assert(num_div(139) == 2)
assert(num_div(1289237) == 2)
print("Похоже на правду!")

Задача 5 (1 балл)

Написать функцию is_prime(n), проверяющую, является ли данное число n простым. Примечание. Можете использовать ранее написанную функцию num_div(n). (Вопрос: Является ли это самым эффективным способом решения данной задачи?)

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert(is_prime(2) and 
       is_prime(3) and 
       is_prime(139) and 
       is_prime(617) and 
       is_prime(293) and 
       not is_prime(12) and 
       not is_prime(13*7))
print("Отлично! Давайте сделаем что-нибудь посложнее.")

Задача 6 (2 балла)

Написать функцию med3(x,y,z), возвращающую медиану из чисел x, y, z (то есть то из этих чисел, которое будет стоять посередине, если их упорядочить). Пользоваться какими-либо библиотечными функциями нельзя! Сортировкой тоже пользоваться нельзя. И функциями min и max тоже нельзя.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
from itertools import permutations
def test_med3(x,y,z,m):
    for t in permutations([x,y,z]):
        assert(med3(*t) == m)
test_med3(1,1,1,1)
test_med3(1,1,2,1)
test_med3(1,2,2,2)
test_med3(1,2,3,2)
test_med3(0,1,2,1)
test_med3(100,200,300,200)
test_med3(100,101,1000,101)
print("Ура! Получилось!")

Задача 7 (2 балла)

Написать функцию is_increasing(lst, strict), проверяющую, является ли список lst возрастающим. Если параметр strict установлен в True, нужно проверять строгое возрастание, иначе нестрогое. Иными словами, функция должна возвращать True, если каждый элемент списка не меньше (если strict установлен в False) или строго больше (если strict установлен в True) предыдущего, и False в противном случае. Если strict не указан, функция должна считать, что strict установлен в True.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert is_increasing([1, 2, 3, 4, 5]) == True
assert is_increasing([1, 10, 15, 16, 17]) == True
assert is_increasing([5]) == True
assert is_increasing([5, 5]) == False
assert is_increasing([5, 6, 7, 7]) == False
assert is_increasing([5, 6, 7, 8, 7]) == False
assert is_increasing([2, 1, 5, 6]) == False

assert is_increasing([1, 1], strict=True) == False
assert is_increasing([1, 1], strict=False) == True

assert is_increasing([1, 2, 3, 3], strict=True) == False
assert is_increasing([1, 2, 3, 3], strict=False) == True
assert is_increasing([1, 2, 3, 2], strict=False) == False
assert is_increasing(list(range(10000))) == True
assert is_increasing([3, 2, 3]) == False

Задача 8

Написать функцию average(list_of_numbers), которая принимает на вход список чисел и возвращает его среднее арифметическое.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert average([5]) == 5
assert average([0]) == 0
assert average([4, 6]) == 5
assert average([1, 2, 3, 4, 5, 6, 7, 8, 9]) == 5
assert average([1, 100, 200, 300]) == 150.25

Задача 9

Написать функцию average_of, которая принимает на вход несколько чисел и возвращает их среднее арифметическое. В отличие от предыдущей задачи, здесь функция должна принимать на вход не один список, а несколько чисел. Примеры см. в тесте.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert average_of(5) == 5
assert average_of(0) == 0
assert average_of(4, 6) == 5
assert average_of(1, 2, 3, 4, 5, 6, 7, 8, 9) == 5
assert average_of(1, 100, 200, 300) == 150.25

Задача 10 (2 балла)

Написать функцию variance(numbers, unbiased), принимающую на вход список вещественных чисел numbers и булевскую переменную unbiased и возвращающую выборочную дисперсию для numbers. Если параметр unbiased установлен в True, должна возвращаться исправленная (несмещённая) выборочная дисперсия. Если параметр unbiased не указан, он считается установленным в True. Вы можете пользоваться ранее созданными функциями, но не можете пользоваться никакими библиотеками.

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

In [ ]:
"# YOUR CODE HERE"
In [ ]:
import numpy as np
np.random.seed(42)
for i in [3, 10, 100, 1000, 10000]:
    num = np.random.uniform(size=i)
    assert np.isclose(variance(num), np.var(num, ddof=1))
    assert np.isclose(variance(num, unbiased=False), np.var(num, ddof=0))
    assert np.isclose(variance(num, unbiased=True), np.var(num, ddof=1))

Задача 11 (2 балла)

Напишите функцию cov(u, v), принимающую на вход два списка чисел u и v, имеющих одинаковую длину, и вычисляющую выборочный коэффициент ковариации для u и v.

В этой задаче запрещено использовать len и range, можно использовать ранее написанную функцию average и обязательно использовать списковые включения и функцию zip.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
import numpy as np
np.random.seed(42)
for i in [3, 10, 100, 1000, 10000]:
    u = np.random.uniform(size=i)
    v = np.random.normal(size=i)
    assert np.isclose(cov(u, v), np.cov(u, v, bias=True)[0, 1])

Задача 12 (1 балл)

Написать функцию swap(some_list, i, j), меняющую в списке some_list местами элементы с индексами i и j. Функция должна модифицировать переданный список some_list и не должна ничего возвращать.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
this_list = [1, 2, 10, 35, 20]
x = swap(this_list, 0, 4)
assert x is None, "Ваша функция ничего не должна возвращать"
assert this_list == [20, 2, 10, 35, 1]

swap(this_list, 3, 3)
assert this_list == [20, 2, 10, 35, 1]

this_list = [1, 2, 10, 35, 20] * 100
swap(this_list, 1, len(this_list) - 2)
assert this_list == [1, 35, 10, 35, 20] + [1, 2, 10, 35, 20] * 98 + [1, 2, 10, 2, 20]

Задача 13 (1 балл)

Написать функцию swapped(some_list, i, j), возвращающую новый список, совпадающий со списком some_list, в котором поменяли местами элементы с индексами i и j. Список some_list не должен меняться.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
this_list = [1, 2, 10, 35, 20]
backup_list = this_list.copy()
x = swapped(this_list, 0, 4)
assert this_list == backup_list, "Исходный список не должен изменяться"
assert x == [20, 2, 10, 35, 1]

assert swapped([1, 2, 3, 4], 2, 2) == [1, 2, 3, 4]

this_list = [1, 2, 10, 35, 20] * 100
assert swapped(this_list, 1, len(this_list) - 2) == ([1, 35, 10, 35, 20] +
                                                     [1, 2, 10, 35, 20] * 98 + 
                                                     [1, 2, 10, 2, 20])

Задача 14 (2 балла)

Написать функцию my_map(f, some_list), которая принимает на вход функцию f и список some_list и возвращает новый список, полученный путём применения функции f к каждому элементу списка some_list. Например, my_map(str, [1, 2, 3]) должен вернуть список, получающийся как [str(1), str(2), str(3)], то есть ['1', '2', '3'].

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert my_map(str, [1, 2, 3]) == ['1', '2', '3']
assert my_map(int, ['12', '34', '56', '789']) == [12, 34, 56, 789]
assert my_map(lambda x: x + 1, [1, 2, 3, 4]) == [2, 3, 4, 5]
assert my_map(None, []) == []
assert my_map(lambda x: x, list(range(10000))) == list(range(10000))
print("Хорошо! Кстати, примерно то же самое делает встроенная функция map")

Задача 15 (3 балла)

Напишите функцию caesar(s, shift), реализующую шифр Цезаря. Функция должна принимать строку для шифрования s, состоящую из букв русского или английского алфавита (в одной строке не может быть сразу двух алфавитов), и значение сдвига shift. В качестве ответа функция должна вернуть зашифрованную строку. Гарантируется, что все буквы строчные. Если значение сдвига в функцию не передается (т.е. функция вызывается как caesar(s)), считайте его равным единице. В русском алфавите есть буква «ё»!

Подсказка: Строки, как и списки, можно итерировать в цикле (например, for l in word:, где word — строка, а l — переменная, которая поочередно принимает значение всех символов, входящих в эту строку).

Подсказка 2: У списков (как и у строк) есть метод .index().

Примеры

Вызов функции

caesar("abcz")

Возвращаемое значение

"bcda"

Вызов функции

caesar("hello world", 3)

Возвращаемое значение

"khoor zruog"

Вызов функции

caesar("питон", 8)

Выходные данные

"чръцх"
In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert caesar('abcz') == 'bcda'
assert caesar('hello', 3) == 'khoor'
assert caesar('питон', 8) == 'чръцх'
assert caesar('питон', 33) == 'питон'
assert caesar('mynes', 99) == 'htizn'
assert caesar('mynes', 26) == 'mynes'
assert caesar('my nes', 25) == 'lx mdr'
assert caesar('и ты брут', 18) == 'ъ дм твед'
assert caesar('et tu brute', 4) == 'ix xy fvyxi'
assert caesar('the cake is a lie', 0) == 'the cake is a lie'
assert caesar('the cake is a lie', 42) == 'jxu sqau yi q byu'
assert caesar("ё") == "ж"

Задача 16 (4 балла)

Это необязательная задача. Её можно смело пропустить.

Рассмотрим некоторое арифметическое выражение, которое может содержать скобки — квадратные или круглые. Каждая скобка должна корректно закрываться скобкой такого же типа. Например, 5 * [1 + 2 + (3 + 4) + 5] — корректное выражение, а выражение 4 + (2 + некорректное, потому что скобка открылась и не закрылась. Также некорректным будет выражение [1 + (2 + 3] + 4), потому что, например, первая квадратная скобка должна была закрыться также квадратной, а закрылась круглой.

Написать функцию check_brackets(expr), принимающую на вход строку, содержащую выражение, и возвращающую True, если выражение корректное, и False в противном случае.

Подсказка. Вам нужно запоминать, в каком порядке какие скобки открывались. Когда скобка корректно закрылась, она вас больше не интересует.

In [ ]:
"# YOUR CODE HERE"
In [ ]:
assert check_brackets('5 * [1 + 2 + (3 + 4) + 5]')
assert not check_brackets('4 + (2 + ')
assert not check_brackets('[1 + (2 + 3] + 4)')
assert check_brackets('[]()[][[([(([]))])]]')
assert not check_brackets(']')
assert not check_brackets(')')
assert not check_brackets('[)]')
assert not check_brackets('[)()]')
assert not check_brackets('[)](')
assert not check_brackets("[[([(]))]]")
assert not check_brackets('[')
assert not check_brackets('(')
assert not check_brackets('(' * 100 + ')' * 99)
assert  check_brackets('(' * 1000 + ')' * 1000)

Лирическое отступление: рекурсия

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

In [ ]:
def factorial(x):
    if x <= 0: 
        return 1
    else:
        return x * factorial(x - 1)
factorial(5)

Задача 17 (4 балла)

Напишите функцию perm, которая принимает массив чисел и печатает (командой print()) все возможные его перестановки. Пользоваться любыми библиотеками запрещено.

Эту задачу тоже можно пропустить. Но можно и сделать :)

Примеры:

Вызов функции

perm([1, 2, 3])

Выходные данные

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
In [ ]:
"# YOUR CODE HERE"
In [ ]:
from ast import literal_eval

test_data = [
    ([1, 2], [[1, 2], [2, 1]]),
    ([3, 4, 5], [[3, 4, 5], [3, 5, 4], [4, 3, 5], [4, 5, 3], [5, 3, 4], [5, 4, 3]]),
    ([4, 3, 5], [[3, 4, 5], [3, 5, 4], [4, 3, 5], [4, 5, 3], [5, 3, 4], [5, 4, 3]]),
    ([12, 10, 8, 14], [[8, 10, 12, 14], [8, 10, 14, 12], [8, 12, 10, 14], [8, 12, 14, 10],
    [8, 14, 12, 10], [8, 14, 10, 12], [10, 8, 12, 14], [10, 8, 14, 12], [10, 12, 8, 14],
    [10, 12, 14, 8], [10, 14, 12, 8], [10, 14, 8, 12], [12, 10, 8, 14], [12, 10, 14, 8],
    [12, 8, 10, 14], [12, 8, 14, 10], [12, 14, 8, 10], [12, 14, 10, 8], [14, 10, 12, 8],
    [14, 10, 8, 12], [14, 12, 10, 8], [14, 12, 8, 10], [14, 8, 12, 10], [14, 8, 10, 12]])]
for inp, answer in test_data:
    with Tester([inp]) as t_out:
        perm(inp)
        assert sorted([literal_eval(y) for y in t_out]) == sorted(answer), "Что-то пошло не так"
print("Ура, всё верно!")