Программирование

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

Данный notebook является набором задач по курсу «Программирование» (Магистерская программа «Журналистика данных», НИУ ВШЭ, 2018-19).

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

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

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

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

  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).

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

Запустите следующие ячейку, чтобы иметь возможность запускать тесты. Эту операцию нужно проделывать каждый раз, когда вы перезапускаете ядро. Если какой-то из тестов говорит 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):

Внимание! Во всех задачах этой домашки, включая эту, не требуется ничего вводить с клавиатуры! В ваших функциях не должна использоваться функция input. Вы можете проверить, как функция работает, запуская её с различными аргументами. Например, после того, как вы написали свою функцию, наберите (в новой ячейке) times2(10) и посмотрите на результат. Что будет, если число 10 заменить на что-нибудь другое?

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_positive(n), проверяющую, является ли число n положительным. Она должна возвращать True, если является, и False, если не является. Функция не должна ничего выводить на экран!

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

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

Написать функцию signum(n), возвращающую число 1, если n положительно, -1, если отрицательно, и 0, если n равно нулю.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert signum(100) == 1
assert signum(1) == 1
assert signum(0) == 0
assert signum(-1) == -1
assert signum(-99) == -1
assert signum(int(1e10)) == 1
assert signum(int(-1e12)) == -1
print("Хорошо!")

Задача 4 (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(), "функция вывела что-то не то"
print("ОК")

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

Написать функцию pack_to_list(s), принимающую на вход строку s и возвращающую список, единственным элементом которого является строка s. Например, pack_to_list("Hello") должна вернуть список ["Hello"].

In [ ]:
# YOUR CODE HERE
In [ ]:
assert pack_to_list("Hello") == ["Hello"]
assert pack_to_list("100") == ["100"]
assert pack_to_list("This is a test") == ["This is a test"]
print("Хорошо, продолжаем!")

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

Напишите функцию sumdiff(a, b), которая принимает на вход два целых числа a и b и возвращает список, состоящий из двух элементов. Первым элементом является сумма a и b, а вторым — их разность (a - b).

In [ ]:
# YOUR CODE HERE
In [ ]:
assert sumdiff(1, 1) == [2, 0]
assert sumdiff(1, -1) == [0, 2]
assert sumdiff(10, 20) == [30, -10]
assert sumdiff(0, 0) == [0, 0]
print("Ага!")

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

Напишите функцию greater_lst(nums), принимающую на вход список nums, состоящий из двух чисел. Она должна вернуть True, если первое число в этом списке больше второго, и False в противном случае.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert greater_lst([1, 2]) is False
assert greater_lst([2, 1]) is True
assert greater_lst([1, 1]) is False
assert greater_lst([100, 1]) is True
assert greater_lst([1, -1]) is True
assert greater_lst([-1, 0]) is False
print("Да")

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

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

Подсказка. Узнать количество элементов в списке можно с помощью функции len. Вы можете использовать функцию sum, чтобы найти сумму элементов списка.

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
print("Это было несложно, да? :)")

Задача 9 (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("Похоже на правду!")

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

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

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("Отлично! Давайте сделаем что-нибудь посложнее.")

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

Напишите функцию primes(n), возвращающую список всех простых чисел от 2 до n (включая n, если оно простое). Вам необходимо использовать ранее написанную функцию is_prime (хотя это и не самый эффективный с точки зрения скорости способ решать эту задачу — эффективнее было бы использовать решето Эратосфена).

In [ ]:
# YOUR CODE HERE
In [ ]:
assert primes(2) == [2]
assert primes(3) == [2, 3]
assert primes(100) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
                       47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
assert primes(97) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
                       47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
assert primes(96) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
                       47, 53, 59, 61, 67, 71, 73, 79, 83, 89]
print("Похоже, верно")

Задача 12 (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("Ура! Получилось!")

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

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

Например, positives_first([-1, 2, -2, 3, 0]) должна вернуть [2, 3, -1, -2].

In [ ]:
# YOUR CODE HERE
In [ ]:
assert positives_first([-1, 2, -2, 3, 0]) == [2, 3, -1, -2]
assert positives_first([1, 2, 3]) == [1, 2, 3]
assert positives_first([3, 2, 1]) == [3, 2, 1]
assert positives_first([-1, -2, -3]) == [-1, -2, -3]
assert positives_first([-1, 2, -3]) == [2, -1, -3]
assert positives_first([-1] * 100 + [0] * 100 + 
                       [1] * 100) == [1] * 100 + [-1] * 100
assert positives_first([1]) == [1]
assert positives_first([-1]) == [-1]
print("Да, едем дальше")

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

Написать функцию all_positive(numbers), проверяющую, верно ли, что все числа в списке numbers являются положительными. Она должна вернуть True, если это верно, и False в противном случае.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert all_positive([1]) is True
assert all_positive([1, 2]) is True
assert all_positive([1, 2, -1]) is False
assert all_positive([-1]) is False
assert all_positive([1, -1]) is False
assert all_positive([1, 1, -1]) is False
assert all_positive([1, 1, -1, 1]) is False
assert all_positive([1, 0]) is False
assert all_positive([0, 1]) is False
assert all_positive([0, -10]) is False
assert all_positive([1, 10]) is True
print("Отлично, это была важная задача")

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

Написать функцию get_words(text), принимающую на вход строку, содержащую некоторый текст, и возвращающую список слов, идущих в этом тексте. В тексте слова могут быть разделены пробелами, а также знаками препинания (., ?, ,, !). Каждое слово в получающемся списке должно быть записано строчными буквами.

Например, get_words("Hello! This is a test,isn't it?") должна вернуть список ['hello', 'this', 'is', 'a', 'test', "isn't", 'it'].

Подсказка. У строк есть метод .replace(), позволяющий заменить в строке одни подстроки на другие. Например:

s = "This is a test"
w = s.replace("is", "ese")

Посмотрите, что теперь лежит в w.

Вы можете избавиться от знаков препинания с помощью .replace(), а затем разделить получившуюся строку по сериям пробелов с помощью .split(). Чтобы заменить прописные буквы на строчные можно использовать метод строк .lower().

In [ ]:
# YOUR CODE HERE
In [ ]:
assert get_words("Hello! This is a test,isn't it?") == ['hello', 'this', 'is', 
                                                        'a', 'test', "isn't", 
                                                        'it']

assert get_words("Haha!haha!hehe,hehe") == ['haha', 'haha', 'hehe', 'hehe']
assert get_words("this") == ['this']
assert get_words('this. that.') == ['this', 'that']
print("Первый шаг к обработке текстов сделан!")

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

Штирлиц использует следующий способ отправлять шифровки в Центр. У него есть шифроблокнот, представляющий собой список слов, которые он может использовать в своих сообщениях. Такой же шифроблокнот хранится в Центре. Каждая шифровка представляет собой последовательность целых чисел. Каждое число соответствует слову из шифроблокнота: 1 значит первое слово, 2 значит второе и т.д. Например, если шифроблокнот имеет вид: ["явка", "квартира", "револьвер", "провалена", "скоро"], а шифровка — "1 4", значит, было передано сообщение "явка провалена". (Штирлиц не знает Python, поэтому использует нумерацию, начинающуюся с единицы.)

Напишите функцию decode(pad, code), принимающую на вход список pad, соодержащий шифроблокнот (в виде списка слов), и строку code, содержащую сообщение (все числа разделены пробелами). Функция должна вернуть строку, представляющую собой закодированное сообщение.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert decode(["явка", "квартира", "револьвер", "провалена", "скоро"], 
              "1 4") == "явка провалена"
assert decode(['a', 'b'], "1 1 2 2 1 2") == 'a a b b a b'
assert decode(['aaa', 'b', 'cd'], ("1 2 3 " * 100)
              .strip()) == ("aaa b cd " * 100).strip()
assert decode(['aaa', 'b', 'cd'], ("1 3 " * 100)
              .strip()) == ("aaa cd " * 100).strip()
print("Это центр. Миссия успешно завершена. Повторяю, миссия успешна завершена. Продолжайте в том же духе. Приём.")

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

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

In [ ]:
# YOUR CODE HERE
In [ ]:
assert is_increasing([1, 2, 3, 4, 5]) is True
assert is_increasing([1, 10, 15, 16, 17]) is True
assert is_increasing([5])
assert is_increasing([5, 5]) is False
assert is_increasing([5, 6, 7, 7]) is False
assert not is_increasing([5, 6, 7, 8, 7])
assert not is_increasing([2, 1, 5, 6])
assert is_increasing([-4, -3, -2, -1])
print("Отлично! Это тоже очень важная задача")

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

Итоговая оценка вычисляется по формуле: $\text{накопленная} \times 0.75 + \text{экзамен} \times 0.25$ и округляется до целого числа. Если оценка имеет вид «целое + 1/2», то она округляется вверх (то есть до «целое + 1», в остальном округлением происходит к ближайшему целому. Написать функцию final_grade(acc, exam), которая бы принимала на вход накопленную и экзаменационную оценки и возвращала итоговую оценку.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert final_grade(1, 2) == 1
assert final_grade(acc=1, exam=2) == 1
assert final_grade(exam=2, acc=1) == 1
assert final_grade(1, 5) == 2
assert final_grade(0, 0) == 0
assert final_grade(0, 1) == 0
assert final_grade(0, 2) == 1
assert final_grade(0, 3) == 1
assert final_grade(0, 4) == 1
assert final_grade(0, 5) == 1
assert final_grade(0, 6) == 2
assert final_grade(0, 7) == 2
assert final_grade(0, 8) == 2
assert final_grade(0, 9) == 2
assert final_grade(1, 0) == 1
assert final_grade(1, 1) == 1
assert final_grade(1, 2) == 1
assert final_grade(1, 3) == 2
assert final_grade(1, 4) == 2
assert final_grade(1, 5) == 2
assert final_grade(1, 6) == 2
assert final_grade(1, 7) == 3
assert final_grade(1, 8) == 3
assert final_grade(1, 9) == 3
assert final_grade(2, 0) == 2
assert final_grade(2, 1) == 2
assert final_grade(2, 2) == 2
assert final_grade(2, 3) == 2
assert final_grade(2, 4) == 3
assert final_grade(2, 5) == 3
assert final_grade(2, 6) == 3
assert final_grade(2, 7) == 3
assert final_grade(2, 8) == 4
assert final_grade(2, 9) == 4
assert final_grade(3, 0) == 2
assert final_grade(3, 1) == 3
assert final_grade(3, 2) == 3
assert final_grade(3, 3) == 3
assert final_grade(3, 4) == 3
assert final_grade(3, 5) == 4
assert final_grade(3, 6) == 4
assert final_grade(3, 7) == 4
assert final_grade(3, 8) == 4
assert final_grade(3, 9) == 5
assert final_grade(4, 0) == 3
assert final_grade(4, 1) == 3
assert final_grade(4, 2) == 4
assert final_grade(4, 3) == 4
assert final_grade(4, 4) == 4
assert final_grade(4, 5) == 4
assert final_grade(4, 6) == 5
assert final_grade(4, 7) == 5
assert final_grade(4, 8) == 5
assert final_grade(4, 9) == 5
assert final_grade(5, 0) == 4
assert final_grade(5, 1) == 4
assert final_grade(5, 2) == 4
assert final_grade(5, 3) == 5
assert final_grade(5, 4) == 5
assert final_grade(5, 5) == 5
assert final_grade(5, 6) == 5
assert final_grade(5, 7) == 6
assert final_grade(5, 8) == 6
assert final_grade(5, 9) == 6
assert final_grade(6, 0) == 5
assert final_grade(6, 1) == 5
assert final_grade(6, 2) == 5
assert final_grade(6, 3) == 5
assert final_grade(6, 4) == 6
assert final_grade(6, 5) == 6
assert final_grade(6, 6) == 6
assert final_grade(6, 7) == 6
assert final_grade(6, 8) == 7
assert final_grade(6, 9) == 7
assert final_grade(7, 0) == 5
assert final_grade(7, 1) == 6
assert final_grade(7, 2) == 6
assert final_grade(7, 3) == 6
assert final_grade(7, 4) == 6
assert final_grade(7, 5) == 7
assert final_grade(7, 6) == 7
assert final_grade(7, 7) == 7
assert final_grade(7, 8) == 7
assert final_grade(7, 9) == 8
assert final_grade(8, 0) == 6
assert final_grade(8, 1) == 6
assert final_grade(8, 2) == 7
assert final_grade(8, 3) == 7
assert final_grade(8, 4) == 7
assert final_grade(8, 5) == 7
assert final_grade(8, 6) == 8
assert final_grade(8, 7) == 8
assert final_grade(8, 8) == 8
assert final_grade(8, 9) == 8
assert final_grade(9, 0) == 7
assert final_grade(9, 1) == 7
assert final_grade(9, 2) == 7
assert final_grade(9, 3) == 8
assert final_grade(9, 4) == 8
assert final_grade(9, 5) == 8
assert final_grade(9, 6) == 8
assert final_grade(9, 7) == 9
assert final_grade(9, 8) == 9
assert final_grade(9, 9) == 9
print("А это уже похоже на что-то практически полезное, да? :)")

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

Напишите функцию fib_not_greater_than(n), возвращающую максимальное число Фибоначчи, не превосходящее n.

In [ ]:
# YOUR CODE HERE
In [ ]:
assert fib_not_greater_than(2) == 2
assert fib_not_greater_than(3) == 3
assert fib_not_greater_than(4) == 3
assert fib_not_greater_than(5) == 5
assert fib_not_greater_than(8) == 8
assert fib_not_greater_than(7) == 5
assert fib_not_greater_than(9) == 8
assert fib_not_greater_than(100) == 89
assert fib_not_greater_than(1000) == 987
print("Фибоначчи вам уже теперь как брат родной, правда?")

Задача 20 (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('(' * 100 + ')' * 99)
assert  check_brackets('(' * 1000 + ')' * 1000)
print("Впечатляюще!")