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

Для выполнения задания найди ссылку-приглашение в онлайн чате, получи доступ к репозиторию с файлом-заготовкой и заполни пропуски в нём. Фиксируй изменения (делай коммиты) после решения каждой задачи. Оставь название файла неизменным, иначе робот-проверятель не найдёт твои ответы. Отправить решения на GitHub нужно до истечения установленного срока.

После завершения работы над каждым вопросом требуется фиксировать изменения (делать коммит), сопровождая его вменяемым описанием сделанного, например:

$ git add .
$ git commit -m "Решение вопроса X"

Так же не возбраняется в любое время проталкивать изменения на GitHub:

$ git push

Вопрос 1

Функция \(G(n)\) определена так:

\[G(n)=\begin{cases}n & n \leq 3\\G(n-1)+2\cdot G(n-2)+3\cdot G(n-3) & \text{иначе}\end{cases}\]

Напиши рекурсивную функцию g, которая вычисляет \(G(n)\). Затем напиши итеративную функцию g_iter, которая также вычисляет \(G(n)\).

def g(n):
    """Возвращает значение G(n), вычисленное рекурсивно.

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

def g_iter(n):
    """Возвращает значение G(n), вычисленное итеративно.

    >>> g_iter(1)
    1
    >>> g_iter(2)
    2
    >>> g_iter(3)
    3
    >>> g_iter(4)
    10
    >>> g_iter(5)
    22
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 2

Напиши функцию has_seven, которая принимает положительное целое k и возвращает булевый результат наличия в целом k цифры 7.

В решении нельзя использовать инструкции присвоения. 
def has_seven(k):
    """Проверка наличия цифры 7 в k
    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 3

Последовательность «пинг-понг» начинается с элемента 1, каждый последующий элемент отличается от предыдущего на единицу. В начале последовательность возрастает. Если номер элемента содержит цифру 7 или делится без остатка на 7, то направление меняется на противоположное. Ниже представлены первые 30 элементов последовательности. Направление изменяется в 7-ом, 14-ом, 17-ом, 21-ом и 28-ом элементах (показано квадратными скобками).

1

2

3

4

5

6

[7]

6

5

4

3

2

1

[0]

1

2

[3]

2

1

0

[-1]

0

1

2

3

4

[5]

[4]

5

6

Создай функцию pingpong, которая возвращает n-ый элемент последовательности «пинг-понг».

В решении этого вопроса также нельзя использовать инструкции присвоения. 
def pingpong(n):
    """Возвращает n-ый элемент последовательности «пинг-понг».

    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"
Если сходу никак не выходит, попробуй решить с присвоениями и циклами. Затем переведи результат на «рекурсивный язык».

Вопрос 4

Напиши функцию ten_pairs, принимающую положительное целое n и возвращающую количество пар цифр в n, в сумме образующих 10.

Число 7 823 952 содержит три таких пары: первая и четвертая цифры (7+3=10), вторая и третья цифры (8+2=10), вторая и последняя цифры (8+2=10).

Только рекурсия, только хардкор! Никаких инструкций присвоения. 
def ten_pairs(n):
    """Возвращает число пар цифр в положительном целом n, в сумме образующих 10.

    >>> ten_pairs(7823952)
    3
    >>> ten_pairs(55055)
    6
    >>> ten_pairs(9641469)
    6
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 5

Когда роботы восстанут и победят людишек, вся финансовая политика, в том числе и разнообразие монет, будет определяться степенями двойки: однорублёвая, двухрублёвая, четырехрублёвая, восьмирублёвая, шестнадцатирублёвая и так далее. И не будет предела номиналам этих монет.

Пусть набор монет образует размен для n рублей, если сумма номиналов этих монет равна n.

Например, следующие наборы являются разменами для 7 рублей:

  • 7 однорублёвых;

  • 5 однорублёвых и 1 двухрублёвая;

  • 3 однорублёвых и 2 двухрублёвых;

  • 3 однорублёвых и 1 четырехрублёвая;

  • 1 однорублёвая и 3 двухрублёвых;

  • 1 однорублёвая, 1 двухрублёвая и 1 четырехрублёвая.

Таким образом, существует 6 способов разменять 7 рублей. Напиши функцию count_change, которая принимает положительное целое amount и возвращает количество способов размена этой суммы инновационными монетами из недалёкого будущего.

def count_change(amount):
    """Возвращает количество способов размена amount киберденьгами.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 6* (для самых умных)

Рекурсивная функция вычисления факториала может быть написана в виде единственного выражения с применением условия:

>>> fact = lambda n: 1 if n == 1 else mul(n, fact(sub(n, 1)))
>>> fact(5)
120

Однако эта реализация базируется на том факте, что всё выражение связано с именем fact, которое используется внутри этого же выражения. Обычно любая рекурсивная функция вызывает саму себя с помощью обращения по имени. В этом задании нужно создать анонимную рекурсивную функцию, то есть такую, которая не использует никакое имя!

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

Для решения этой задачи необходимы встроенные функции sub и mul из модуля operator . 
from operator import sub, mul

def make_anonymous_factorial():
    """Возвращает выражение, вычисляющее факториал.

    >>> make_anonymous_factorial()(5)
    120
    """
    return ТВОЕ_ВЫРАЖЕНИЕ_ЗДЕСЬ

Не забудь отправить работу на проверку:

$ git add .
$ git commit -m "Окончательное решение"
$ git push