Статистика и открытые данные

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

Основано на задачах отсюда и отсюда. Авторы задач в подборке: А. Зотов, И. Щуров.

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

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

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

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

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

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

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

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

Запустите следующие ячейку, чтобы иметь возможность запускать тесты. Эту операцию нужно проделывать каждый раз, когда вы перезапускаете ядро. Если какой-то из тестов говорит NameError: name 'Tester' is not defined, нужно запустить эту ячейку ещё раз.

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 балл).

Написать функцию 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 (то есть то из этих чисел, которое будет стоять посередине, если их упорядочить). Пользоваться какими-либо библиотечными функциями нельзя! Сортировкой тоже пользоваться нельзя.

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

Задача 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))

Задача 11 (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]

Задача 12 (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])

Задача 13 (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'

Задача 14 (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)

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

Напишите рекурсивную функцию ackermann(m, n), принимающую на вход значения $m$ и $n$ и возвращающую значение функции Аккермана $A(m, n)$. Функция Аккермана задается следующей формулой:

$A(m,n)=\begin{cases} n+1, & m=0\\ A(m-1, 1), &m>0, n=0\\ A(m-1, A(m, n-1)), &m>0, n>0 \end{cases}$

Циклами и библиотечными функциями пользоваться запрещено.

Внимание! Функция Аккермана растет очень быстро, и поэтому ее вычисление для больших чисел может занять продолжительное время. Мы не советуем вам тестировать свое решение при $m>3$. :)

In [ ]:
# YOUR CODE HERE
In [ ]:
assert ackermann(0, 0) == 1
assert ackermann(1, 1) == 3
assert ackermann(2, 2) == 7
assert ackermann(3, 3) == 61
assert ackermann(3, 5) == 253
assert ackermann(2, 4) == 11
assert ackermann(2, 8) == 19

Задача 16 (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("Ура, всё верно!")